×

Square form factorization. (English) Zbl 1126.11004

Authors’ summary: 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.

MSC:

11A51 Factorization; primality
11E16 General binary quadratic forms
11R11 Quadratic extensions
11Y05 Factorization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Michael A. Morrison and John Brillhart, A method of factoring and the factorization of \?\(_{7}\), Math. Comp. 29 (1975), 183 – 205. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. · Zbl 0302.10010
[2] Duncan A. Buell, Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. · Zbl 0698.10013
[3] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[4] Harvey Cohn, A second course in number theory, John Wiley & Sons, Inc., New York-London, 1962. · Zbl 0208.31501
[5] Jason E. Gower. Square form factorization. Ph.D. thesis, Purdue University, December 2004. · Zbl 1126.11004
[6] David Joyner and Stephen McMath. http://cadigweb.ew.usna.edu/ wdj/mcmath/.
[7] A. Ya. Khinchin, Continued fractions, The University of Chicago Press, Chicago, Ill.-London, 1964. · Zbl 0117.28601
[8] 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.
[9] J. S. Milne. Algebraic Number Theory, 1998. available at http://www.math.lsa.umich.edu/  jmilne.
[10] 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. · Zbl 0742.11001
[11] Hans Riesel, Prime numbers and computer methods for factorization, 2nd ed., Progress in Mathematics, vol. 126, Birkhäuser Boston, Inc., Boston, MA, 1994. · Zbl 0821.11001
[12] D. Shanks. Analysis and Improvement of the Continued Fraction Method of Factorization. Abstract 720-10-43. Amer. Math. Soc. Notices, 22:A-68, 1975.
[13] Daniel Shanks. An Attempt to Factor \( {N}=1002742628021\). Manuscript, 3 pages, available at [6].
[14] Daniel Shanks. Notes for Analysis and Improvement of the Continued Fraction Method of Factorization. Manuscript, 15 pages, available at [6].
[15] Daniel Shanks. SQUFOF Notes. Manuscript, 30 pages, available at [6].
[16] 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.
[17] 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. · Zbl 0334.12005
[18] Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973, pp. 51 – 70. Congressus Numerantium, No. VII.
[19] Samuel S. Wagstaff Jr., Cryptanalysis of number theoretic ciphers, Computational Mathematics Series, Chapman & Hall/CRC, Boca Raton, FL, 2003. · Zbl 1045.11001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.