Quote:
Originally Posted by paulunderwood
Please tell us how one gets a factor from the conditions you mention above,

If
3^(N1) == 1 (mod N), and
3^((N1)/2) == M (mod N), then
M^2 == 1 (mod N), so (assuming 1 <= M < N)
we have (M  1)*(M + 1) == 0 (mod N).
If M == 1 (mod N) or M == 1 (mod N), one of the factors is 0 (mod N).
Otherwise, M  1 =/= 0 (mod N), M + 1 =/= 0 (mod N), and (M+1)*(M+1) == 0 (mod N). Since gcd(M1, M+1)  2 then, assuming N is odd, we have
gcd(M1, N) * gcd(M+1, N)
is a proper factorization of N.