# 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?

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

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 $n$th 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 $n$th root of unity. If $r$ is a primitive $n$th 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 $p$th 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.

# Euler’s Criterion for Quadratic Residues

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.

# Fermat’s Little Theorem

Introduction

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.

# Proofs from the Book

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. $\begin{array}{ccl}\zeta(s)&=&\displaystyle\sum_{n=1}^{\infty}{\frac{1}{n^s}}\\&=&1+\frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\frac{1}{5^s}+\frac{1}{6^s}+\cdots\end{array}$
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.)