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.
=========================