The magic of mathematics and theoretical computer science is all the unexpected connections. You start looking for general principles and then mysterious connections emerge. Nobody can say why this is. — Robert Endre Tarjan
Let be a prime number. We know that . Let be the ring the polynomials with indeterminate and coefficients in . The polynomial factors over as follows for various :
None of the factors above can be factored anymore, hence they are irreducible over . Let us call the trivial factor since the root already belongs to . But why do we have two nontrivial irreducible factors of , each of degree 3, whereas has only one non-trivial irreducible factor of degree 12? It appears that either there is only one nontrivial factor, or the degree of all nontrivial factors is the same. Why?
To this day, no method of finding a generator of is known to be more efficient than essentially trying 2, then 3, and so on. Who cares? Well, the difficulty of breaking a certain public key cryptosystem (due to El Gamal) depends on the difficulty of working with generators of . — Keith Conrad
An th root of unity in a finite field is an element satisfying , where is an integer. If is the smallest positive integer with this property, is called a primitive th root of unity. If is a primitive th root of unity, then all elements in the set are also roots of unity. Actually, the set form a cyclic group of order under multiplication, with generator .
Problem: Suppose you are given a finite field of degree , and you are promised that there indeed exists a primitive th root of unity for prime. Find , and in particular, produce a C++code that finds it.
In what follows, we talk about how to find such a root and provide my C++ code; the code uses the awesome NTL library.
This is a beautiful theorem which states that the difference between a positive integer and a prime power of , , is divisible by . It’s history can be found in Wikipedia: Fermat posited the theorem (and as usual, did not give the proof) while Euler first published a proof using mathematical induction. Below, we will state the theorem and provide a simple-to-understand proof using only modular arithmetic, followed by another simple proof using mathematical induction.