On sharp transitions in making squares. (English) Zbl 1321.11122

Summary: In the fastest-performing integer factoring algorithms, one creates a sequence of integers (in a pseudo-random way) and wishes to rapidly determine a subsequence whose product is a square. In 1994 C. Pomerance [Proc. Int. Congr. Math., ICM 1994, vol. I, Basel, Birkhäuser, 411–422 (1995; Zbl 0854.11047)] stated the following problem which encapsulates all of the key issues: Select integers \(a_1,a_2,\ldots,\) at random from the interval \([1,x]\), until some (nonempty) subsequence has product equal to a square. Find a good estimate for the expected stopping time of this process. A good solution should allow one to determine the optimal choice of parameters in many factoring algorithms.
Pomerance (loc. cit.), using an idea of R. Schroeppel (1985), showed that with probability \(1-o(1)\) the first subsequence whose product equals a square occurs after at least \(J_0^{1-o(1)}\) integers have been selected, but no more than \(J_0\), for an appropriate (explicitly determined) \(J_0=J_0(x)\). We tighten Pomerance’s interval to \[ (\pi/4)(e^{-\gamma} - o(1)) J_0, (e^{-\gamma} + o(1)) J_0, \] where \(\gamma = 0.577\ldots \) is the Euler-Mascheroni constant, and believe that the correct interval is \((e^{-\gamma} - o(1))J_0, (e^{-\gamma} + o(1)) J_0\), a “sharp threshold”. In our proof we confirm the well-established belief that, typically, none of the integers in the square product have large prime factors. The heart of the proof of our upper bound lies in delicate calculations in probabilistic graph theory, supported by comparative estimates on smooth numbers using precise information on saddle points.


11Y05 Factorization
11Y16 Number-theoretic algorithms; complexity


Zbl 0854.11047
Full Text: DOI arXiv


[1] Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Abramowitz, M. and Stegun, I. A., Eds., New York: Dover Publications, 1965.
[2] J. P. Buhler, H. W. Lenstra Jr., and C. Pomerance, ”Factoring integers with the number field sieve,” in The Development of the Number Field Sieve, New York: Springer-Verlag, 1993, vol. 1554, pp. 50-94. · Zbl 0806.11067 · doi:10.1007/BFb0091539
[3] N. J. Calkin, ”Dependent sets of constant weight binary vectors,” Combin. Probab. Comput., vol. 6, iss. 3, pp. 263-271, 1997. · Zbl 0887.60015 · doi:10.1017/S0963548397003040
[4] R. Crandall and C. Pomerance, Prime Numbers; A Computational Perspective, Second ed., New York: Springer-Verlag, 2005. · Zbl 1088.11001
[5] E. Croot, A. Granville, R. Pemantle, and P. Tetali, ”Running time predictions for factoring algorithms,” in Algorithmic Number Theory, New York: Springer-Verlag, 2008, vol. 5011, pp. 1-36. · Zbl 1205.11132 · doi:10.1007/978-3-540-79456-1_1
[6] J. D. Dixon, ”Asymptotically fast factorization of integers,” Math. Comp., vol. 36, iss. 153, pp. 255-260, 1981. · Zbl 0452.10010 · doi:10.2307/2007743
[7] R. Durrett, Probability. Theory and Examples, Pacific Grove, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1991. · Zbl 0709.60002
[8] E. Friedgut, ”Sharp thresholds of graph properties, and the \(k\)-sat problem,” J. Amer. Math. Soc., vol. 12, iss. 4, pp. 1017-1054, 1999. · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[9] A. Granville and K. Soundararajan, ”Large character sums,” J. Amer. Math. Soc., vol. 14, iss. 2, pp. 365-397, 2001. · Zbl 0983.11053 · doi:10.1090/S0894-0347-00-00357-X
[10] A. Hildebrand and G. Tenenbaum, ”On integers free of large prime factors,” Trans. Amer. Math. Soc., vol. 296, iss. 1, pp. 265-290, 1986. · Zbl 0601.10028 · doi:10.2307/2000573
[11] P. Leroux, ”Enumerative Problems Inspired by Mayer’s Theory of Cluster Integrals,” Electron. J. Combin., 2004. · Zbl 1054.05056
[12] C. Pomerance, ”The quadratic sieve factoring algorithm,” in Advances in Cryptology, New York: Springer-Verlag, 1985, vol. 209, pp. 169-182. · Zbl 0596.10006 · doi:10.1007/3-540-39757-4_17
[13] C. Pomerance, ”The number field sieve,” in Mathematics of Computation 1943-1993: a Half-Century of Computational Mathematics, Providence, RI: Amer. Math. Soc., 1994, vol. 48, pp. 465-480. · Zbl 0821.11064
[14] C. Pomerance, ”The role of smooth numbers in number-theoretic algorithms,” in Proceedings of the International Congress of Mathematicians, Vol. 1, 2, Basel, 1995, pp. 411-422. · Zbl 0854.11047
[15] C. Pomerance, ”Multiplicative independence for random integers,” in Analytic Number Theory, Vol. 2, Boston, MA: Birkhäuser, 1996, vol. 139, pp. 703-711. · Zbl 0865.11085
[16] C. Pomerance, ”Smooth numbers and the quadratic sieve,” in Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge: Cambridge Univ. Press, 2008, vol. 44, pp. 69-81. · Zbl 1188.11065
[17] R. D. Silverman, ”The multiple polynomial quadratic sieve,” Math. Comp., vol. 48, iss. 177, pp. 329-339, 1987. · Zbl 0608.10004 · doi:10.2307/2007894
[18] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge: Cambridge Univ. Press, 1995, vol. 46. · Zbl 0880.11001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.