Factor extraction from an even modular order
= Factor extraction from an even modular order
If $r$ is even, $a^r\equiv1\pmod N$, and $a^{r/2}\not\equiv-1\pmod N$, then $\gcd(a^{r/2}-1,N)$ is a nontrivial factor unless the order was not minimal.
= Factor extraction from an even modular order
If $r$ is even, $a^r\equiv1\pmod N$, and $a^{r/2}\not\equiv-1\pmod N$, then $\gcd(a^{r/2}-1,N)$ is a nontrivial factor unless the order was not minimal.