Detecting squarefree numbers

Andrew R Booker; Ghaith Hiary; Jon P Keating

doi:10.1215/00127094-2856619

Detecting squarefree numbers

Andrew R Booker, Ghaith Hiary, Jon P Keating

Research output: Contribution to journal › Article (Academic Journal) › peer-review

9 Citations (Scopus)

401 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 language	English
Pages (from-to)	235-275
Number of pages	41
Journal	Duke Mathematical Journal
Volume	164
Issue number	2
DOIs	https://doi.org/10.1215/00127094-2856619
Publication status	Published - 30 Jan 2015

Keywords

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

Access to Document

10.1215/00127094-2856619Licence: Unspecified

BHKAccepted author manuscript, 642 KBLicence: Unspecified

Handle.net

Persistent link

Cite this

@article{4add2eaab89944e395917fff0159763d,

title = "Detecting squarefree numbers",

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.",

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

author = "Booker, {Andrew R} and Ghaith Hiary and Keating, {Jon P}",

year = "2015",

month = jan,

day = "30",

doi = "10.1215/00127094-2856619",

language = "English",

volume = "164",

pages = "235--275",

journal = "Duke Mathematical Journal",

issn = "0012-7094",

publisher = "Duke University Press",

number = "2",

}

TY - JOUR

T1 - Detecting squarefree numbers

AU - Booker, Andrew R

AU - Hiary, Ghaith

AU - Keating, Jon P

PY - 2015/1/30

Y1 - 2015/1/30

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

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

KW - 11Y16: Algorithms; complexity [See also 68Q25]

KW - 11M06: ζ(s) and L(s,χ)

KW - 11Y35: Analytic computations

KW - 11M50: Relations with random matrices

UR - http://www.scopus.com/inward/record.url?scp=84922545397&partnerID=8YFLogxK

U2 - 10.1215/00127094-2856619

DO - 10.1215/00127094-2856619

M3 - Article (Academic Journal)

AN - SCOPUS:84922545397

SN - 0012-7094

VL - 164

SP - 235

EP - 275

JO - Duke Mathematical Journal

JF - Duke Mathematical Journal

IS - 2

ER -

Detecting squarefree numbers

Abstract

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint