Results 1 to 2 of 2

Math Help - factorization by finding modular square roots

  1. #1
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    factorization by finding modular square roots

    Prove that having three distinct solutions of the conguence x^2=y\mod n, where n,\,y are known and n=pq is a product of distinct primes, we can find p and q efficiently.

    I've managed to prove, with the Chinese remainder theorem, that the congruence always has four distinct solutions and that we can easily find the fourth solution when we have three.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: factorization by finding modular square roots

    Quote Originally Posted by ymar View Post
    Prove that having three distinct solutions of the conguence x^2=y\mod n, where n,\,y are known and n=pq is a product of distinct primes, we can find p and q efficiently.

    I've managed to prove, with the Chinese remainder theorem, that the congruence always has four distinct solutions and that we can easily find the fourth solution when we have three.
    Suppose that the three solutions are r, s, t: r^2\equiv s^2\equiv t^2\equiv y\pmod n. Then 0\equiv r^2-s^2 = (r+s)(r-s)\pmod n. That can only happen if s\equiv\pm r\pmod n, or r+s and rs are equal (mod n) to the two proper divisors of n, namely p and q. In the latter case, we have efficiently found p and q. So we have to deal with the former case, when s\equiv -r\pmod n (we know that r and s are distinct, so we cannot have s\equiv r\pmod n).

    In a similar way, (r+t)(r-t)\equiv 0\pmod n. But t≠r and t≠r(=s). Therefore r+t and rt are equal (mod n) to p and q. So again we have efficiently found p and q.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 4th 2010, 01:49 AM
  2. Finding square roots mod n
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 5th 2009, 02:48 AM
  3. Modular Arithmetic- brain teezer- finding x
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 8th 2008, 06:42 PM
  4. Replies: 5
    Last Post: March 22nd 2008, 05:28 PM

Search Tags


/mathhelpforum @mathhelpforum