Bollobás, Béla
Making Squares  Sieves, Smooth Numbers, Cores and Random Xorsat (Keynote Speakers)
Abstract
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 nontrivial 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.
BibTeX  Entry
@InProceedings{bollobs:LIPIcs:2018:8896,
author = {B{\'e}la Bollob{\'a}s},
title = {{Making Squares  Sieves, Smooth Numbers, Cores and Random Xorsat (Keynote Speakers)}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {3:13:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770781},
ISSN = {18688969},
year = {2018},
volume = {110},
editor = {James Allen Fill and Mark Daniel Ward},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8896},
URN = {urn:nbn:de:0030drops88967},
doi = {10.4230/LIPIcs.AofA.2018.3},
annote = {Keywords: integer factorization, perfect square, random graph process}
}
18.06.2018
Keywords: 

integer factorization, perfect square, random graph process 
Seminar: 

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Issue date: 

2018 
Date of publication: 

18.06.2018 