View Single Post
Old 2020-01-23, 22:37   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,271 Posts
Default

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

3^(N-1) == 1 (mod N), and

3^((N-1)/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(M-1, M+1) | 2 then, assuming N is odd, we have

gcd(M-1, N) * gcd(M+1, N)

is a proper factorization of N.
Dr Sardonicus is offline   Reply With Quote