The Role of Smooth Numbers in Number Theoretic Algorithms
Carl B. Pomerance · Birkhäuser Basel eBooks · 1995
A smooth number is a number with only small prime factors. In particular, a positive integer is y-smooth if it has no prime factor exceeding y . Smooth numbers are a useful tool in number theory because they not only have a simple multiplicative structure, but are also fairly numerous. These twin properties of smooth numbers are the main reason they play a key role in almost every moder integer factorization algorithm. Smooth numbers play a similar essential role in discrete logarithm algorithms (methods to represent some group element as a power of another), and a lesser, but still important, role in primality tests.