2026-08-20T01:45:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8896 2024-03-06T10:43:41Z ddc:004 open_access

Making Squares - Sieves, Smooth Numbers, Cores and Random Xorsat (Keynote Speakers) Bollobás, Béla integer factorization perfect square random graph process Since the advent of fast computers, much attention has been paid to practical factoring algorithms. Several of these algorithms set out to find two squares x^2, y^2 that are congruent modulo the number n we wish to factor, and are non-trivial in the sense that x is not equivalent to +/- y mod n. In 1994, this prompted Pomerance to ask the following question. Let a_1, a_2, ... be random integers, chosen independently and uniformly from a set {1, ... x}. Let N be the smallest index such that {a_1, ... , a_N} contains a subsequence, the product of whose elements is a perfect square. What can you say about this random number N? In particular, give bounds N_0 and N_1 such that P(N_0 <= N <= N_1)-> 1 as x -> infty. Pomerance also gave bounds N_0 and N_1 with log N_0 ~ log N_1. In 2012, Croot, Granville, Pemantle and Tetali significantly improved these bounds of Pomerance, bringing them within a constant of each other, and conjectured that their upper bound is sharp. In a recent paper, Paul Balister, Rob Morris and I have proved this conjecture. In the talk I shall review some related results and sketch some of the ideas used in our proof. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Béla Bollobás 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.3 urn:nbn:de:0030-drops-88967 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode