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 ≥ 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((1 + o(1))(ln n) 1/3  (ln ln n)  2/3 ) deterministic time.
['Bartosz Zralek']
A deterministic version of Pollard's p-1 algorithm