7.2

1. How come by making beta alpha to the t power we can hide information?

2. I think group theory is starting to cogitate in my mind. It's starting to feel very concrete. When this happens to me with math, I start proving things anew, for myself. Not new things, but I feel like I develop the proof for certain things even though I was brought up in them. They're just no longer rote. It's happening a little bit with RSA also. If I had a real blog, I wouldn't subject you to this inane commentary.

6.5-6.7, 7.1

1. In discrete logs, why would the prime be left out of the notation? Surely the logarithm makes little sense without the context of the prime in question, or can it be generalized?

2. Interestingly enough, one of the efforts to break RSA is headed by people who want to watch high definition films on their Linux machines. Based on what I read some months ago, one attack vector concerned the use of a low public exponent (something like e=3) in the AACS Blu-ray standard. This could be seen as a discrete logarithm problem, correct? And are these logarithms harder to solve as the exponent grows?

6.4.1

1. Why look for linear dependence (mod 2) specifically?

2. I am guessing this method doesn't scale because the matrices would get unduly large. Since each column represents a prime, we could quickly get to 1000 columns whilst dealing with primes around 10000. When dealing with 50 digit numbers, that's probably nothing.

6.4

1. The most difficult part for me is this: choosing to use B! is to make the algorithm easier, right? Otherwise, we could just use powers of primes less than B.

2. This is brilliant and simple and was disseminated in 1978 which boggles my mind. Part of me thinks that this is some low-hanging fruit that was somehow missed by all the other people looking for thesis topics but another thinks that the nature of things always looks more obvious in hindsight.

6.3

1. Why does the Miller-Rabin test work? I don't see it.

2. How is the guarantee that the test is correct more than 3/4 the time supposed to lend any kind of assurance to a person relying on it to secure their private data. He mentions once or twice that the test can be performed multiple times to get certainty arbitrarily close to 100% but also mentions that in many cases, one test is enough. My question is, in what venue would someone who needed a prime (for whatever reason) be satisfied with a certainty with lower bound 0.75? How is that useful?

3.10

1. If the Jacobi symbol is +1, it does not imply that a is a square mod n, but if it is -1, it implies that it definitely is not. Is that correct?

2. Whoa. The law of quadratic reciprocity. In some cases, this can be extended to even powers that are themselves powers of two, right? Suppose we want to determine whether b is a fourth mod p. Then x^4=b (mod p) is the same as (x^2)^2=b (mod p) so we determine, if p=3 (mod 4) (?), x^2. We then determine whether x^2 is a square mod p. Here when we write x^2, we aren't actually assuming that such an x exists, although it looks like it. If necessary, we could let y=x^2 and solve y^2=b (mod p) and then x^2=y (mod p) so that x^4=b (mod p). Is this right?

3.9

1. So when the author says to let x=y^(p+1)/4 (mod p) so that x^4=y^p+1 (mod p), do we know x and y?

2. While I was reading, I was thinking how the actual intuition behind Fermat's theorem has been kept from me in my education. I know proof techniques and enough number theory to justify it, but it has been so formalized that the impetus is lost. Then I started thinking, maybe results are what's important since they allow us to settle our brains--to rest them upon the rigor and irrefutable truth proof brings. We start thinking of things at higher levels and in more general terms until we're all brought up in the same education and creativity is only preserved in the sporadic genius of choice minds.

3.12, 6.2

1. I'm not sure I follow how the continued fraction method actually yields the factorization of n.

2. The news that RSA had a seemingly obvious weakness was unsettling, and underscores the importance of interdisciplinary collaboration. The author mentions that this class of weaknesses was not considered since the mathematics was well understood, and I would be interested to know the emphasis of the Stanford undergraduate who revealed this weakness. I'm sure he was studying math. I bet he was also studying Computer Science.

6.1

1. I hate to be like this, but I have gone over RSA several times. Stay tuned for attacks, though. I'm sure I'll have questions.

2. I'm going to once again bring up the "invented" vs. "discovered" notion of mathematics. It seems like the math climate today is that things are defined and then we see what follows, and this strikes me as an "invented" viewpoint. I fall in the both camp but there are a lot of things--identities and elegant results--that I think are discovered. To that extent, I feel like I'm surrounded by atheists. Except for our author who mentions that it's conjectured that the NSA discovered the RSA algorithm before, well, R., S., and A. did. Now I have mixed feelings. I think this is an algorithm that was invented. It's sort of like when you find the balance (religiously) between what's possible and what's realistic (like miraculous healing), and then someone attributes an everyday empirical result to a miracle. You don't want to suggest it's not intervention, but you don't really think it is. And by you, I mean me. Sorry, this isn't very topical. This is my only blog, though.

3.6-3.7

1. So if n is a Carmichael number and (a,n)=1 (which means a does not share what I assume is a small number of prime factors), a^phi(n)=1 (mod n) and the Euler-Fermat theorem fails?

2. I am fascinated by logarithms, probably because I don't understand them beyond basic application. I think they are analytic which boggles my mind: how numbers can contain in themselves and their algebraic relationships so much information. The discrete logarithm is also interesting because I can see how it would be useful but I have no idea how to go about finding it.

3.4-3.5

1. I know I'm not supposed to say nothing, but this is the fourth time I've been "taught" the Chinese Remainder theorem and fourth I've gone over modular exponentiation.

2. Cryptography is a pretty good mix of the theoretical and the practical. On the one hand, secure cryptosystems need to be provably secure, and this almost always includes a mathematical analysis of the system in an idealized manner, as in, is it possible to break it without going through all possible solutions? Is there a method to obtain a solution analytically? On the other, we have real world needs of speed and convenience. We move from states to processes and algorithms, of which modular exponentiation is a prime example. Not only does it avoid overflow, the time complexity is logarithmic with the exponent and not linear like the naive, albeit correct, implementation is.

Test Review

1. The most important things we have talked about, I think, are the principles of a secure algorithm, like whether it is susceptible to a known plaintext attack or under what conditions is a certain method secure. Probably not crack this Caeser cipher but more like what are the main vulnerabilities of the Hill Cipher.

2. A few simple code cracking problems. A question or two on whether a proposed algorithm has a certain weakness. Maybe one to do a portion of DES or AES.

3. AES and DES. I think I'm ok with all the rest.