# Factoring large primes

• October 4th 2009, 06:55 PM
posix_memalign
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 ?
• October 5th 2009, 04:19 AM
aidan
Quote:

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:

$x^2 \equiv r \, (mod \,\, n)$
$y^2 \equiv r \, (mod \,\, n)$
subtract
$x^2 - y^2 \equiv r-r \, (mod \,\, n)$
&
$(x+y)(x-y) \equiv 0 \, (mod \,\, n)$

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