Section 6.3, due Wednesday October 20

1. (Difficulty) The Miller-Rabin Primiality Test was the most confusing test that was discussed in the section. I understood the steps, but how does the result conclude if the number is prime or not?More examples in class would be wonderful. Also what is the difference between strong pseudoprimes and just pseudoprimes?

2. (Reflective) It is interesting that there are many tests that guarantee that a number is composite, but for a long time there were not tests that could guarantee primality. It still takes some work, it seems, with the new algorithm by Agrawal, Kayal, and Saxena to discover a number is a prime. Are there any other known tests that guarantee primality? It seems like there will/would be more tests soon.