0
$\begingroup$

I've been hitting myself in the head trying to figure this problem out, but no luck so far. Let $N$ be an integer that equals the product of two odd primes, and $\gcd(a, N) = 1$ (i'll specify $a$ in a bit). Suppose I knew how to find all four solutions to $x^2 \equiv a \mod N$ for some $a$. How can I factor $N$ with this assumption?

This is the second part of a homework question, but I asked about a homework question (1st part) earlier today (maybe it'll help with this problem)

Perfect square modulo $n = pq$

So far, i've been trying different examples, but I haven't seen a consistent pattern. What I do see is that the four solutions have to do with the factors of $N$, where in some examples I did, subtracting two solutions gave me a factor of $N$.

One example I did:

Primes: 3 and 5

The problem: $x^2 \equiv a \mod N$

The only possible $a$ values with solutions are $1$ and $4$ mod 15.

When $a = 1$, I found that my solutions are 1, 4, 11, 14 mod 15.

When $a = 4$, my solutions are $2, 7, 8, 13$.

I did it for other 2 distinct odd primes, but they did not provide me with an insight.

Thanks.

  • 2
    A hint: the solutions pair off into pairs that sum to zero (ex 1 and 14, 4 and 11). Take one from each pair (say 1 and 11) and add them, (giving 12 in this case). What can we tell about this new value?2012-06-28
  • 0
    I got the pattern and I think I did it the way you did. I used gcd in the process. Not sure how to explain the workings behind it, but I just know it works, hehe. Thanks Thomas.2012-06-28
  • 0
    Cool! See if you can use some of the work from the problem you linked to show why it works! :)2012-06-28

1 Answers 1