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.