Square form factorization

Gower, Jason; Wagstaff, Samuel, Jr.

doi:10.1090/S0025-5718-07-02010-8

Square form factorization
HTML articles powered by AMS MathViewer

by Jason E. Gower and Samuel S. Wagstaff Jr. PDF

Math. Comp. 77 (2008), 551-588 Request permission

Abstract:

We present a detailed analysis of SQUFOF, Daniel Shanks’ Square Form Factorization algorithm. We give the average time and space requirements for SQUFOF. We analyze the effect of multipliers, either used for a single factorization or when racing the algorithm in parallel.

References

Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5
Duncan A. Buell, Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR 1012948, DOI 10.1007/978-1-4612-4542-1
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Harvey Cohn, A second course in number theory, John Wiley & Sons, Inc., New York-London, 1962. MR 0133281
Jason E. Gower. Square form factorization. Ph.D. thesis, Purdue University, December 2004.
David Joyner and Stephen McMath. http://cadigweb.ew.usna.edu/~wdj/mcmath/.
A. Ya. Khinchin, Continued fractions, University of Chicago Press, Chicago, Ill.-London, 1964. MR 0161833
H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260
J. S. Milne. Algebraic Number Theory, 1998. available at http://www.math.lsa.umich.edu/~jmilne.
Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An introduction to the theory of numbers, 5th ed., John Wiley & Sons, Inc., New York, 1991. MR 1083765
Hans Riesel, Prime numbers and computer methods for factorization, 2nd ed., Progress in Mathematics, vol. 126, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1292250, DOI 10.1007/978-1-4612-0251-6
D. Shanks. Analysis and Improvement of the Continued Fraction Method of Factorization. Abstract 720-10-43. Amer. Math. Soc. Notices, 22:A–68, 1975.
Daniel Shanks. An Attempt to Factor ${N}=1002742628021$. Manuscript, 3 pages, available at [6].
Daniel Shanks. Notes for Analysis and Improvement of the Continued Fraction Method of Factorization. Manuscript, 15 pages, available at [6].
Daniel Shanks. SQUFOF Notes. Manuscript, 30 pages, available at [6].
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
Daniel Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972) Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842
Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. MR 0371855
Samuel S. Wagstaff Jr., Cryptanalysis of number theoretic ciphers, Computational Mathematics Series, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 2000260