Large Sieve,Miller-Rabin Compositeness Witnesses and Integer Factoring Problem

Abstract

G. Miller in his seminal paper from the mid 1970s has proven that the problem of factoring integers reduces to computing Euler’s totient function φ under the Extended Riemann Hypothesis. We show, unconditionally, that such a deterministic polynomial reduction exists for a large class of integers.