DROPS

Document

Keynote Speakers

DOI: 10.4230/LIPIcs.AofA.2018.3

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

Authors: Béla Bollobás

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

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.

Cite as

Béla Bollobás. Making Squares - Sieves, Smooth Numbers, Cores and Random Xorsat (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bollobas:LIPIcs.AofA.2018.3,
  author =	{Bollob\'{a}s, B\'{e}la},
  title =	{{Making Squares - Sieves, Smooth Numbers, Cores and Random Xorsat}},
  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 =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.3},
  URN =		{urn:nbn:de:0030-drops-88967},
  doi =		{10.4230/LIPIcs.AofA.2018.3},
  annote =	{Keywords: integer factorization, perfect square, random graph process}
}

Search Results

Documents authored by Bollobás, Béla

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

Abstract

Cite as

Thanks for your feedback!

Could not send message