Difficult: Nothing, it all made sense. The elliptic curve math is simple, and I am already very familiar with DH and ElGamal.

Reflective: I was sad to see no discussion of message encryption with elliptic curves. It is also sad to just see extensions to known methods that have man-in-the-middle attacks.

Exam Prep:
Important: Math in Z_p, Proofs about the infinitude of primes, how to factor primes, multiplicative functions, characters, encryption, and elliptic curve point addition.

Questions: Pretty much what we have seen so far, but with a focus on encryption.

Understand: There is nothing I actually feel that week on. The biggest problems I have had on the tests to date has been a lack of exactitude, which is my fault and not a problem with what I have learned.

Section 6.3

Difficult: I can read the algorithm just fine, but I feel lost when reading the definition for how they got up to the algorithm. I read it twice, and I still just don't seem to fully grasp it. I can't even tell why.

Reflective: I think it is really cool that we can find medium sized factors of numbers. It makes me think more and more that there must be a quick way to find them. Is there any proof of what time complexity class that factoring numbers belongs to?

Chapter 6.1-6.2

Difficult: This is all pretty familiar since I have taken the cryptography class before. I would like it if we could see you run the material in sage, but I don't think we have a project in class, so that probably won't be possible.

Reflective: It is very interesting to consider these curves. I still find it amazing that we are able to use them for cryptography.

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.

Section 3.3 Part 3

Difficult: Especially on pages 118-119, when the sums are changing form over and over I get lost. I admit that I have a hard time fully follwing this part of the proofs. When we talk about them in class I can mainly see it, but not always, and that is what was the hardest in the proof.

Reflective: Theorem 3.3.7 seems very interesting to me. I would have never thought that there would be arithmetic progressions of length k. If possible I would love to see the proof some time during the class.

Section 3.3 Part 2

Difficult: I find that I have a hard time following the part of the proof, Lemma 3.3.8, where they go from the Dirichlet L-series to the Euler product representation. I don't get how the multiplication goes to summation. Does this relate back to something we did with Riemann zeta function?

Reflective: I still find it amazing that mathematicians thought up these proofs. They are so layered and complex, that it just blows my mind.

Section 3.6

Difficult: I didn't think there was much that was that hard to understand in this section. The math is all very simple, and for once I think the book actually described it rather well.

Reflective: I think it is interesting that we have these relations between various arithmetic functions. I am interested to see how this all plays out in the next section.

Section 3.3 First Half

Difficult: I didn't know what a root of unity was, so that made it harder to understand the proof. I looked it up and now can follow it, but it doesn't come the most intuitively.

Reflective: I think it is interesting that we have so much knowledge about the characters mod k. What I find the most interesting is how each proof is very straightforward and simple, nothing really that complex.

Section 3.2.5

Difficult: I got lost when they used Lemma 3.2.5.1 in their proof of the infinite primes. I guess that probably comes from the fact that I didn't understand the Lemma that clearly when I read it in the first place.

Reflective: Another proof. I am not sure what this tells us about the primes though, but I am sure that it adds something of value.

Section 3.2.4

Difficult: I find myself a little bit lost around the part of the proof here we show the existence of m'. I think I mostly follow it, but it is the most hazy part.

Reflective: I think it is interesting that we know the fewest number of terms to the k power we need to get every other term. This may not be very applicable, but to me it is a very interesting fact.

Section 3.2.2

Difficult: I got lost during the explanation of Fermat's two-square theorem. I could understand the first part, but when the began to add all the different functions I got lost as to what they were speaking about.

Reflective: I think it is very interesting that we have defined all the numbers that can be the sum of squares. I am also interested to see how the Dirichlet character and function will be used later.

Section 3.2-3.2.1

Difficult: The infinite descent proof confused me. Someone the transitions seem hand wavy to me. I can mostly follow the in between steps, but it doesn't come together as I was expecting.

Reflective: I don't really know what to say. I am interested to see where this is going, but I don't yet see why this is going to apply to the infinitude of primes.

Section 3.1.5

Difficult: I got lost on the proof of Lemma 3.1.5.5. It just keeps going and I don't think I get the very first part quite well enough to follow it through. I also don't understand why in Lemma 3.1.5.1 we need primes that are congruent to 1 mod 4 in the first part.

Reflective: It is interesting to see some proofs of specific cases, but I would rather just get straight into seeing the main proof.

Rest of Section 1.3.4

Difficult: Some of the proofs of the Fibonacci numbers leave me confused. They treat some of the inductive steps of the Fibonacci numbers as obvious, but I am not seeing them.

Reflective: It was interesting to see all the various properties of the Fibonacci numbers. Some seem pretty obvious, but others were pretty crazy. I am surprised that there is so much interesting about them.

Section 3.1.4 through Page 72

Difficult: The most difficult part was just remembering all the various geometric rules. I havn't dealt with many of them in a long time, so I was rather hazy on some of them. Other than that it was pretty interesting.

Reflective: I found it rather cool to see how easy it was to draw a line with length equal to the golden number, even though it is irrational.

Section 3.1.3

Difficult: I got lost on the proof of Euler's theorem on the relation of perfect numbers to Mersenne primes. I don't understand how we can directly state the value of the sum of the factors of u.

Reflective: I didn't know that perfect numbers had any way to directly calculate them. I guess they still don't since Mersenne primes don't either, but it is still interesting to see this relationship. I wonder what this means in a larger picture sense.

Section 3.1.2

Difficult: All of it was pretty hard to follow, but the worst was the Riemann zeta function. I just had a hard time on the second page of its description.

Reflective: Analytic proofs are an interesting difference to most of the proofs we have been doing, but I have to admit they are much more confusing for me.

Exam 1 Prep

◦Which topics and theorems do you think are the most important out of those we have studied?
I think those that deal with congruence and facts learned about Z_p would be the most important. This would include subjects such as the number of integers relatively prime to some given n, whether a given number is quadratic residue, etc...

◦What kinds of questions do you expect to see on the exam?
Some application, maybe say solving Jacobi numbers, or solving for x in some large polynomial in Z_[some composite]. Also to write out proofs that are similar to the ones we have done in class/homework. Maybe more proofs of the infinitude of primes.


◦ What do you need to work on understanding better before the exam?
I just need more practice seeing and working the more important proofs. I understand them, but I am not sure I could reproduce them on demand.

Section 3.1.1

Difficult: I wasn't able to really follow the proof of Lemma 3.1.1. I don't see how we transfer from the set of F9k) for all k element of the Naturals, then limit it to a single f(k) and then re-apply it to all f(k).

Reflective. I think that it is interesting that there are so many proofs of the infinitude of primes, and that they all show us something a little different about the primes.

Jacobi Numbers

Difficult: The reading was really short and I already knew about Jacobi numbers so I didn't really find anything hard. The results shown follow pretty straightforward from Legrange numbers.

Reflective: I read a little more and saw about Euler psuedo-primes. I know there are systems that lack carmichle type numbers, and I was interested to see another. I find probalistic methods very interesting.

Section 2.6

Difficult: I had a hard time following the proofs of the two Lemmas given by Gauss. They were long, and I got lost early, which didn't help.

Reflective: I find it interesting that we can easily determine if a number is a quadratic residue, but determining what x is, is computationally hard. I find it so interesting that it can be so easy to prove existence without proving what an item is.

Section 2.5.2

Difficult: Following the initial description of the Chinese Remainder Theorem was also hard. I am having a hard time correctly following all of its pieces.

Reflective: I like how the fact that we can reduce polynomials comes into play for the finite field math of AES. I also like how the quadratic formula can be used in Z_p.

Section 2.5.1

Difficult: I found the description of the Chinese remainder theorem hard to follow. Also there examples I felt jumped around. It was hard to follow what they were doing at each individual step.

Reflective: It is interesting to see how we can expand what we have been learning to solve systems not only in Z_p, but also in in Z_n, where n is composite.

Section 2.4.4

Oops, last time I blogged about the wrong section (2.4.5, today's section). Here is what I should have written for last time.

Difficult: I still have a hard time conceptualizing what is going to be a primitive root and what is not. I feel that it should be a little more obvious, but maybe it isn't.

Reflective: The existance of psuedo-primes is interesting, especially how there are even a set of numbers where they will always appear prime using Fermat's Little Theorem. It makes it clear that we can't extrapolate too much from what we have.

Section 2.4.5

Difficult: I did have a little bit of a problem following the proof of Lemma 2.4.5.2. I understand it now, but it was a little harder to follow because it switched back to using the division algorithm, which I wasn't expecting.

Reflective: I liked how we offed an alternative proof of the theorem 2.4.5.2. I really like it when I can see multiple proofs for the same concept, it helps me see how everything is connected.

Section 2.4.3

Difficult: Once again not too much was difficult because this is basic in the areas of cryptography that I study. The only difficult thing was following all the proofs in the book. I just don't feel they are written as clearly as they could be.

Reflective: Once again I find this information to be extremely interesting. It amazes me how much is later derived from these very concepts. It is also interesting to see how it is so trivial to determine much of this material with congruences for computers.

Section 2.4.2

Difficult: This section was mostly review from my 2 cryptography classes and my abstract algebra class. As such the only difficult part was Theorem 2.4.2.4, but just because I had never seen it before. It makes sense, though, and it is a nice contradiction proof.

Reflective: I am constantly amazed by what we pull out of congruences and modular arithmatic. Just today I had to re-explain finite field math for AES to someone, and it is crazy how well it works. I am interested to see what we will pull out of it this semester.

Section 2.4

Difficult: The most difficult part at first was reviewing the concept of a UFD, and Euclidean domains, though this second time through I think I understand it without and problem. The congruence stuff made sense because I have done it several times before.

Reflective: I find it interesting how much can be learned about number systems by mapping them to others, as shown in the relationship between Euclidean domains and UFDs.

Section 2.3

Difficult: I had a bit of a difficult time undersanding the language used to describe UFDs. It didn't help that there were no proofs of the two theorems. I was able to get it in the end, but it was a little harder.

Reflective: Once again this was mostly review for me, the Lemma 2.3.3, about perfect nth powers was new to me, and without any examples of how this is used I am not quite sure its purpose, but i am sure that will come up more later.

Section 2.1 - 2.2

Difficult: For me the hardest part of the section was the proof that showing well ordered property and induction were equivalent. I had a slightly hard time following the proof the entire way through.

Reflective: For the most part this material is stuff that I still freshly remember from abstract algebra. It was interesting to see lemmas written slightly different then I have seen them in the past, such as that (a, b)*[a, b] = a*b. I guess I knew this since I knew [a, b] = a * b / (a, b), but I had just never seen it written in that form.

Introduction

I am currently a first year masters student, and will graduate April 2013. I plan to continue with a PhD in computer science after I graduate.

I have taken Linear Algebra, Multivariate calculus, Cryptography, and abstract algebra since calculus.

I am taking this class since much of the research in cryptography has a basis in number theory. I want to prepare myself so that I could do my PhD in cryptography.

What has made math classes the best for me is when they involve application to real problems using software such as Mathematica or Maple.

Unique about myself is that I speak fluent Chinese and am starting to learn Russian.