Smooth Orders and Cryptographic Applications
01 January 2002
We obtain rigorous upper bounds on the number of primes p (= x for which p - 1 is smooth or has a large smooth factor. Conjecturally these bounds are nearly tight. As a corollary, for almost all primes p the multiplicative order of 2 modulo p is not smooth. We also discuss some cryptographic applications.