On the Abundance of Large Primes with Small B-smooth values for p-1: An Aspect of Integer Factorization

— The security of RSA public key cryptography and RSA digital signature relies on the assumption of the hardness of the factorization of integers. Since the inception of RSA, there have been a series of proposals for factorizing large integers. A handful of integer factorization methods rely on the fact that the prime factor (cid:1816) having smooth p -1 value. Pollard’s p -1 is a method heavily based on this fact. It takes sub-exponential time for certain integers though not suitable for all integers. This paper experiments on the abundance (or scarcity) of smooth p -1 for large primes by examining their availability and suitability.