Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

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
Email: b.zralek@impan.gov.pl

DOI: http://dx.doi.org/10.1090/S0025-5718-09-02262-5
PII: S 0025-5718(09)02262-5
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