FORTRAN 77 on PDP-11

Paul Koning wrote:

Depending on how deep you want to dig, if you like primes, you should get yourself some cryptography textbooks. A good primer, without a lot of serious math, is Bruce Schneier's "Applied Cryptography". If you want to understand the math in depth, get "Handbook of Applied Cryptography" (I think that's the correct title) by Menezes et al. I have both, though I'm stuck at around chapter 2 in the latter because the math goes beyond what I know. I think Knuth has a discussion of the M-R test -- surely you have Knuth, right? If not, you need to fix that. The M-R test is a "probabilistic primality test" -- a fast way of testing a number for being prime that has a certain probability of giving the wrong answer. You can do the test repeatedly, and if the tests are done right so they are independent, the test will become more and more accurate. This test is generally used in crypto programs because it is fast. There are also tests for primality that are exact rather than probabilistic -- those are MUCH slower. For multi-thousand-bit numbers, people use M-R unless they absolutely, positively require a guarantee of primality and can afford the hours or days of CPU time investment. An example: the Diffie-Hellman parameters for the IKE key exchange protocol (part of IPsec) were subjected to the full primality test, not just M-R.