Factoring with Hints

Abstract

We introduce a new approach to (deterministic) integer factorisation, which could be described in 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

• riemann zeta function
• factorisation of rsa moduli
• complex analysis
• 11m06
• 94a60