Factoring with Hints

Research output: Contribution to journalArticlepeer-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 languageEnglish
Pages (from-to)123-130
Number of pages8
JournalJournal of Mathematical Cryptology
Volume15
Issue number1
DOIs
Publication statusPublished - Jan 1 2021

Keywords

  • complex analysis
  • factorisation of RSA moduli
  • Riemann zeta function

ASJC Scopus subject areas

  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Factoring with Hints'. Together they form a unique fingerprint.

Cite this