Integer factoring and compositeness witnesses
type: Item
instance of: scholarly article
title: Integer factoring and compositeness witnesses
zbMATH Open document ID: 1468.11244
author: Jacek Pomykała
author: Maciej Radziejewski
published in: Journal of Mathematical Cryptology
publication date: 2021-05-03T00:00:00Z
review text: 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…
reviewed by: Markus Hittmeir
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 11Y11
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 7342057
zbMATH Keywords: large sieve
zbMATH Keywords: factoring algorithms
zbMATH Keywords: \(Z_n^*\)-generating sets
zbMATH Keywords: Dirichlet characters
zbMATH Keywords: smooth numbers
zbMATH Keywords: discrete logarithm problem for composite numbers
zbMATH Keywords: primality testing
zbMATH Keywords: Euler's totient function
zbMATH Keywords: RSA
MaRDI profile type: Publication
full work available at URL: jmc-2019-0023
OpenAlex ID: W3080573067
cites work: Q4847943
cites work: The least quadratic non residue
cites work: ON THE LEAST n WITH χ(n) ≠ 1
cites work: Q5317673
cites work: Large Sieve, Miller-Rabin Compositeness Witnesses and Integer Factoring Problem
cites work: The number of solutions of \(\varphi (x)=m\)
cites work: Q2785582
cites work: Some remarks on computing the square parts of integers
cites work: ON THE LEAST QUADRATIC NON-RESIDUE
cites work: Riemann's hypothesis and tests for primality
cites work: On reducing factorization to the discrete logarithm problem modulo a composite
cites work: Probabilistic algorithm for testing primality
cites work: Fast multiplication of large numbers
cites work: Q5500818
cites work: A deterministic version of Pollard’s $p-1$ algorithm
DOI: 10.1515/JMC-2019-0023
description: scientific article; zbMATH DE number 7342057