15-451			12/01/04

* more on relation of number theory and FFT
* more on primality testing, or other questions, or TA evaluations...
===================================================

More modular arithmetic:

If you pick some a in Z_N^* and look at the sequence 1, a, a^2, a^3, ...
(mod N), you will eventually get back to 1.  
     E.g., a=2, N=7, you get: 1, 2, 4, 1.

Working over Z_N^*, the "order" of an element a is the smallest t such
that a^t = 1 mod N.

A useful fact is if you look at the set {1, a, a^2, a^{t-1}}, where t
is the order of a, then this is a subgroup of Z_N^*:
  - closed under multiplication: 
		 a^i * a^j = a^{i+j} = a^{i+j mod t} mod N.
  - closed under inverses:
		 a^{t-i} * a^i = 1 mod N.
		
Note: This gives another proof of Fermat's little theorem.  If N is
prime, then the size of Z_N^* is N-1.  We know the size of a subgroup
divides the size of the whole group.  So, N-1 is a multiple of t.
This means that:
  a^{N-1} = a^{t*something} = (a^t)^{something} = 1^{something} = 1 mod N.


=================

FFT with modular arithmetic.

In lecture, we talked about the FFT and how using modular arithmetic
we can get primitive mth roots of unity.  E.g., 2 is a primitive 8th
root of unity mod 17.  A natural question to ask (which someone did
ask!) is: given m (which is some power of 2), how can you find w and N
so that w is a primitive mth root of unity mod N.   Here are two ways:

* Method 1: let w = 2, let N = 2^{m/2}+1.   [N doesn't have to be prime]

    - This means that w^{m/2} = -1 mod N, and so w^m = 1 mod N.

    - But could it be that the order of w is less than m?  If so, then
      since w^m = 1 mod N, the order of w must be some number t that divides
      m (i.e., m is a multiple of t). [Remember w^m = w^{m mod t}].

      But since m is a power of 2, this means that if t < m and t
      divides m, then t must divide m/2, and we know w^{m/2} is not
      equal to 1 mod N.  So, such t cannot exist.

  However, a problem with method #1 is that N is big (O(m) bits) and so
  each basic operation could take a long time.  So, another way to do
  this is:

* Method 2: Choose N to be the smallest prime of the form N = km + 1.
  It turns out that you generally expect to hit a prime with k =
  O(log m), but even k=O(m) would be fine.  (N would still only take
  O(log m) bits to write down).  We now pick a generator g in Z_N^* [a
  number whose order is N-1], and finally let w = g^k mod N.   How to
  pick a generator?   It turns out there are a lot of generators and
  since we can think of this as a kind of pre-processing step, we could
  imagine just picking g at random, letting w=g^k, and just checking if
  w indeed has order m as we want. 


------------------
can do this, or answer questions on other material or do TA
evaluations...

Primality testing:

In lecture we discussed a randomized primality testing algorithm.
Idea was: 
- if N is prime, then a^{N-1} = 1 mod N, for all a < N.

- So, let's try a bunch of random a's and test to see if a^{N-1} = 1
  mod N or not. 

- Two problems: 

  (1) it could be that N is composite, and yet EVERY a in Z_N^* has
  the property that a^{N-1} = 1 mod N.  These are called Carmichael
  numbers.  Luckily, these are rare and easy to factor [will get to in
  a minute]. Recall, Z_N^* = {a: 0 < a < N and a is relatively prime to N}

  (2) Could it be that ALMOST EVERY a in Z_N^* N^* has the property
  that a^{N-1} = 1 mod N??? 

One thing we can at least see is that (2) is not a problem.  The set
S = {a in Z_N^* such that a^{N-1} = 1 mod N} is a subgroup of Z_N^*.
Let's prove it:
     Closed under multiplication:  
      If a in S, b in S, then ab in S because (ab)^{N-1} = a^{N-1}*b^{N-1} = 1
     Closed under inverses:
      If a in S, ab = 1 mod N, then (ab)^{N-1} = 1, so b^{N-1} = 1.

Since the size of a subgroup must divide the size of the group itself,
that means that either S = Z_N^* or else at least half the elements in
Z_N^* are not in S.

So, this gives us our randomized one-sided-error algorithm for testing
primality, if you're willing to believe me that Carmichael numbers are
easy to factor.

Rough argument of how to factor Carmichael numbers:

 - First, suppose we have some number x that's not 1 or -1, such that
 x^2 = 1 mod N.  E.g., 11^2 = 1 mod 15.  This means that (x-1)*(x+1)
 is a multiple of N, even though neither x-1 nor x+1 is.  So,
 GCD(x-1,N) gives us a factor of N. (As does GCD(x+1,N))


 - to factor Carmichael numbers, we pull out all the 2's from N-1:
 i.e., we write N-1 = 2^k * B.  We then pick some random a's and
 compute a^B, a^{2B}, a^{4B}, ..., a^{N-1}.  (Notice that each element
 in this list is the square of the one before it).  We know the last
 thing will be 1.  It turns out that if N is Carmichael, you have at
 least a 50/50 chance that somewhere along the way, you had some x not
 equal to 1 or -1 whose square became 1.  Proving this again uses
 group properties.


=========================