PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

Square form factorization, II

Volume 70 / 2022

Clinton Bradford, Samuel S. Wagstaff, Jr. Bulletin Polish Acad. Sci. Math. 70 (2022), 13-34 MSC: Primary 11A51; Secondary 11E16, 11R11, 11Y05. DOI: 10.4064/ba211003-1-11 Published online: 2 December 2022


We propose a new subexponential time integer factoring algorithm called SQUFOF2, based on ideas of D. Shanks and R. de Vogelaere. It begins by using a sieve like that in the multiple polynomial Quadratic Sieve to construct a square value of a binary quadratic form. It uses this value to produce a square form. Then it factors the integer $N$ as the original SQUFOF does by taking an inverse square root and following a nonprincipal cycle to a symmetry point. This marriage with the Quadratic Sieve transforms SQUFOF from an $O(N^{1/4})$ algorithm into one with subexponential time. On the way we prove new facts about the infrastructure distance, which is used in the time complexity analysis.


  • Clinton BradfordDepartment of Mathematics
    Purdue University
    West Lafayette, IN 47907-2067, USA
  • Samuel S. Wagstaff, Jr.Center for Education and Research
    in Information Assurance and Security
    Department of Computer Science
    Purdue University
    West Lafayette, IN 47907-1398, USA
    ORCID: 0000-0001-6855-784X

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image