Sections 7.3-7.5 Monday Nov 1rst

  So this reading assigment is the discrete log equivalent of the reading on treaty verification and non-repudiation for RSA.  Cool applications of a cipher system.  The reading seemed to be going off on three topics until at the end when Diffie-Hellman and ElGamal were shown to be similar.
  ElGamal works because (a^-k)(m)(a^k)=m in the ring of integers modulo a prime p.  But I remember that that is not always the case for every group.  I think that non-abelian groups are the ones for which  (a^-k)(m)(a^k)=m is not true.  But I need to look that up again.
  Diffie-Hellman is pretty slick. Alics picks an x and Bob picks a y and each sends the other a raised to their integer mod p, then they raise the number they recieved to their own integer's power.  then both end up with the same number to use as a key, even though Eve only knows a^x and a^y.  Eve can't find a^(xy) because that would solve the discrete log problem.  Really clever.
  Have to go over why this is the same as the ElGamal procedure though.  Suppose that seeing the lecture tomorrow will make the linkage more clear.
  Dr. Doud kept saying that he wanted to show us "Russian Peasant" multiplication, but lamented that he did not have the time to show us.  If you have time that would be neat to see.
  Hope that the conference you attended went well. See you tomorrow.

Oct 29 2010 Section 7.2

  This discusses the discrete log problem and shows how difficult a discrete log equation is to solve and shows a few algorithms for solving them.  The DES and AES algorithms were easier to read because they were diagrammed, I think that drawing out the steps is pretty critical to having them sink in.
  The three algorithms that were mentioned were Pohlig-Hellman, Baby Step-Giant Step and Index Calculus.
  Baby Step-Giant Step seems to be the easiest to understand.  You find a^j=ba^(-nk) with 0<j,k < n and that gives you j+nk  is the answer.  This is only effective for problems with p is less than 10^20.  Not as effective as the Index Calculus, which the book says is effective up to p is less than 10^200.
  I don't understand the P-H.
  I see lots of problems with the primes that are 3 mod 4.  First they have problems with factoring, then they have problems with the discrete log.  I bet they are related to the Collatz conjecture.  And all those other hard problems that haven't been solved yet.
How is it that 4 comes into both factoring and discrete logs?
Come to think of it, 4 is really important in the Collatz conjecture too.  Maybe I should look into that.

Section 4.6 Due Friday October 22

Today's reading was on Fermat factoring and p-1 factoring.
Fermat factoring was pretty simple to understand.  The idea of completing the square to factor is pretty well discussed in high school algebra, and this is very similar to the quadratic formula.  On the other hand p-1 is kind of weird.  I suppose that is because this is a probabilistic attack on RSA and it will take a bit of work to understand that fully.  Almost like approximating a function with a power series.  but I don't understand the gcd(b-1,n)=1 mod (n) part, why compute all of the bj's if you don't use them?  At least, the statement of the theorem doesn't show how they are used.  Perhaps during the lecture their use will be made more clear.

Section 3.9 Friday, Oct 14

  So this is basically the generalization of the Chinese Remainder Theorem to the case of non linear congruences.  It didn't seem too hard to understand, but I still have some problems with the Extended Euclidean algorithm, which would be needed to find inverses.

  This is a way to attack RSA, and also a caveat to those building an RSA to choose p and q well in the system.

  Thinking about this section has made me think that slide rules must be build on modular arithmetic, that the two parts of the slide rule move against each other the same way that the two modular expressions move against each other when you are using the Chinese remainder theorem.  Also, you can use a slide rule to take square roots, and you can use the Chinese remainder theorem to take square roots.

  There are geometric interpretations for classical algebraic systems, and I would like to know more about the geometry of algebraic rings,  which I imagine as kind of like a bunch of slide rules near each other.  But I still need to think about what GCD means in a slide rule interpretation of an algebraic system.

October 10 Section 3.12

This section is on continued fractions.  It was a pretty cool chapter because I always thought that continued fractions were unwieldly, but the fact that when partial fractions converge each approximation can be proved to be better than the last one is really cool.  It is a built in margin of error calculator.
My problem with the examples is it didn't show how to get a decimal representation of the number to use in the algorithm for creating a continued fraction.  They approximated pi, but used pi to create the fraction that they used to approximate pi.

October 4th section 3.3 and 3.4

  The reading for today was about the Chinese Remainder theorem which can be used to break a congruence problem into a system of smaller congruences, or to take a system of congruences to a single congruence statement.  I assume this is how RSA works, by large number systems of congruence.  But I need to reread that section to get it clear.  I reread the section on block sipher modes and it makes sense now.  I think that the reading-lecture-rereading is the best method of study.
  But back to the CRT, if x = 4 mod 7 and x = 3 mod fifteen, then x=18.
  Larger numbers are only more difficult because the process is longer, but not too hard.
  Still kind of scared about the test though.  Esspecially because I have class all day Tuesdays and will have to take the test tomorrow.