bradfor3_Square_Forms_Thesis_slight_format_tweak.pdf (378.5 kB)
Download fileSquare Forms Factoring with Sieves
Square Form Factoring is an O(N1/4) factoring algorithm developed by D. Shanks using certain properties of quadratic forms. Central to the original algorithm is an iterative search for a square form. We propose a new subexponential-time algorithm called SQUFOF2, based on ideas of D. Shanks and R. de Vogelaire, which replaces the iterative search with a sieve, similar to the Quadratic Sieve.
History
Degree Type
- Doctor of Philosophy
Department
- Mathematics
Campus location
- West Lafayette
Advisor/Supervisor/Committee Chair
Samuel S. WagstaffAdditional Committee Member 2
William HeinzerAdditional Committee Member 3
Tong LiuAdditional Committee Member 4
David McReynoldsUsage metrics
Categories
Keywords
factoringfactoring algorithmssubexponential factoring algorithmsquadratic formsSQUFOFSQUFOF2Square Forms Factoringsquare formsintegral binary quadratic formsindefinite quadratic formsindefinite integral binary quadratic formspolynomial sievesquadratic sieveinfrastructure distanceAlgebra and Number Theory