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

作者：Durnoga Konrad; Pomykala Jacek^*

来源：Fundamenta Informaticae, 2017, 156(2): 179-185.

DOI：10.3233/FI-2017-1603

• large sieve
• factoring algorithms
• Z*(n)-generating sets
• Dirichlet characters
• smooth numbers
• Discrete Logarithm Problem for Composite Numbers

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 phi under the Extended Riemann Hypothesis. We show, unconditionally, that such a deterministic polynomial reduction exists for a large class of integers.

• 出版日期2017