Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A deterministic version of Pollard's $ p-1$ algorithm

Author: Bartosz Zrałek
Journal: Math. Comp. 79 (2010), 513-533
MSC (2000): Primary 11Y16; Secondary 11Y05, 68Q10
Published electronically: May 6, 2009
MathSciNet review: 2552238
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this article we present applications of smooth numbers to the unconditional derandomization of some well-known integer factoring algo- rithms.

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 ($ k\ge 2$) devised by Bach and Shallit.

We also investigate reductions of factoring to computing Euler's totient function $ \varphi$. We point out some explicit sets of integers $ n$ that are completely factorable in deterministic polynomial time given $ \varphi(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(\ln n)$ oracle queries for values of $ \varphi$ are sufficient to completely factor any integer $ n$ in less than $ \exp\Bigl((1+o(1))(\ln n)^{\frac{1}{3}} (\ln\ln n)^{\frac{2}{3}}\Bigr)$ deterministic time.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11Y05, 68Q10

Retrieve articles in all journals with MSC (2000): 11Y16, 11Y05, 68Q10

Additional Information

Bartosz Zrałek
Affiliation: Institute of Mathematics, Polish Academy of Sciences, 00-956 Warsaw, Poland

Keywords: Pollard's $p-1$ method, derandomization, Euler's $\varphi $-function and factorization
Received by editor(s): November 26, 2007
Received by editor(s) in revised form: October 3, 2008, and January 1, 2009
Published electronically: May 6, 2009
Article copyright: © Copyright 2009 American Mathematical Society