An efficient solution of the congruence $x^2 + ky^2 = m\\pmod{n}$

Author

Pollard, John M. ; Schnorr, Claus P.

Volume

Issue

fYear

1987

fDate

9/1/1987 12:00:00 AM

Firstpage

702

Lastpage

709

Abstract

The equation of the title arose in the proposed signature scheme of Ong-Schnorr-Shamir. The large integers $n, k$ and $m$ are given and we are asked to find any solution $x, y$ . It was believed that this task was of similar difficulty to that of factoring the modulus $n;$ we show that, on the contrary, a solution can easily be found if $k$ and $m$ are relatively prime to $n$ . Under the assumption of the generalized Riemann hypothesis, a solution can be found by a probabilistic algorithm in $O(\\log n)^{2}|\\log \\log |k||)$ arithmetical steps on $O(\\log n)$ -bit integers. The algorithm can be extended to solve the equation $X^{2} + KY^{2} = M \\pmod {n}$ for quadratic integers $K, M \\in {\\bf Z}[\\sqrt {d}]$ and to solve in integers the equation $x^{3} + ky_{3} + k^{2}z^{3} - 3kxyz = m \\pmod {n}$ .

Keywords

Cryptography; Feedback communication; Number theory; Polynomials; Digital signatures; Equations; Helium; Polynomials; Public key; Public key cryptography;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.1987.1057350

Filename

1057350

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=943353