Clay Math Institute Lecture 7 Dec 2010

1. The lecture was primarily on Prime Numbers. There wasn't anything TOO new in the lecture. He talked mostly about the mystery behind some patterns contained within prime numbers and then focused the remainder of the time on the RSA cryptosystem. One thing that is hard for me to fathom is how simple prime numbers are, yet how hard the research on them is. For instance, why is it so hard to find the next prime number? Isn't it just the next non-crossed off number using the Eratosthenese Sieve? Or why is it so hard to explain why factoring large numbers is hard. I know it's hard, but why is it hard to explain?
2. Something rather interesting about the presentation was contained in one sentence the presenter used: "Prime numbers are like atoms." He was saying that every number that isn't prime can be broken down into its key component numbers that ARE prime. I had never thought about prime numbers like this, but now that's pointed out, I like the comparison.

Section 16.5 Due 8 Dec 2010

1. The reading was simply an application of elliptical curves combined with cryptosystems we've already covered in the course. There wasn't anything TOO difficult about that. There was one thing, however. I didn't really understand WHY the verification step works in the ElGamal Digital Signatures application of elliptical curves. Also, I think I'm just over analyzing the reading, but it is very explicit in pointing out the fact that k^-1*k is not 1 but is congruent to 1. I don't understand why they're pointing that out here. I thought that was made clear in the beginning of the book. As such, I'm worried I'm missing something.
2. The thing I thought about most in relation to this reading was why would we use Elliptical Curves in a situation rather than using one of the original cryptosystems we've discussed. That is, why use the Elliptical Curve version of ElGamal rather than just plain old ElGamal? The question is, what advantages does one have over the other?

Section 16.3 Due 3 Nov 2010

1. Two things I don't really understand. Toward the beginning of the reading it uses the denominator of the slope between two points to find the gcd between it and the number trying to be factored. I don't think I really understand WHY they use the denominator of the slope. After reading it through a few times, it seems like they did this because they were trying to find the inverse of 1770. Nonetheless, I'm not sure how this leads to using it to find the factorization of 2773. Then later in the reading, toward the end, they mentioned that this method is similar to finding gcd(1,n) and gcd(2,n) and so forth. It's probably not a big deal, but I don't see how they are related.
2. It's not too difficult but I'm interested in knowing more about the difference between "smooth" and "B-smooth." Again, it's probably not a big deal, but I have this thing with somewhat ambiguous definitions. Who's to say what are "only small prime factors" and what's not? Where is the line drawn?

Section 16.2 Due 1 Dec 2010

1. The thing I don't quite understand is why we would want to mod an elliptic curve. It seems to me that gives us less points on the curve to work with. In cryptography, don't we want as many options as possible, leaving more room for error on the part of the attacker? In short, how does mod-ing an elliptic curve increase advantages? Perhaps this won't be made clear til we start examining the cryptography applications of elliptic curves.
2. I'm starting to guess that as far as cryptography applications go, elliptic curves may be useful once we DO mod a point because then it will be harder to undo the mod, thus increasing the security.  One other thing, I got lost on why they used 2773 as an example when it isn't prime. How important is it for p to be prime when modding? What goes wrong when p is not prime?

Section 16.1 Due 29 Nov 2010

1. The hardest part for me to understand was the first example they give us to examine. It was hard to follow where all the numbers were coming from and why they were substituting certain expressions for specific variables in various other expressions. I also didn't understand why they could say that the sum of the three roots is minus the coefficient of x^2. Then later in the reading it suggests that -4 is a double root. Yet earlier in the reading it suggested as a "technical point" that we wouldn't worry about multiple roots until 16.3.
2. When doing these readings, I like to predict how the new ideas and techniques being introduced are going to be used in cryptography. I'm guessing that somehow the author of a certain key is going to use a made up equation (made up according to certain guidelines). Then the author is going to pick two (possibly random?) points and use them to find the third point based on the line that goes through P1 and P2 as described in the text. The coordinates of the third point will then be used to create an encryption and decryption key. I don't know HOW the coordinates will be used (unless the original two points are chosen so that the third point is composed of two large random numbers and then we would be in the realm of RSA) but I'm pretty sure they will be used to create E[k] and D[k]. I'm guessing all this purely on the ideas we've discussed on public cryptosystems. The third point is easy to find only to the author of the equation of the elliptical curve. It would be nigh impossible for a random citizen to find the original two points based purely on the third point. This leaves me with the question, "what components will be made public? P3? P2 & P1?" My guess is P3. Then the author can use P1 and P2 to create a decryption key.

Shor algorithm and section 9.3 Due 22 Nov 2010

1. It was a very well written article. It didn't use hardly any math (except periods and mods). But there were still a few issues I had with it. Finding phi(n) corresponds to finding a multiple of the period mod some N. However, how does one choose N? I'm still having trouble figuring out how to choose N. Furthermore, once one DOES choose N, and finds the period then how can one be sure of the corresponding phi(n)? For example, in the article they let N=15 and found the period to be 6 and phi(n)=12 and explained that sure enough 6 divides 12. When I read this, I thought, "but 6 also divides 24 and 36 and 66, etc." How can I find phi(n) based solely on the period?
2. There was a part explaining something called repeated squaring. It seems to me that's the same as our exponentiating a number mod n that we've learned. On another note, or maybe this would best fit under the previous section, it seems like this article would fit better under our section that examined RSA rather than quantum cryptosystems?

Section 14.1, 14.2 Due 17 Nov 2010

1. I've read the sections twice over and am still having trouble understanding how exactly Peggy can use square roots of factors of x to show Victor that she has factored n. How is showing Victor x[1] or x[2] the same as showing Victor that she has factored n? Isn't she giving him enough information so that he can actually deduce what s is, or for that matter what the factors of n are? I think I'm getting lost in the labeling of variables somehow.
2. If Peggy were to mis-choose which numbers to send to Victor as proof, wouldn't there be worse consequences than Victor knowing that Peggy didn't find a factor of n? Wouldn't Victor know that for some reason Peggy was just shooting in the dark, hoping to find some secret information or get something out of Victor? How does this apply to the example of crooks trying to steal sensitive information?