Assignment 12

Section 6.3 contained a few interesting theorems for testing whether or not a number is prime. The basic principle and Fermat's primality test were fairly simple and it was easy (given previous reading in chapter three) to see how each test determines the compositeness of a number (that it is composed of multiple prime factors) even without finding the prime factors of the number. The Miller-Rabin Primality test, however, was thoroughly confusing and, even after multiple reads, my imagination could not grasp why it works or doesn't work for deterimining the compositeness of a number other than it is based on the basic principle and fermat's primality test. Not only is the test long but a proof is not shown which may mean that the number theory behind it is not necessary for the course and that it should just be accepted as sound. Similarly, the Solovay-Strassen primality test was not formally prooved but is quite easier to grasp.

This section underlines the importance of primes in cryptology, and more generally, in number theory. When I was first introduced to the fundamental theorem of arithmetic, that every number is composed of one or more primes, it struck me as a novel concept that such an apparently abstract fact could be so "fundamental." After the little number theory we've learned and the extensive applications in cryptography, prime numbers are arguably the most important aspect of numbers universally speaking. What this section also indicates is the difficulty in determining whether or not a number is actually prime without trying all possible factors. All tests given in the section are sufficient for determining whether a number is composite or namely, not prime, but none were able to prove conclusively that a number is prime. This fact then closely ties probability to number theory and can only result in even more interesting results.