Square form factorization, II

• Autorzy: Bradford Clinton , Wagstaff Samuel S. Jr

Identyfikatory

DOI

10.4064/ba211003-1-11

• Języki publikacji: EN

Abstrakty

EN

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(N1/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.

Słowa kluczowe

EN

integer factorization; binary quadratic form; infrastructure distance

• Wydawca: Instytut Matematyczny PAN
• Czasopismo: Bulletin of the Polish Academy of Sciences. Mathematics
• Rocznik: 2022
• Tom: Vol. 70, no. 1
• Strony: 13--34
• Opis fizyczny: Bibliogr. 22 poz., tab.

Twórcy

autor

Bradford Clinton

• Department of Mathematics, Purdue University West Lafayette, IN 47907-2067, USA

autor

Wagstaff Samuel S. Jr

• Center for Education and Research in Information Assurance and Security
• Department of Computer Science ,Purdue University West Lafayette, IN 47907-1398, USA

• https://orcid.org/0000-0001-6855-784X

Bibliografia

• [1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1976.
• [2] E. Bach and J. Shallit, Algorithmic Number Theory, Vol. I: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.
• [3] D. A. Buell, Binary Quadratic Forms: Classical Theory and Modern Computations, Springer, Berlin, 1989.
• [4] E. R. Canfield, P. Erdős, and C. Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), 1-28.
• [5] H. Cohen, A Course in Computational Algebraic Number Theory, Springer, New York, 1996.
• [6] D. Coppersmith and S. Winograd, On the asymptotic complexity of matrix multiplication, SIAM J. Comput. 11 (1982), 472-492.
• [7] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, New York, 2001.
• [8] K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Ark. Mat. Astronom. Fys. A 22 (1930), no. 10, 14 pp.
• [9] C. F. Gauss, Disquisitiones Arithmeticae, Yale Univ. Press, New Haven, CT, 1966 (English ed.).
• [10] J. E. Gower and S. S. Wagstaff, Jr., Square form factorization, Math. Comp. 77 (2008), 551-588.
• [11] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Clarendon Press, Oxford, 1979.
• [12] D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, MA, 1981.
• [13] D. E. Knuth and L. Trabb Pardo, Analysis of a simple factorization algorithm, Theoret. Computer Sci. 3 (1976), 321-348.
• [14] H. W. Lenstra, Jr., On the calculation of regulators and class numbers of quadratic fields, in: J. V. Armitage (ed.), Journées Arithmétiques, 1980, London Math. Soc. Lecture Note Ser. 56, Cambridge Univ. Press, Cambridge, 1982, 123-150.
• [15] H. W. Lenstra, Jr., and C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483-516.
• [16] C. Pomerance, Analysis and comparison of some integer factoring algorithms, in: H. W. Lenstra, Jr., and R. Tijdeman (eds.), Computational Methods in Number Theory, Part 1, Math. Centre Tracts 154, CWI, Amsterdam, 1982, 89-139.
• [17] P. Pritchard, A sublinear additive sieve for finding prime numbers, Comm. ACM 24 (1981), 18-23.
• [18] D. Shanks, The infrastructure of a real quadratic field and its applications, in: Proc. 1972 Number Theory Conf. (Boulder, CO), Univ. of Colorado, Boulder, CO, 1972, 217-224.
• [19] D. Shanks, Square forms factorization, lecture, before 1975.
• [20] D. Shanks, SQUFOF (an unfinished manuscript), available at https://homes.cerias.purdue.edu/~ssw/shanks.pdf.
• [21] A. J. van der Poorten, A note on NUCOMP, Math. Comp. 72 (2003), 1935-1946.
• [22] S. S. Wagstaff, Jr., The Joy of Factoring, Student Math. Library 68, Amer. Math. Soc., Providence, RI, 2013.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).