Assignment 14

Section 6.4 finally reached a topic that has been repeatedly brought up in class throughout the quarter: factoring numbers into primes. The methods in this section illustrate some of the attempts to find factorization techniques aside from the extremely slow method of dividing a number n by all primes up to n. These method's include Fermat's method as an older and slower method (originally this method was difficult to understand because it was ambiguous as to whether or not the B! represented a factorial or some other variable, even with the acceptence that it represents a factorial, the reasoning behind it is not adequately proven in the book). Factoring by methods in section 6.3 including the Miller-Rabin test and finally the Universal Exponent factorization model.

The most interesting piece of information in my mind was throughout the reading there were phrases such as "sometimes this allows us to factor n" and "if _____ are found by some reasonable method then there is a chance this will work." These phrases represent the fundamental problem faced by cryptographers and number theorists alike, namely factoring is slow and difficult to do and no one has yet come up with a solution to the problem. Perhaps quantum computing will provide an answer...