A deterministic version of Pollard's p-1 algorithm

DOI10.1090/S0025-5718-09-02262-5MaRDI QIDQ3584788zbMATH OpenFDO

Authors Bartosz Źrałek

Publication date 30 August 2010

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.4102

zbMATH Keywords

derandomizationEuler's \(\varphi \)-function and factorizationPollard's \(p-1\) method

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: In this article we present applications of smooth numbers to the unconditional derandomization of some well-known integer factoring algorithms. We begin with Pollard's $p-1$ algorithm, which finds in random polynomial time the prime divisors $p$ of an integer $n$ such that $p-1$ is smooth. We show that these prime factors can be recovered in deterministic polynomial time. We further generalize this result to give a partial derandomization of the $k$-th cyclotomic method of factoring ($kge2$) devised by Bach and Shallit. We also investigate reductions of factoring to computing Euler's totient function $phi$. We point out some explicit sets of integers $n$ that are completely factorable in deterministic polynomial time given $phi(n)$. These sets consist, roughly speaking, of products of primes $p$ satisfying, with the exception of at most two, certain conditions somewhat weaker than the smoothness of $p-1$. Finally, we prove that $O(lnn)$ oracle queries for values of $phi$ are sufficient to completely factor any integer $n$ in less than $expBigl((1+o(1))(lnn{)}^{1/3}(lnlnn{)}^{2/3}Bigr)$ deterministic time.

Recommendations

• Using partial smoothness of p-1 for factoring polynomials modulo p
• Deterministic integer factorization with oracles for Euler's totient function
• A deterministic algorithm for integer factorization
• scientific article; zbMATH DE number 503356
• An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• A p + 1 Method of Factoring
• An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
• Divisors in residue classes, constructively
• Explicit Bounds for Primality Testing and Related Problems
• Factoring integers with elliptic curves
• Factoring polynomials with rational coefficients
• Factoring with Cyclotomic Polynomials
• scientific article; zbMATH DE number 981695 (Why is no real title available?)
• scientific article; zbMATH DE number 3910466 (Why is no real title available?)
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• scientific article; zbMATH DE number 3801620 (Why is no real title available?)
• scientific article; zbMATH DE number 799791 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 3265895 (Why is no real title available?)
• On a problem of Oppenheim concerning Factorisatio Numerorum
• PRIMES is in P
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality
• Self-witnessing polynomial-time complexity and prime factorization
• Some remarks on computing the square parts of integers
• Some results on computational complexity
• Sums of Divisors, Perfect Numbers and Factoring
• The average least witness is 2
• Using partial smoothness of p-1 for factoring polynomials modulo p

Cited in

(9)

• Integer factoring and compositeness witnesses
• Using partial smoothness of p-1 for factoring polynomials modulo p
• On reducing factorization to the discrete logarithm problem modulo a composite
• An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient
• scientific article; zbMATH DE number 849975 (Why is no real title available?)
• Deterministic integer factorization with oracles for Euler's totient function
• New Characterization of the Factor Refinement Algorithm with Applications
• Deterministic factoring with oracles
• Elliptic-curve factoring, witnesses and oracles

This page was built for publication: A deterministic version of Pollard's \(p-1\) algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3584788)