Sharp Transitions in Making Squares

Details Sharp Transitions in Making Squares Sharp Transitions in Making Squares

2008-11-03

arxiv.org/abs/0811.0372v1

Mathematics

Number Theory

Scientific paper

In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to rapidly determine a subsequence whose product is a square (which we call a square product). In his lecture at the 1994 International Congress of Mathematicians, Pomerance observed that the following 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 has product equal to a square. Find good estimate for the expected stopping time of this process. A good solution to this problem should help one to determine the optimal choice of parameters for one's factoring algorithm, and therefore this is a central question. 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). Herein we determine this expected stopping time up to a constant factor, tightening 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. We will also confirm the well established belief that, typically, none of the integers in the square product have large prime factors. We believe the upper of the two bounds to be asymptotically sharp.

Affiliated with

Also associated with

No associations

Rating

Sharp Transitions in Making Squares does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp Transitions in Making Squares, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp Transitions in Making Squares will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-234470