Integer factoring and compositeness witnesses (Q2023317)

An increasingly popular approach to the integer factorization problem is the study of its relations to other difficult tasks in algorithmic number theory. One such example is the computation of Euler's totient function \(\varphi\). It is a well-known open problem to find an unconditional, deterministic, polynomial-time algorithm for factoring \(N\in\mathbb{N}\) under the assumption that \(\varphi(N)\) is known. In this context, the authors present several reductions from integer factoring to problems related to \(\varphi\), such as computing \(\varphi(N)\), multiples of \(\varphi(N)\), the factorization of \(\varphi(N)\) or a small number of iterates of \(\varphi\). All these reductions are unconditional, deterministic and polynomial-time, but fail for certain inputs, the so-called ``hard'' integers. While results of this type have already been known, the contribution of the present paper is the improvement of the upper bounds for the number of hard integers. The core idea is based on the notions of Fermat-Euclid witnesses and Power-Difference witnesses. In short, such witnesses \(w\in\mathbb{Z}_N^*\) allow to compute a proper factor of \(N\) via certain GCD expressions that require knowledge of \(\varphi(N)\). The authors show that either there is such a witness up to a small bound \(B\), or certain primitive Dirichlet characters with large least character nonresidue exist. Subsequently, they establish the results stated in the abstract by exploiting already known bounds for least character nonresidues. Further refinements are achieved by assuming knowledge of the factorization of \(\varphi(N)\). Finally, a hybrid approach using at most \(\log N\) iterations of \(\varphi\) is presented. As pointed out in the last section of the paper, some of the algorithms also work if only a multiple of \(\varphi(N)\) is known. In any case, the paper is an interesting contribution to this research area, and a valuable investigation of compositeness witnesses and the properties of hard numbers.