When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.3
URN: urn:nbn:de:0030-drops-88967
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8896/
 Go to the corresponding LIPIcs Volume Portal

### 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},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8896},
URN =		{urn:nbn:de:0030-drops-88967},
doi =		{10.4230/LIPIcs.AofA.2018.3},
annote =	{Keywords: integer factorization, perfect square, random graph process}
}
```

 Keywords: integer factorization, perfect square, random graph process Collection: 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

DROPS-Home | Fulltext Search | Imprint | Privacy