An efficient solution of the congruencex^2 + ky^2 = mpmod{n}
John M. Pollard, Claus Peter Schnorr · IEEE Transactions on Information Theory · 1987
The equation of the title arose in the proposed signature scheme of Ong-Schnorr-Shamir. The large integersn, kandmare given and we are asked to find any solutionx, y. It was believed that this task was of similar difficulty to that of factoring the modulusn;we show that, on the contrary, a solution can easily be found ifkandmare relatively prime ton. Under the assumption of the generalized Riemann hypothesis, a solution can be found by a probabilistic algorithm inO(\log n)^{2}|\log\log|k||)arithmetical steps onO(\log n)-bit integers. The algorithm can be extended to solve the equationX^{2} + KY^{2} = M \pmod{n}for quadratic integersK, M \in {\bf Z}[\sqrt{d}]and to solve in integers the equationx^{3} + ky_{3} + k^{2}z^{3} - 3kxyz = m \pmod{n}.