Why x^p-1 Factors over GF(2) the Way It Does

Let p be a prime number. We know that F_2=GF(2)=\{0,1\}. Let F_2[x] be the ring  the polynomials with indeterminate x and coefficients in F_2. The polynomial (x^p-1) \in F_2[x] factors over F_2 as  follows for various p:

x^3-1=(1+x) (1+x+x^2).
x^5-1=(1+x) (1+x+x^2+x^3+x^4).
x^7-1=(1+x) (1+x+x^3) (1+x^2+x^3).
x^{11}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}).
x^{13}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12}).
x^{17}-1=(1+x) (1+x^3+x^4+x^5+x^8) (1+x+x^2+x^4+x^6+x^7+x^8).

None of the factors above can be factored anymore, hence they are irreducible over F_2. Let us call x+1 the trivial factor since the root x= 1 already belongs to F_2. But why do we have two nontrivial irreducible factors of x^7-1, each of degree 3, whereas x^{13}-1 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?

Continue reading “Why x^p-1 Factors over GF(2) the Way It Does”

Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code

9th roots of unity. Source: Kyle Miller’s article.

To this day, no method of finding a generator of Z_p^* 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 Z_p^*.Keith Conrad

An nth root of unity in a finite field F is an element r \in F satisfying r^n=1, where n is an integer. If n is the smallest positive integer with this property, r is called a primitive nth root of unity. If r is a primitive nth root of unity, then all elements in the set \mu_n = \{1, r, r^2, \cdots, r^{n-1}\} are also roots of unity. Actually, the set \mu_n form a cyclic group of order n under multiplication, with generator r.

Problem: Suppose you are given a finite field F=GF(2^d) of degree d, and you are promised that there indeed exists a primitive pth root of unity r\in F for p prime. Find r, 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”

Euler’s Criterion for Quadratic Residues

Leonhard Euler (source: Prolineserver)

Here we would show a beautiful application of Fermat’s Little Theorem.

An integer a is a quadratic residue with respect to prime p if a \equiv x^2 \mod{p} for some integer x.

Given a prime p and an integer a, how fast can we decide whether a is a quadratic residue modulo p? As it turns out (courtesy to Euler), pretty fast.

Continue reading “Euler’s Criterion for Quadratic Residues”

Fermat’s Little Theorem


This is a beautiful theorem which states that the difference between a positive integer a and a prime power of a, a^p-a, is divisible by p. 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”

Euler’s Product Form of Riemann Zeta Function

Riemann zeta function is a rather simple-looking function. For any number s, the zeta function \zeta(s) is the sum of the reciprocals of all natural numbers raised to the s^\mathrm{th} power.


Although the variable s is a complex number, for the sake of simplicity, we will treat s as real.  (Real numbers are a subset of complex numbers.)

Continue reading “Euler’s Product Form of Riemann Zeta Function”