Sharp Transitions in Making Squares - Mathematics > Number TheoryReport as inadecuate

Sharp Transitions in Making Squares - Mathematics > Number Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: In many integer factoring algorithms, one produces a sequence of integerscreated in a pseudo-random way, and wishes to rapidly determine a subsequencewhose product is a square which we call a square product. In his lecture atthe 1994 International Congress of Mathematicians, Pomerance observed that thefollowing problem encapsulates all of the key issues: Select integers a 1, a 2,>

. at random from the interval 1,x, until some non-empty subsequence hasproduct equal to a square. Find good estimate for the expected stopping time ofthis process. A good solution to this problem should help one to determine theoptimal choice of parameters for one-s factoring algorithm, and therefore thisis a central question.Pomerance 1994, using an idea of Schroeppel 1985, showed that withprobability 1-o1 the first subsequence whose product equals a square occursafter at least J 0^{1-o1} integers have been selected, but no more than J 0,for an appropriate explicitly determined J 0=J 0x. Herein we determine thisexpected stopping time up to a constant factor, tightening Pomerance-s intervalto $$ \pi-4e^{-\gamma} - o1J 0, e^{-\gamma} + o1 J 0,$$ where$\gamma = 0.577

.$ is the Euler-Mascheroni constant. We will also confirm thewell established belief that, typically, none of the integers in the squareproduct have large prime factors. We believe the upper of the two bounds to beasymptotically sharp.

Author: Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali


Related documents