A deterministic version of Pollard’s $p-1$ algorithm
A deterministic version of Pollard’s $p-1$ algorithm
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 …