On sharp transitions in making squares

DOI10.4007/ANNALS.2012.175.3.10MaRDI QIDQ431647zbMATH OpenOpenAlexWikidataFDO

Authors Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali

Publication date 29 June 2012

Published in Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.0372

zbMATH Keywords

factorization algorithmrandom hypergraphsmooth numbersDixon's random squares algorithmsievingsmooth number estimatessquare product

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16)

Abstract: 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 ${\displaystyle }$[ (pi/4)(e^{-gamma} - o(1))J_0, (e^{-gamma} + o(1)) J_0],${\displaystyle }$ where $gamma=\mathrm{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.

Recommendations

• Running Time Predictions for Factoring Algorithms
• The sharp threshold for making squares
• scientific article; zbMATH DE number 849975
• A hyperelliptic smoothness test. I
• Generation of Elements with Small Modular Squares and Provably Fast Integer Factoring Algorithms

Cites work

• scientific article; zbMATH DE number 989379 (Why is no real title available?)
• scientific article; zbMATH DE number 3959521 (Why is no real title available?)
• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 475434 (Why is no real title available?)
• scientific article; zbMATH DE number 733561 (Why is no real title available?)
• scientific article; zbMATH DE number 849975 (Why is no real title available?)
• scientific article; zbMATH DE number 903721 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• Asymptotically Fast Factorization of Integers
• Dependent Sets of Constant Weight Binary Vectors
• Enumerative problems inspired by Mayer's theory of cluster integrals
• Large character sums
• On Integers Free of Large Prime Factors
• Running Time Predictions for Factoring Algorithms
• Sharp thresholds of graph properties, and the $k$-sat problem
• Smooth numbers and the quadratic sieve
• The Multiple Polynomial Quadratic Sieve

Cited in

(9)

• Small cores in 3-uniform hypergraphs
• scientific article; zbMATH DE number 849975 (Why is no real title available?)
• Orienteering with one endomorphism
• The Most Frequent Values of the Largest Prime Divisor Function
• Running Time Predictions for Factoring Algorithms
• Counting primitive subsets and other statistics of the divisor graph of \(\{1,2,\dots,n\}\)
• A problem of Erdős–Graham–Granville–Selfridge on integral points on hyperelliptic curves
• Rigorous analysis of a randomised number field sieve
• The sharp threshold for making squares

This page was built for publication: On sharp transitions in making squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q431647)