Thread: Factoring large primes

How can I use these facts:

880525^2 = 2 (mod 2288233)
2057202^2 = 3 (mod 2288233)
648581^2 = 6 (mod 2288233)
668676^2 = 77 (mod 2288233)


to factor 2288233 ?

Originally Posted by posix_memalign

How can I use these facts:
880525^2 = 2 (mod 2288233)
2057202^2 = 3 (mod 2288233)
648581^2 = 6 (mod 2288233)
668676^2 = 77 (mod 2288233)
to factor 2288233 ?

You have supplied:
648581^2 = 6 (mod 2288233)
&
[(880525)(2057202)]^2 = (2)(3) (mod 2288233)

Thus

GCD((880525)(2057202) - 648581 , 2288233) = 1871


This is why:
with the condition that x & y are NOT congruent modulo n:



subtract

&


Either (x+y) divides n
or (x-y) divides n