Integer factoring and compositeness witnesses

Journal of mathematical cryptology

article

Jacek Pomykała¹  Maciej Radziejewski² 

[1] Faculty of Mathematics, University of Warsawul.Banacha 2;Faculty of Mathematics and Computer Science, Adam Mickiewicz Universityul.Umultowska 87

关键词: Large sieve;    factoring algorithms;    Zn*-generating sets;    Dirichlet characters;    smooth numbers;    Discrete Logarithm Problem for composite numbers;    primality testing;    Euler’s totient function;    RSA;   

DOI  :  10.1515/jmc-2019-0023

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

We describe a reduction of the problem of factorization of integers n ≤ x in polynomial-time (log x ) M + O (1) to computing Euler’s totient function, with exceptions of at most x O (1/ M ) composite integers that cannot be factored at all, and at most x exp − cM(loglog⁡ x)3(logloglog⁡ x)2$\begin{array}{} \displaystyle \left(-\frac{c_M(\log\log x)^3}{(\log\log\log x)^2}\right) \end{array}$ integers that cannot be factored completely. The problem of factoring square-free integers n is similarly reduced to that of computing a multiple D of ϕ ( n ), where D ≪ exp((log x ) O (1) ), with the exception of at most x O (1/ M ) integers that cannot be factored at all, in particular O ( x 1/ M ) integers of the form n = pq that cannot be factored.

【 授权许可】

CC BY|CC BY-NC-ND