Section 6.3, Due October 20

Difficult: I do not understand how this fits in with what we have discussed about RSA so far. It seems that you can use the Miller-Rabin method to "break" RSA pretty readily, since n is definitely composite. Choosing a random number a, it seems that chances are high you would then be able to follow the procedure in the example on page 178 to find one of the primes p or q, and then use that knowledge to find the other. So is RSA not secure after all? I didn't fully understand the discussion of why the test works on page 179, but I think I might after reading it a few more times. It is just hard to follow.

Reflective: I didn't realize how easy it was to find primes. I recognize that neither of these tests prove primality for a number, but they seem to give a pretty sure bet. I notice that they mention strong pseudoprimes for multiple bases, in fact there is even one for all bases that are primes less than 200. Is this psuedoprime also good for nonprime bases less than 200? The statistics are given for the possibility of a number being a psuedoprime for some chosen base, and I'm not well versed in statistics, but it seems to me that picking more than one base to check and making sure some are prime and some are composite will raise the possibility of discovering if the number you are testing is a composite or not by a great deal.