Add brief section on RSA. Describe new prime-search system.

diff --git a/README.mp b/README.mp
index a70e08d..bc75817 100644 (file)
--- a/README.mp
+++ b/README.mp
@@ -304,53 +304,34 @@ Modular multiplication and exponentiation
        out of their way to make it easy for you by choosing a very
        small public exponent.)
 
+       RSA decryption is fully covered by the library, because doing it
+       properly is complicated and difficult since it involves playing
+       with blinding factors and the Chinese Remainder Theorem.
+
+       (There's also a useful RSA parameter recovery system which can
+       determine all the useful bits of information for efficient RSA
+       decryption given a very small amount of information.  For
+       example, given the modulus and both exponents, it can recover
+       the two secret factors.  This is, by the way, a good reason not
+       to share a modulus among many users.)
+
 
 Finding prime numbers
 
        Prime numbers are important too.  Finding them is not ever-so
-       easy.
+       easy.  THere's a huge variety of useful properties which are
+       needed, and it's basically impossible to cover everything.
 
        Catacomb has two useful facilities.  There's a fast sequential-
-       search filtering system called `pgen', and a good (but
+       search filtering system called `pfilt, and a good (but
        probabilistic) primality tester which implements the Rabin-
        Miller test.
 
-       The idea is that you initialize a pgen object with a starting
-       place.  It spends a short time initializing itself, and then
-       tells you whether the number you gave it is (a) definitely
-       composite, (b) definitely prime (only for small numbers), or (c)
-       it doesn't know.  The advantage of the pgen system is that it's
-       good at stepping regularly.  You can advance it by 2 or 4 very
-       rapidly, and it will give you the same sort of answer for the
-       next number.
-
-       When you find a number which pgen says it doesn't know about,
-       you must test it more thoroughly.  This is time-consuming, but
-       pgen has weeded out many no-hopers so it's not so bad.
-
-       The Rabin-Miller test takes a number to test, and stores it in a
-       context.  You then give it some random numbers, and it gives you
-       results.  When you've finished, you destroy the context.
-
-       The Rabin-Miller test has two possible responses: (a) definitely
-       not prime, and (b) probably prime.  Answer (a) is certain.
-       Answer (b) you may get with a composite number at most one time
-       in four.  If you try n times, the probability of a composite
-       number going unnoticed is at most one in 4^n.  In fact, the real
-       probability is *much* lower than this.
-
-       It's also important to bear in mind that this is examining the
-       probability that a number passes n Rabin-Miller tests given
-       that it's composite.  What's actually interesting the the
-       probability that a number is composite given that it passed n
-       tests.  This probability is lower still.  For 1024-bit numbers,
-       which are about the right size by current standards of security,
-       you need only five tests to ensure a probability of less than 1
-       in 2^80 of a composite number slipping through.
-
-       There are specialized functions for finding various sorts of
-       prime numbers with particular properties.  Read the header files
-       to find out what they do.
+       Over the top of this is a confgurable plug-in-appropriate-bits
+       system called `pgen' which tied everything together.  You're
+       much better off using `pgen' than grovelling about with the
+       filter and Rabin-Miller tests by hand.  The low-level details
+       are much better used to create new `pgen' components.
 
 
 Conclusion