Factoring with Hints

Francesco Sica

doi:10.1515/jmc-2020-0078

Factoring with Hints

Francesco Sica

Research output: Contribution to journal › Article › peer-review

Abstract

We introduce a new approach to (deterministic) integer factorisation, which could be describedin the cryptographically fashionable term of "factoring with hints": we prove that, for any 0 given the knowledge of the factorisations of O(N1/3) terms surrounding N = pq product of two large primes, we can recover deterministically p and q in O(N1/3) bit operations. This shows that the factorisations of close integers are non trivially related and that consequently one can expect more results along this line of thought.

Original language	English
Pages (from-to)	123-130
Number of pages	8
Journal	Journal of Mathematical Cryptology
Volume	15
Issue number	1
DOIs	https://doi.org/10.1515/jmc-2020-0078
Publication status	Published - Jan 1 2021

Keywords

complex analysis
factorisation of RSA moduli
Riemann zeta function

ASJC Scopus subject areas

Computer Science Applications
Computational Mathematics
Applied Mathematics

Access to Document

10.1515/jmc-2020-0078

Cite this

@article{bdb5b5d60a1643448eec986e9358f6b9,

title = "Factoring with Hints",

abstract = "We introduce a new approach to (deterministic) integer factorisation, which could be describedin the cryptographically fashionable term of {"}factoring with hints{"}: we prove that, for any 0 given the knowledge of the factorisations of O(N1/3) terms surrounding N = pq product of two large primes, we can recover deterministically p and q in O(N1/3) bit operations. This shows that the factorisations of close integers are non trivially related and that consequently one can expect more results along this line of thought.",

keywords = "complex analysis, factorisation of RSA moduli, Riemann zeta function",

author = "Francesco Sica",

note = "Funding Information: Research supported in part by a grant from the Social Development Fund. Publisher Copyright: {\textcopyright} 2020 F. Sica, published by De Gruyter.",

year = "2021",

month = jan,

day = "1",

doi = "10.1515/jmc-2020-0078",

language = "English",

volume = "15",

pages = "123--130",

journal = "Journal of Mathematical Cryptology",

issn = "1862-2976",

publisher = "Walter de Gruyter GmbH & Co. KG",

number = "1",

}

TY - JOUR

T1 - Factoring with Hints

AU - Sica, Francesco

PY - 2021/1/1

Y1 - 2021/1/1

N2 - We introduce a new approach to (deterministic) integer factorisation, which could be describedin the cryptographically fashionable term of "factoring with hints": we prove that, for any 0 given the knowledge of the factorisations of O(N1/3) terms surrounding N = pq product of two large primes, we can recover deterministically p and q in O(N1/3) bit operations. This shows that the factorisations of close integers are non trivially related and that consequently one can expect more results along this line of thought.

AB - We introduce a new approach to (deterministic) integer factorisation, which could be describedin the cryptographically fashionable term of "factoring with hints": we prove that, for any 0 given the knowledge of the factorisations of O(N1/3) terms surrounding N = pq product of two large primes, we can recover deterministically p and q in O(N1/3) bit operations. This shows that the factorisations of close integers are non trivially related and that consequently one can expect more results along this line of thought.

KW - complex analysis

KW - factorisation of RSA moduli

KW - Riemann zeta function

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

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

U2 - 10.1515/jmc-2020-0078

DO - 10.1515/jmc-2020-0078

M3 - Article

AN - SCOPUS:85097198253

SN - 1862-2976

VL - 15

SP - 123

EP - 130

JO - Journal of Mathematical Cryptology

JF - Journal of Mathematical Cryptology

IS - 1

ER -

Factoring with Hints

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this