Finding Four Million Large Random Primes

A number n is a (base two) pseudoprime if it is composite and satisfies the identity 1$$ 2^{n - 1} \equiv 1\left( {\bmod n} \right). $$ Every prime satisifies (1), but very few composite numbers are pseudoprimes. If pseu- doprimes are very raTe, then one could even find large “industrial strength” primes (say for cryptographic use) by simply choosing large random values for n until an n is found that satisfies (1). H ow rare are pseudoprimes? We performed an experiment that attempts to provide an answer. We also provide some references to the literature for theoretical analyses.