A deterministic version of Pollard's p-1 algorithm
| dc.creator | Zralek, Bartosz | |
| dc.date | 2007-07-27 | |
| dc.date | 2009-05-12 | |
| dc.date.accessioned | 2026-07-07T13:13:14Z | |
| dc.date.available | 2026-07-07T13:13:14Z | |
| dc.description | 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 ($k\ge 2$) devised by Bach and Shallit. We also investigate reductions of factoring to computing Euler's totient function $ϕ$. We point out some explicit sets of integers $n$ that are completely factorable in deterministic polynomial time given $ϕ(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 $ϕ$ are sufficient to completely factor any integer $n$ in less than $\exp\Bigl((1+o(1))(\ln n)^{1/3} (\ln\ln n)^{2/3}\Bigr)$ deterministic time. | |
| dc.description | Expanded and heavily revised version, to appear in Mathematics of Computation, 21 pages | |
| dc.identifier | https://arxiv.org/abs/0707.4102 | |
| dc.identifier | http://arxiv.org/abs/0707.4102 | |
| dc.identifier | doi:10.1090/S0025-5718-09-02262-5 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/229821 | |
| dc.subject | Number Theory | |
| dc.subject | 11Y16 (Primary); 11Y05, 68Q10 (Secondary) | |
| dc.title | A deterministic version of Pollard's p-1 algorithm | |
| dc.type | text |