Integer factoring and compositeness witnesses
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.
- Large sieve, Miller-Rabin compositeness witnesses and integer factoring problem
- Reductions among number theoretic problems
- On deterministic reduction of factoring integers to computing the exponents of elements in modular group
- An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient
- A deterministic version of Pollard's p-1 algorithm
- A deterministic version of Pollard's p-1 algorithm
- Fast multiplication of large numbers
- scientific article; zbMATH DE number 981695 (Why is no real title available?)
- scientific article; zbMATH DE number 799791 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- Introduction to analytic and probabilistic number theory. Transl. from the 3rd French edition by Patrick D. F. Ion
- Large sieve, Miller-Rabin compositeness witnesses and integer factoring problem
- On reducing factorization to the discrete logarithm problem modulo a composite
- ON THE LEAST n WITH χ(n) ≠ 1
- ON THE LEAST QUADRATIC NON-RESIDUE
- Probabilistic algorithm for testing primality
- Riemann's hypothesis and tests for primality
- Some remarks on computing the square parts of integers
- The least quadratic non residue
- The number of solutions of \(\varphi (x)=m\)
- On oracle factoring of integers
- Integer factorization and twin primes verification algorithms
- On deterministic reduction of factoring integers to computing the exponents of elements in modular group
- Large sieve, Miller-Rabin compositeness witnesses and integer factoring problem
- A reduction of integer factorization to modular tetration
- Elliptic-curve factoring, witnesses and oracles
- Integer factoring and modular square roots
This page was built for publication: Integer factoring and compositeness witnesses
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2023317)
