3 ms·

To add: not only you test for primality, but also for common attacks. Not all primes are equally strong http://www.uow.edu.au/~jennie/WEB/WEB99/1999_07.pdf http

• rdl 13y ago
  Plus technically e could be random (PGP used to do this, now ~everyone uses a fixed value as far as I know).
• pbsd 13y ago
  For primes of current acceptable size (>= 1024 bits), you might as well drop those extra checks. The elliptic curve method gives you around 2^512 attempts at doing the exact same thing, each one with the same probability of having a smooth p-1 or p+1. The paper you link to reaches essentially the same conclusion.