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(N 1/3+ϵ ) terms surrounding N = pq product of two large primes, we can recover deterministically p and q in O(N 1/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.