2007-05-21
----------

1. Hand back second drafts.  Final drafts due on last day of class.  You must
   both email me an electronic version and turn in a printed version.

2. Turn in homework.

3. Projects -- everyone say your name and briefly description of your
   project.

4. Pollard p-1:
   (a) define B-power smooth
        p_i^(e_i) <= B
   (b) How to compute LCM(1...B)
   (c) Pollard p-1 idea:
        INPUT: Positive integer N, bound B. 
        OUTPUT: Maybe find the p | N with p-1 a B-power smooth number.
        ALG:
          1. let m = lcm(1..B)
          2. a = 2
          3. Let x = a^m - 1 (mod N) and g = gcd(x, N)
          4. If g != 1 or N, output g.
          5. a = a + 1 and go to 2 (up to say a = 10).

5. Example:
       N = 5917, B=5.

6. Why it works: 
       If N = p*N' say, with p-1 B-power smooth, then a^m - 1
       is divisible by p by Fermat's Little Theorem.  But
       a^m - 1 often isn't divisible by all other prime factors
       of N'. 

8. Next time: Lenstra elliptic curve method.
   Example of elliptic curve addition:
   (1,0) + (0,2) = (3,4) on y^2 = x^3 - 5x + 4