| > This section describes two methods for checking the primality of an integer n, one with order of growth Theta(sqrt(n)), and a 'probabilistic' algorithm with order of growth Theta(log n). The book explains order of growth a few pages before this example, so the only assumed knowledge here is what a prime number is, which seems very reasonable. > Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n. That's the concise definition of Fermat's Little theorem, that he then proceeds to explain in detail. Again, not presupposed knowledge, but something new to learn. He explains congruent modulo, so you are expected to know what prime numbers are, and what positive integers are. Again, CS books from MIT are not for you if you don't know those two things. > When we first introduced the square-root procedure, in section 1.1.7, we mentioned that this was a special case of Newton's method. If x -> g(x) is a differentiable function, then a solution of the equation g(x) = 0 is a fixed point of the function x -> f(x) where [complex formula] and Dg(x) is the derivative of g evaluated at x. This one assumes that you understand the material from section 1.1.7. I think you've succeeded in making a case for reading the book and completing the exercises in order, but not that it places unreasonable expectations on its reader. |