Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Square form factorization


Authors: Jason E. Gower and Samuel S. Wagstaff Jr.
Journal: Math. Comp. 77 (2008), 551-588
MSC (2000): Primary 11A51, 11E16, 11R11, 11Y05
Published electronically: May 14, 2007
MathSciNet review: 2353967
Full-text 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.


References [Enhancements On Off] (What's this?)


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 55455-0436
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/S0025-5718-07-02010-8
PII: S 0025-5718(07)02010-8
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.