Smooth Orders and Cryptographic Applications

摘要

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, we show that for almost all primes p the multiplicative order of 2 modulo p is not smooth, and we prove a similar but weaker result for almost all odd numbers n. We also discuss some cryptographic applications.