License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.3
URN: urn:nbn:de:0030-drops-88967
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8896/
Go to the corresponding LIPIcs Volume Portal

Bollobás, Béla

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

pdf-format:
LIPIcs-AofA-2018-3.pdf (0.2 MB)

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},
  address =	{Dagstuhl, Germany},
  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 Published by LZI