Detecting squarefree numbers

Andrew R Booker, Ghaith Hiary, Jon P Keating

Research output: Contribution to journalArticle (Academic Journal)peer-review

2 Citations (Scopus)
321 Downloads (Pure)

Abstract

We present an algorithm, based on the explicit formula for L-functions and conditional on the generalized Riemann hypothesis, for proving that a given integer is squarefree with little or no knowledge of its factorization. We analyze the algorithm both theoretically and practically and use it to prove that several RSA challenge numbers are not squarefull.

Original languageEnglish
Pages (from-to)235-275
Number of pages41
JournalDuke Mathematical Journal
Volume164
Issue number2
DOIs
Publication statusPublished - 30 Jan 2015

Keywords

  • 11Y16: Algorithms; complexity [See also 68Q25]
  • 11M06: ζ(s) and L(s,χ)
  • 11Y35: Analytic computations
  • 11M50: Relations with random matrices

Fingerprint Dive into the research topics of 'Detecting squarefree numbers'. Together they form a unique fingerprint.

Cite this