When $n = pq$ where $p$ and $q$ are primes, we can generate random numbers until we get $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$. This implies $n$ has some common factor with $a^2-b^2$, and then we can use the Euclidean algorithm to find the gcd, which will be a factor of $n$.

However, I'm trying to figure out how to solve the problem when $n$ is an arbitrary number ($n$ being a product of two primes is not guaranteed). How could I generalize the above case to find a general solution?

  • 1
    $\begingroup$ Just repeat the process until you've reduced all the factors to primes? $\endgroup$ – Squeamish Ossifrage Nov 15 '19 at 2:56
  • $\begingroup$ Note: $n$ doesn't just have a common factor with $a^2 - b^2$; $n$ is a factor of $a^2 - b^2$, so $\gcd(n, a^2 - b^2)$ doesn't help. You need to go a step further to factor $n$. $\endgroup$ – Squeamish Ossifrage Nov 15 '19 at 2:58
  • $\begingroup$ (Hint: Can you write $a^2 - b^2$ another way?) $\endgroup$ – Squeamish Ossifrage Nov 15 '19 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.