2007-04-09

1. Turn in your homework now.
   Redistribute.
   Reminder: Be *very* careful not to loose the person's homework 
   that you will grade.  Also, this grading process is *very* 
   valuable to you -- you will learn things you will not learn
   in other classes, and in _life_ usually you will really
   be evaluated by your peers. 

REMARKS from the Grader:

I always look at where the first grader took off points.  I read all
their comments.  The computational problems, I briefly look at, but I
assume that the first grader can grade this part okay (so problems 2
and 3 on this assignment).  Problem 1 was pretty straightforward and
didn't cause too much problem.  On problem 4a, the biggest error was
basically assuming what you were to prove in some way.  You had to use
prime factorization, or some other property of primes.  Part a) cause
more trouble than part b).  On problem 5b, as you already knew, many
people didn't prove the hint.

I'd guess overall I'd say that you can tell some people know what a
"proof" is, how you write one up, etc., and do well.  There are a few
students who still don't seem to know.  The grading was pretty good.
There were only one or two that I thought the first grader gave them a
lower score than I would have.  The surprising thing to me was how
sometimes a grader would give a perfect score on a problem, when there
were big problems with the proof.  If they don't know if its correct,
they should just write a comment indicating so.  The more comments the
grader makes, the better.

-------------------

2. Remarks about your feedback.  Reading through it all carefully, the
   following emerged:

Please -- 
   a. Stop me if I do not write enough on the blackboard.
   b. Stop me if I do not give enough details (especially, 
      about groups, rings, etc.)
   c. Ask me to slow down if necessary.

Way more people need me to explain more, write more, and slow down
than want me to speed up.   If the class is too slow for you at
certain points, work on something else, like your project or the
homework.  I often have my best ideas during lectures on things
that I already know. 

--- TODAY: Two algorithms -- powers and inverses. 

You will need to be able to do these entirely by hand on numbers with
up to 3 digits in order to get a perfect score on the in-class
midterm.

3. Explain the extended Euclidean algorithm with a couple 
of examples.
ALGORITHM: xgcd
INPUT: a, b
OUTPUT: x, y and g such that a*x + b*y = g and g = gcd(a,b).
Useful -- allows one to invert and modulo n and solve equations
modulo n efficiently.  Crucial that you understand this if you
wish to understand public key cryptography!
HOW it works:
Write
     a = b*q + r
Then as we saw before
    gcd(a,b) = gcd(b,r).    (run through proof in words).
We have
    r = a - b*q
Now we just keep this up, keeping track of the relation.
    b = r*q' + r'
so 
    r' = b - r*q' = b - (a - b*q)*q' = b - a*q' + b*q*q'
                          = a*(-q') + b*(1+q*q')
etc., gives
    g = gcd(a,b) = a*x + b*y
explicitly.

Best illustrated with a bunch of examples. 
  * gcd(17, 61)
  * gcd(20, 135)
  * gcd(35, 100)
  * gcd(91, 21)
  * gcd(389,431)
   
APPLICATION: Solve a*z = b (mod n) when gcd(a,n) = 1.
Solution.  Find x,y such that a*x + n*y = 1.  Then a*x = 1(mod n),
so just multiply both sides of equation by x, to get
           z = x*b (mod n),
i.e., x is inverse of a modulo n.

--------------

4. Computing powers quickly.
This is even more important if you want to understand how
public-key cryptography works. 

ALGORITHM:
INPUT: a, m and n
OUTPUT: a^m (mod n).
How it works:
  (1) Write m in *binary*
  (2) Then
       a^m = prod a^(2^i)
      for various i.
      And each a^(2^i) we get by successively squaring. 

Examples:
1. Find the last two digits of 7^91.  
   Solution: compute 7^91 (mod 100).
   We do this using the generic algorithm above combined
   with a trick to simplify it a little.

  (1) write 11 in binary:
We do this by dividing by 2 and checking whether the
remainder is 1 over and over until done. 
    11 = 5*2 + 1
     5 = 2*2 + 1
     2 = 1*2 + 0
     1 = 0*2 + 1
  So in binary, (11)_2 = 1011, 
  which we check:
     11 = 1*8 + 1*2 + 1.

  (2) Compute a, a^2, a^4, a^8 and output
        a^8 * a^2 * a
  We have
    a = 7
    a^2 = 49
    a^4 = 49^2 = 1   (or work mod 4 and 25 and use crt)
          49
        ----
          41
          6
        ----
          01
    a^8 = 1^2 = 1
  Then
    a^8 * a^2 * a = 1 * 49 * 7 = 43 (mod 100).