 Factor extraction from an even modular order

If $r$ is even, $a^r\equiv 1(\mathrm{mod}N)$, and $a^{r/2}\not\equiv -1(\mathrm{mod}N)$, then $\gcd (a^{r/2}-1,N)$ is a nontrivial factor unless the order was not minimal.