= Solution
The <multiplicative order> of $\alpha$ modulo $N$ is the least positive integer $r$ such that
$$
\alpha^r\equiv1\pmod N.
$$
It exists because $\alpha$ and $N$ are <coprime integers>.
Suppose that $r$ is <even> and
$$
\alpha^{r/2}\not\equiv-1\pmod N.
$$
The minimality of $r$ also gives $\alpha^{r/2}\not\equiv1\pmod N$. Since
$$
(\alpha^{r/2}-1)(\alpha^{r/2}+1)
=\alpha^r-1\equiv0\pmod N,
$$
the <factor extraction from an even modular order> yields
$$
\boxed{\gcd(\alpha^{r/2}-1,N)}
$$
as a nontrivial factor of $N$; equivalently one may also compute $\gcd(\alpha^{r/2}+1,N)$. Thus the required conditions are that $r$ be even and that $\alpha^{r/2}\not\equiv-1\pmod N$.
Back to article page
