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.
Continue reading “Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code”
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.
Continue reading “Fermat’s Little Theorem”
Riemann zeta function is a rather simple-looking function. For any number , the zeta function is the sum of the reciprocals of all natural numbers raised to the power.
Although the variable is a complex number, for the sake of simplicity, we will treat as real. (Real numbers are a subset of complex numbers.)
Continue reading “Euler’s Product Form of Riemann Zeta Function”