On sharp transitions in making squares

Abstract

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 Pomerance stated the following problem which encapsulates all of the key issues: Select integers $a_1,a_2,\dots,$ 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 (1994), using an idea of 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…$ 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.

  • [AS] Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Abramowitz, M. and Stegun, I. A., Eds., New York: Dover Publications, 1965.
    @book{AS, EDITOR={Abramowitz, M. and Stegun, I. A.},
      TITLE={Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables},
      PUBLISHER={Dover Publications},
      ADDRESS={New York},
      YEAR={1965},
     }
  • [buhler] Go to document 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.
    @incollection {buhler, MRKEY = {1321221},
      AUTHOR = {Buhler, J. P. and Lenstra, Jr., H. W. and Pomerance, Carl},
      TITLE = {Factoring integers with the number field sieve},
      BOOKTITLE = {The Development of the Number Field Sieve},
      SERIES = {Lecture Notes in Math.},
      VOLUME = {1554},
      PAGES = {50--94},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1993},
      MRCLASS = {11Y05 (11N36 11Y40)},
      MRNUMBER = {1321221},
      DOI = {10.1007/BFb0091539},
      ZBLNUMBER = {0806.11067},
      }
  • [Calkin] Go to document N. J. Calkin, "Dependent sets of constant weight binary vectors," Combin. Probab. Comput., vol. 6, iss. 3, pp. 263-271, 1997.
    @article {Calkin, MRKEY = {1464565},
      AUTHOR = {Calkin, Neil J.},
      TITLE = {Dependent sets of constant weight binary vectors},
      JOURNAL = {Combin. Probab. Comput.},
      FJOURNAL = {Combinatorics, Probability and Computing},
      VOLUME = {6},
      YEAR = {1997},
      NUMBER = {3},
      PAGES = {263--271},
      ISSN = {0963-5483},
      MRCLASS = {60C05},
      MRNUMBER = {1464565},
      MRREVIEWER = {Nikolai Volodin},
      DOI = {10.1017/S0963548397003040},
      ZBLNUMBER = {0887.60015},
      }
  • [CP] R. Crandall and C. Pomerance, Prime Numbers; A Computational Perspective, Second ed., New York: Springer-Verlag, 2005.
    @book {CP, MRKEY = {2156291},
      AUTHOR = {Crandall, Richard and Pomerance, Carl},
      TITLE = {Prime Numbers; A Computational Perspective},
      EDITION = {Second},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2005},
      PAGES = {xvi+597},
      ISBN = {978-0-387-25282-7; 0-387-25282-7},
      MRCLASS = {11A41 (11A51 11Y05 11Y11 11Y35)},
      MRNUMBER = {2156291},
      MRREVIEWER = {Robert Juricevic},
      ZBLNUMBER = {1088.11001},
      }
  • [CGPT] Go to document 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.
    @incollection {CGPT, MRKEY = {2467835},
      AUTHOR = {Croot, Ernie and Granville, Andrew and Pemantle, Robin and Tetali, Prasad},
      TITLE = {Running time predictions for factoring algorithms},
      BOOKTITLE = {Algorithmic Number Theory},
      SERIES = {Lecture Notes in Comput. Sci.},
      VOLUME = {5011},
      PAGES = {1--36},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2008},
      MRCLASS = {11Y05 (11Y16 68W40)},
      MRNUMBER = {2467835},
      MRREVIEWER = {S. V. Nagaraj},
      DOI = {10.1007/978-3-540-79456-1_1},
      ZBLNUMBER = {1205.11132},
      }
  • [dixon] Go to document J. D. Dixon, "Asymptotically fast factorization of integers," Math. Comp., vol. 36, iss. 153, pp. 255-260, 1981.
    @article {dixon, MRKEY = {0595059},
      AUTHOR = {Dixon, John D.},
      TITLE = {Asymptotically fast factorization of integers},
      JOURNAL = {Math. Comp.},
      FJOURNAL = {Mathematics of Computation},
      VOLUME = {36},
      YEAR = {1981},
      NUMBER = {153},
      PAGES = {255--260},
      ISSN = {0025-5718},
      CODEN = {MCMPAF},
      MRCLASS = {10A30 (10A25)},
      MRNUMBER = {0595059},
      MRREVIEWER = {H. L. Abbott},
      DOI = {10.2307/2007743},
      ZBLNUMBER = {0452.10010},
      }
  • [poisson] R. Durrett, Probability. Theory and Examples, Pacific Grove, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1991.
    @book {poisson, MRKEY = {1068527},
      AUTHOR = {Durrett, Richard},
      TITLE = {Probability. Theory and Examples},
      SERIES = {The Wadsworth \& Brooks/Cole Statistics/Probability Series},
      PUBLISHER = {Wadsworth \& Brooks/Cole Advanced Books \& Software},
      ADDRESS = {Pacific Grove, CA},
      YEAR = {1991},
      PAGES = {x+453},
      ISBN = {0-534-13206-5},
      MRCLASS = {60-01},
      MRNUMBER = {1068527},
      MRREVIEWER = {George L. O'Brien},
      ZBLNUMBER = {0709.60002},
      }
  • [friedgut] Go to document E. Friedgut, "Sharp thresholds of graph properties, and the $k$-sat problem," J. Amer. Math. Soc., vol. 12, iss. 4, pp. 1017-1054, 1999.
    @article {friedgut, MRKEY = {1678031},
      AUTHOR = {Friedgut, Ehud},
      TITLE = {Sharp thresholds of graph properties, and the {$k$}-sat problem},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {12},
      YEAR = {1999},
      NUMBER = {4},
      PAGES = {1017--1054},
      ISSN = {0894-0347},
      MRCLASS = {05C80 (42C10)},
      MRNUMBER = {1678031},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1090/S0894-0347-99-00305-7},
      ZBLNUMBER = {0932.05084},
      }
  • [GS] Go to document A. Granville and K. Soundararajan, "Large character sums," J. Amer. Math. Soc., vol. 14, iss. 2, pp. 365-397, 2001.
    @article {GS, MRKEY = {1815216},
      AUTHOR = {Granville, Andrew and Soundararajan, K.},
      TITLE = {Large character sums},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {14},
      YEAR = {2001},
      NUMBER = {2},
      PAGES = {365--397},
      ISSN = {0894-0347},
      MRCLASS = {11L40 (11N25)},
      MRNUMBER = {1815216},
      MRREVIEWER = {S. W. Graham},
      DOI = {10.1090/S0894-0347-00-00357-X},
      ZBLNUMBER = {0983.11053},
      }
  • [hild] Go to document A. Hildebrand and G. Tenenbaum, "On integers free of large prime factors," Trans. Amer. Math. Soc., vol. 296, iss. 1, pp. 265-290, 1986.
    @article {hild, MRKEY = {0837811},
      AUTHOR = {Hildebrand, Adolf and Tenenbaum, G{é}rald},
      TITLE = {On integers free of large prime factors},
      JOURNAL = {Trans. Amer. Math. Soc.},
      FJOURNAL = {Transactions of the American Mathematical Society},
      VOLUME = {296},
      YEAR = {1986},
      NUMBER = {1},
      PAGES = {265--290},
      ISSN = {0002-9947},
      CODEN = {TAMTAM},
      MRCLASS = {11N25},
      MRNUMBER = {0837811},
      MRREVIEWER = {Aleksandar Ivi{ć}},
      DOI = {10.2307/2000573},
      ZBLNUMBER = {0601.10028},
      }
  • [pierre] P. Leroux, "Enumerative Problems Inspired by Mayer’s Theory of Cluster Integrals," Electron. J. Combin., 2004.
    @article{pierre,
      author={Leroux, P.},
      TITLE={Enumerative Problems Inspired by {M}ayer's Theory of Cluster Integrals},
      JOURNAL={Electron. J. Combin.},
      NOTE={paper R32, May 14},
      YEAR={2004},
     }
  • [pom0] Go to document C. Pomerance, "The quadratic sieve factoring algorithm," in Advances in Cryptology, New York: Springer-Verlag, 1985, vol. 209, pp. 169-182.
    @incollection {pom0, MRKEY = {0825590},
      AUTHOR = {Pomerance, Carl},
      TITLE = {The quadratic sieve factoring algorithm},
      BOOKTITLE = {Advances in Cryptology},
      VENUE={{P}aris, 1984},
      SERIES = {Lecture Notes in Comput. Sci.},
      VOLUME = {209},
      PAGES = {169--182},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1985},
      MRCLASS = {11Y05 (68Q25 68R05 94A60)},
      MRNUMBER = {0825590},
      MRREVIEWER = {Claus-Peter Schnorr},
      DOI = {10.1007/3-540-39757-4_17},
      ZBLNUMBER = {0596.10006},
      }
  • [pom4] 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.
    @incollection {pom4, MRKEY = {1314884},
      AUTHOR = {Pomerance, Carl},
      TITLE = {The number field sieve},
      BOOKTITLE = {Mathematics of {C}omputation 1943--1993: a Half-Century of Computational Mathematics},
      VENUE={{V}ancouver, {BC},
      1993},
      SERIES = {Proc. Sympos. Appl. Math.},
      VOLUME = {48},
      PAGES = {465--480},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, RI},
      YEAR = {1994},
      MRCLASS = {11Y05 (11N35)},
      MRNUMBER = {1314884},
      MRREVIEWER = {Michael Filaseta},
      ZBLNUMBER = {0821.11064},
      }
  • [pom1] 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.
    @inproceedings {pom1, MRKEY = {1403941},
      AUTHOR = {Pomerance, Carl},
      TITLE = {The role of smooth numbers in number-theoretic algorithms},
      BOOKTITLE = {Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol. 1, 2},
      VENUE={{Z}ürich, 1994},
      PAGES = {411--422},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Basel},
      YEAR = {1995},
      MRCLASS = {11Y05 (11A51 11Y16)},
      MRNUMBER = {1403941},
      MRREVIEWER = {Oliver Schirokauer},
      ZBLNUMBER = {0854.11047},
      }
  • [pom2] C. Pomerance, "Multiplicative independence for random integers," in Analytic Number Theory, Vol. 2, Boston, MA: Birkhäuser, 1996, vol. 139, pp. 703-711.
    @incollection {pom2, MRKEY = {1409387},
      AUTHOR = {Pomerance, Carl},
      TITLE = {Multiplicative independence for random integers},
      BOOKTITLE = {Analytic Number Theory, {V}ol. 2},
      VENUE={{A}llerton {P}ark, {IL},
      1995},
      SERIES = {Progr. Math.},
      VOLUME = {139},
      PAGES = {703--711},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Boston, MA},
      YEAR = {1996},
      MRCLASS = {11Y16 (11N25 11Y05 68Q25)},
      MRNUMBER = {1409387},
      MRREVIEWER = {Joe P. Buhler},
      ZBLNUMBER = {0865.11085},
      }
  • [pom3] 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.
    @incollection {pom3, MRKEY = {2467543},
      AUTHOR = {Pomerance, Carl},
      TITLE = {Smooth numbers and the quadratic sieve},
      BOOKTITLE = {Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography},
      SERIES = {Math. Sci. Res. Inst. Publ.},
      VOLUME = {44},
      PAGES = {69--81},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2008},
      MRCLASS = {11Y05 (11-01 11N35 11Y16)},
      MRNUMBER = {2467543},
      MRREVIEWER = {Samuel S. Wagstaff, Jr.},
      ZBLNUMBER = {1188.11065},
      }
  • [silverman] Go to document R. D. Silverman, "The multiple polynomial quadratic sieve," Math. Comp., vol. 48, iss. 177, pp. 329-339, 1987.
    @article {silverman, MRKEY = {0866119},
      AUTHOR = {Silverman, Robert D.},
      TITLE = {The multiple polynomial quadratic sieve},
      JOURNAL = {Math. Comp.},
      FJOURNAL = {Mathematics of Computation},
      VOLUME = {48},
      YEAR = {1987},
      NUMBER = {177},
      PAGES = {329--339},
      ISSN = {0025-5718},
      CODEN = {MCMPAF},
      MRCLASS = {11Y05},
      MRNUMBER = {0866119},
      MRREVIEWER = {Torleiv Kløve},
      DOI = {10.2307/2007894},
      ZBLNUMBER = {0608.10004},
      }
  • [tenen] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge: Cambridge Univ. Press, 1995, vol. 46.
    @book {tenen, MRKEY = {1342300},
      AUTHOR = {Tenenbaum, G{é}rald},
      TITLE = {Introduction to Analytic and Probabilistic Number Theory},
      SERIES = {Cambridge Stud. Adv. Math.},
      VOLUME = {46},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1995},
      PAGES = {xvi+448},
      ISBN = {0-521-41261-7},
      MRCLASS = {11-02 (11Kxx 11Mxx 11Nxx)},
      MRNUMBER = {1342300},
      MRREVIEWER = {H. G. Diamond},
      ZBLNUMBER = {0880.11001},
      ZBLNUMBER = {0831.11001},
      }

Authors

Ernie Croot

School of Mathematics
Georgia Institute of Technology
686 Cherry Street
Atlanta, GA 30332-0160

Andrew Granville

Dépt. de mathématiques et de statistiques
Université de Montréal
CP 6128, succ. Centre-Ville
Montréal QC H3C 3J7
Canada

Robin Pemantle

Department of Mathematics
David Rittenhouse Laboratories
209 S. 33rd Street
University of Pennsylvania
Philadelphia, PA 19104-6395

Prasad Tetali

School of Mathematics
Georgia Institute of Technology
686 Cherry Street
Atlanta, GA 30332-0160