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 1012, 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 1012.

 

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

 

Sources:

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