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.

For an odd integer $N$ having at least two distinct prime divisors, choose a uniform unit $a\mathrm{mod}N$. The Chinese remainder theorem for unit groups makes its odd-prime-power components independent cyclic groups. Failure of factor extraction from an even modular order requires all components to have equal 2-primary order exponents. For any component each possible exponent has probability at most $1/2$, so conditioning on another component bounds failure by $1/2$. Excluding the identity unit only improves the success proportion.