Given a composite number $P$ and two integers $x$ and $y$ such that: $x^2 = y^2 \pmod P$ we can factor $P$ using factor = $\mathrm{gcd}(P, x-y)$ or $\mathrm{gcd}(P, x+y)$.

Now are there a similar relation where we are given multiple $(x_i, y_i)$ pairs such that:

  1. $(x_i^2 - y_i^2) \pmod P = r_i$ (where $r_i \neq 0$)
  2. We can still combine and use these pairs to find a factor of $P$ (in polynomial time) given these pairs (perhaps if the $r_i$'s are small enough or they share some structure with each other and so on).

Essentially a generalization of the congruence of squares.

  • $\begingroup$ Usually we reserve the letter $P$ for prime numbers. $\endgroup$
    – D.W.
    Mar 31 at 3:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.