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

Basilla, Julius M.; Wada, Hideo

Proc. Japan Acad., Ser. A 81, No. 8, 137-140 (2005).

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.

Reviewer: Olaf Ninnemann (Berlin)

MSC:

11D09	Quadratic and bilinear Diophantine equations
11Y05	Factorization
11Y16	Number-theoretic algorithms; complexity

Keywords:

quadratic Diophantine equation; Pell equation; continued fraction method; prime decomposition

References:

[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