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