Section 5.4.2

Difficult: I have done these encryptions a lot, so nothing was difficult. I work in the security lab, so cryptography is becoming second nature.

Reflective: It is interesting that we don't make use of an NP-Hard problem for encryption. It isn't even NP-Complete, and could possible live in P. It is interesting that we are depending so much on something we think is hard, but not provably so.

Section 5.4-5.4.1

Difficult: Nothing, I have seen this material before in Math 485.

Reflective: I think it is interesting that they say cryptography is broken up between classical encryption and public key encryption, while completely ignoring symmetric key encryption. Unlike their definition of classical encryption, the algorithm itself can be known, and the security, just as in public key cryptography, is in the key.

Section 5.3.2

Difficult: I feel that I understand each individual equation, but I am having a hard time filling out a complete mental picture of the proof. I don't really know where the disconnect is though.

Reflective: I don't really get why we care so much about Mersenne primes. What applications do they have, besides being huge. I wonder because it seems like we spend a lot of time looking for them, but I havn't heard why we need them.

Section 5.3.1

Difficult: I think I understood the material pretty well. The hardest part was during the proof of the correctness of the Solovay-Strassen primality test. It really wasn't that bad, but did have a lot of parts.

Reflective: It is interesting how reliable these probabilistic tests are. It is trivial to test a large number of paces, and come with a very tight bound on the error. It is also interesting that even deterministic algorithms have error, due to problems with hardware, and so at some point might really not be that much more reliable.

Section 5.3

Difficult: There wasn't much difficult, especially since the proof for AKS was omitted. I don't understand how they come to the calculation on the bounds, especially since one of the checks is that r is prime, which can only be cone in a recursive manner by running this algorithm on r as well, but maybe I am missing something.

Reflective: I think it is very interesting that their is a polynomial bounded algrotihm for determining whether a number is prime or not. It makes me wonder if factoring actually lives in P and not only in NP.

Section 5.1-5.2

Difficult: Overall the section was pretty easy. I did struggle with the proof of Theorem 5.2.1, but I think that I understand it now. The rest is familiar material.

Reflective: This was a walk down memory lane. I hadn't thought about sieving methods in a while, as I already know the probabilistic methods. I am interested in studying the deterministic polynomial method if we have time.

Exam 2 Prep

Theorems: Proofs of the infinitude of primes. Binet formula. Fermat's Two-Square theorem. Dirichlet's theorem. The multiplicative function theorems. Chebychev's estimate proof.

What kind of questions: I expect to see proofs about primes, their infinitude and form. Fib. numbers. Binomials. Problems dealing with the number of primes less than x.

Better understand: I feel most unsure about what for the questions will take. Going over that would be very helpful. Other than that if you could show problem 3.13 from the book, that is the one homework problem I still have no clue about the solution.

Rest of the semester: I would be interested in any parts of number theory that could be applied to cryptography, and most especially experimental cryptography (aka, not just AES, eliptic curves, RSA, etc.). Maybe stuff dealing with fully homomorphic encryption.

Rest of Section 4.2

Difficult: I had a little bit of a hard time following all of the powers, but other than that it all pretty much made sense. It mostly just seems to follow allong the same path os we took today in class.

Reflective: I think it is interesting that for all n their is a prime between n and 2n. I guess it shouldn't be that surprising, but it is cool to see how while the primes are sparse, they aren't that sparse.

Section 4.2 to Page 144

Difficult: I got pretty much the entire section. I don't understand the equality of pg.139, but I'm sure I'll get the luck of proving it on the HW :) Other than this it makes sense.

Reflective: I am interested to see big O and little O notation in this book. I have only seen it used in computer science, so it is interesting to see it one of my math courses. I guess I have seen it in Computability and Complexity Theory, which is also a very mathy course, but still it was interesting.

Section 4.1 - 4.2

Difficult: This section was pretty simple. I had read this first part of the chapter earlier in the semester, and so it all makes pretty good sense. The binomial parts we already went over in class.

Reflective: I think the approximation of n! is very interesting. It is crazy how we can get so many approximations so that we don't need summation or multiplication over a set of numbers.