**Prime Numbers:**

Because we need prime numbers
for encryption, we also need an efficient algorithm to test the primality of
some candidate number, *n*. The algorithm we used is the Miller-Rabin
Pseudoprime Test.

Using pseudoprimes (composites
that appear to be primes) as *p, q *could
allow multiple decryptions of incoming messages, as the mapping from message to
encrypted data and back would not be one-to-one. Therefore it is imperative that we identify pseudoprimes.

A
strong pseudoprime to a base *b *is an
odd composite *n* with _{}* *(for *d*
odd) for which *either*:

_{}

*or*

* *

_{}

for
some *r = *0, 1, 2, …, *. The algorithm
to test for these strong pseudoprimes is as follows for some potential prime **n *and base* b*:

1. Find *d *and
*s *as above, and randomly choose *b*, .

2. Test _{}. If this is true, *n *is either prime or a strong

pseudoprime to the base *b.* Randomly choose next base, repeat. If this is false, go to the next step.

3. If _{}, and *d < s*,
then *n* is either prime or a strong

pseudoprime to the base *b*.
Otherwise, let d be doubled and repeat

step 3.
If _{}, *n* is definitely
composite.

The
potential problem with this method is knowing when to stop testing. It is known that a pseudoprime will pass
this test for at most one fourth of all bases less than itself, but we can do
better. If we restrict our domain of
bases to prime numbers less than the candidate, the test becomes much more
efficient. Repeating the strong
pseudoprime test for *b* = 2, 3, 5
correctly identifies all primes below _{}with only 13 exceptions, and if 7 is added, then the only
exception less than _{}is 315,031,751. Jaeschke (1993) showed that there are only 101
strong pseudoprimes for the bases 2, 3, and 5 less than 10^{12}, nine
if 7 is added, and none if 11 is added.
Therefore, if we restrict our set of primes to be {2, 3, 5, 7, 11}, we
can positively identify all primes below 10^{12}.

Because
we are dealing mainly with 32-bit integers (~10^{10}), the set above is
easily sufficient to allow us to catch all pseudoprimes in our range.

Sources:

http://mathworld.wolfram.com/StrongPseudoprime.html