when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-88967
URL:

### Making Squares - Sieves, Smooth Numbers, Cores and Random Xorsat (Keynote Speakers)

 pdf-format:

### 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 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.

### 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:1--3:1},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-078-1},
ISSN =	{1868-8969},
year =	{2018},
volume =	{110},
editor =	{James Allen Fill and Mark Daniel Ward},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},