On the solution of \(x^2-dy^2=\pm m\). (English) Zbl 1152.11320

The authors study the Pellian equation \(x^ 2-dy^ 2=\pm m\). Gauss gave an efficient algorithm for solving it. The authors give an algorithm that is (in the authors’ words “essentially the same as Gauss’ but a little more efficient and simpler”. Finally they propose an improvement of a factorization algorithm based on Shanks’ SQUFOF method.


11D09 Quadratic and bilinear Diophantine equations
11Y05 Factorization
11Y16 Number-theoretic algorithms; complexity
Full Text: DOI Euclid


[1] J.M. Basilla, On the solution of \(x^{2}+dy^{2}=m\), Proc. Japan Acad., 80A (2004), no. 5, 40-41. · Zbl 1106.11042
[2] H. Cohen, A course in computational algebraic number theory , Springer, Berlin, 1993. · Zbl 0786.11071
[3] C.F. Gauss, Disquisiones Arithmeticae , Fleischer, Leipzig, 1801.
[4] L.K. Hua, Introduction to number theory , Translated from the Chinese by Peter Shiu, Springer, Berlin, 1982. · Zbl 0483.10001
[5] M.A. Morrison and J. Brillhart, A method of factoring and the factorization of \(F_{7}\), Math. Comp. 29 (1975), 183-205. · Zbl 0302.10010
[6] O. Perron, Die Lehre von dem Kettenbrüchen I , Teubner, Stuttgart, 1954. · Zbl 0056.05901
[7] T. Takagi, Lectures on the elementary theory of numbers , 2nd ed., Kyoritsu-publication, Tokyo, 1971. (In Japanese). · Zbl 1098.81696
[8] H. Wada, A note on the Pell equation, Tokyo J. Math. 2 (1979), no. 1, 133-136. · Zbl 0413.10008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.