2007-04-11

1. * Turn in your *graded* homework now.
   * Reminder -- feel free to slow me down if necessary.
   * Hand out new homework assignment -- due next Monday

2. Computing powers quickly.
This is very 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).
   
                  
3. Primality testing. 
Prove theorem:
 An integer p > 1 is prime <==> for all a =/= 0 (mod p) we have
     a^(p-1) = 1 (mod p).
Proof. One direction is Fermat's little theorem.
Other: Use "contrapositive".  If p is composite then
       let a be a proper divisor not 1 or p. 
       Then a | p | a^(p-1) - 1, so a | 1, a contradiction. 

So a primality *test* is:

   Compute 2^(p-1) (mod p).  If it's =/= 1 then p is definitely composite.

If it is 1, "probably" p is prime.  Choose a few more bases besides
2 to increase confidence.  This will be enough to find large "pseudo-primes"
for cryptographic purposes.   Emphasize that this frequently will
find for you composite numbers that you do not know how to factor. 

4. Charmichael numbers:
   p=561 has property that a^(p-1) = 1 (mod p) for all a with gcd(a,p)=1,
Theorem (Pomerance, Granville, Alford, 1994): There are infinitely many
Charmichael numbers.

(But there aren't very many.)

5. Lucas-Lehmer test and GIMPS:
Mersenne numbers: 2^p - 1
 - 44 known to be prime.
 - Biggest primes knowns. 
 - Next one found will probably yield a $100K prize.
 - Lucas-Lehmer test:
    Let s = Mod(4,2^p - 1).
    for i in range(3, p+1):   (i.e., 3,4,5,...,p
      s = s^2 - 2
    if s == 0:
       2^p - 1 is definitely prime,
    else:
       2^p - 1 is definitely composite.
  It's that simple.  
  http://www.mersenne.org for much more.
  The proof of the above algorithm at http://www.mersenne.org is
  sketchy, badly typeset, and only gives one direction of the proof,
  and assumes more algebraic number theory than most people know.
  Student project:
    1. Understand, in a very accessible way, how to prove that the 
       above algorithm works.
    2. Write up really nice proof that algorithm works. 
    3. Have your proof replace the one at http://www.mersenne.org