Square form factorization
Authors:
Jason E. Gower and Samuel S. Wagstaff Jr.
Journal:
Math. Comp. 77 (2008), 551588
MSC (2000):
Primary 11A51, 11E16, 11R11, 11Y05
Published electronically:
May 14, 2007
MathSciNet review:
2353967
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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.
 1.
Michael
A. Morrison and John
Brillhart, A method of factoring and the
factorization of 𝐹₇, Math.
Comp. 29 (1975),
183–205. Collection of articles dedicated to Derrick Henry Lehmer on
the occasion of his seventieth birthday. MR 0371800
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 2.
Duncan
A. Buell, Binary quadratic forms, SpringerVerlag, New York,
1989. Classical theory and modern computations. MR 1012948
(92b:11021)
 3.
Henri
Cohen, A course in computational algebraic number theory,
Graduate Texts in Mathematics, vol. 138, SpringerVerlag, Berlin,
1993. MR
1228206 (94i:11105)
 4.
Harvey
Cohn, A second course in number theory, John Wiley & Sons,
Inc., New YorkLondon, 1962. MR 0133281
(24 #A3115)
 5.
Jason E. Gower.
Square form factorization. Ph.D. thesis, Purdue University, December 2004.
 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. MR 0161833
(28 #5037)
 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. MR 697260
(86g:11080)
 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. MR 1083765
(91i: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. MR 1292250
(95h:11142)
 12.
D. Shanks.
Analysis and Improvement of the Continued Fraction Method of Factorization. Abstract 7201043. Amer. Math. Soc. Notices, 22:A68, 1975.
 13.
Daniel Shanks.
An Attempt to Factor . 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. MR 0316385
(47 #4932)
 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. MR 0389842
(52 #10672)
 18.
Daniel
Shanks, Five numbertheoretic 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. MR 0371855
(51 #8072)
 19.
Samuel
S. Wagstaff Jr., Cryptanalysis of number theoretic ciphers,
Computational Mathematics Series, Chapman & Hall/CRC, Boca Raton, FL,
2003. MR
2000260 (2004f:11144)
 1.
 J. Brillhart and M. A. Morrison.
A Method of Factoring and the Factorization of . Mathematics of Computation, 29:183205, 1975. MR 0371800 (51:8017)
 2.
 Duncan A. Buell.
Binary Quadratic Forms: Classical Theory and Modern Computations. SpringerVerlag, 1989. MR 1012948 (92b:11021)
 3.
 Henri Cohen.
A Course in Computational Algebraic Number Theory. SpringerVerlag, 1996. MR 1228206 (94i:11105)
 4.
 Harvey Cohn.
A Second Course in Number Theory. John Wiley & Sons, Inc., 1962. MR 0133281 (24:A3115)
 5.
 Jason E. Gower.
Square form factorization. Ph.D. thesis, Purdue University, December 2004.
 6.
 David Joyner and Stephen McMath.
http://cadigweb.ew.usna.edu/~wdj/mcmath/.
 7.
 A. Y. Khinchin.
Continued Fractions. The University of Chicago Press, third edition, 1964. MR 0161833 (28:5037)
 8.
 H. W. Lenstra, Jr.
On the Calculation of Regulators and Class Numbers of Quadratic Fields. In J. V. Armitage, editor, Journées Arithmétiques, 1980, volume 56 of Lecture Notes Series, pages 123150. London Mathematical Society, 1982. MR 0697260 (86g:11080)
 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. John Wiley & Sons, Inc., fifth edition, 1991. MR 1083765 (91i:11001)
 11.
 Hans Riesel.
Prime Numbers and Computer Methods for Factorization. Birkhaüser, second edition, 1994. MR 1292250 (95h:11142)
 12.
 D. Shanks.
Analysis and Improvement of the Continued Fraction Method of Factorization. Abstract 7201043. Amer. Math. Soc. Notices, 22:A68, 1975.
 13.
 Daniel Shanks.
An Attempt to Factor . 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. In Proceedings of Symposia in Pure Mathematics, volume 20, pages 415440. American Mathematical Society, 1971. MR 0316385 (47:4932)
 17.
 Daniel Shanks.
The Infrastructure of a Real Quadratic Field and its Applications. In Proceedings of the 1972 Number Theory Conference, pages 217224, Boulder, Colorado, 1972. MR 0389842 (52:10672)
 18.
 Daniel Shanks.
Five NumberTheoretic Algorithms. In Proceedings of the Second Manitoba Conference on Numerical Mathematics, pages 5170. Utilitas Mathematica, 1973. Number VII in Congressus Numerantium. MR 0371855 (51:8072)
 19.
 Samuel S. Wagstaff, Jr.
Cryptanalysis of Number Theoretic Ciphers. CRC Press, 2003. MR 2000260 (2004f:11144)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
11A51,
11E16,
11R11,
11Y05
Retrieve articles in all journals
with MSC (2000):
11A51,
11E16,
11R11,
11Y05
Additional Information
Jason E. Gower
Affiliation:
Institute for Mathematics and its Applications, University of Minnesota, 424 Lind Hall, 207 Church St. S.E., Minneapolis, Minnesota 554550436
Email:
gower@ima.umn.edu
Samuel S. Wagstaff Jr.
Affiliation:
Center for Education and Research in Information Assurance and Security, and Department of Computer Science, Purdue University, West Lafayette, Indiana 47907
Email:
ssw@cerias.purdue.edu
DOI:
http://dx.doi.org/10.1090/S0025571807020108
PII:
S 00255718(07)020108
Keywords:
Integer factorization,
binary quadratic form
Received by editor(s):
March 13, 2005
Received by editor(s) in revised form:
November 9, 2006
Published electronically:
May 14, 2007
Additional Notes:
This paper is based on the Ph.D.\ thesis of the first author, supervised by the second author. Both authors are grateful for the support of the CERIAS Center at Purdue University and by the Lilly Endowment Inc.
Dedicated:
This paper is dedicated to the memory of Daniel Shanks
Article copyright:
© Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
