Results 1 to 2 of 2

Math Help - Factoring large primes

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    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 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by posix_memalign View Post
    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


    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime factoring a large number.
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 10th 2011, 04:10 AM
  2. Replies: 13
    Last Post: December 19th 2010, 03:09 PM
  3. Factoring numbers into product of primes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2010, 05:17 AM
  4. factoring a large polynomial
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 29th 2008, 06:38 PM
  5. Factoring a large Diff of Squares
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 28th 2008, 01:49 PM

Search Tags


/mathhelpforum @mathhelpforum