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 ?

Printable View

- October 4th 2009, 06:55 PMposix_memalignFactoring 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 ? - October 5th 2009, 04:19 AMaidan
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