Page 23 - Hardware Implementation of Finite-Field Arithmetic

6 Cha pte r O n e

More generally:
Properties 1.3
1. Let g = gcd(a, n). Then the equation ax ≡ d (mod n) has a
solution x if and only if g divides d.
2. The solutions of ax ≡ d (mod n) are the same as the solutions
of (a/g)x ≡ (d/g) (mod n/g).
3. There are g solutions, all of them congruent modulo n/g.

Proofs
1. If ax ≡ d (mod n), then ax − d = qn. As g divides both a and n, it
also divides d.
If g divides d, then d = qg. According to Eq. (1.1), g is a linear
combination of a and n, that is g = ba + cn. So d = q(ba + cn) and
x = qb is a solution.
2. If g divides d and ax ≡ d (mod n), that is ax − d = qn, then (a/g)x −
(d/g) = q(n/g) and (a/g)x ≡ (d/g) (mod n/g). Inversely, if (a/g)x ≡
(d/g) (mod n/g) then ax ≡ d (mod n).
3. As a/g and n/g are relatively prime, there is a unique solution
− 1
within Z , namely, x = x = (d/g)(a/g) mod n/g. The complete
n/g 0
set of solutions within Z is
n
x = x + k(n/g) ∀k = 0, 1, . . . , g − 1
k 0
Observe that if k < g and x < (n/g), then x ≤ (n/g) − 1 + ( g − 1)(n/g) =
0 k
n − 1.
Definitions 1.8
1. The set of elements x of Z relatively prime with n is the
n
multiplicative group Z * :
n
Z * = {x ∈ Z | gcd(x, n) = 1}
n n
2. The Euler phi function φ (n) is the number of elements in Z *.

n
According to Property 1.2, Z * is the set of invertible elements of Z .
n n
In particular, if p is a prime number then
Z * = {1, 2, . . . , p − 1} and φ (p) = p − 1
p
Property 1.4 (Fermat’s little theorem ) Let p be a prime. Any integer
x satisfies x ≡ x (mod p), and any integer x not divisible by p satisfies
p
x p − 1 ≡ 1 (mod p).
Proof If x is not divisible by p and if ix ≡ jx (mod p), that is, (i − j)x =
qp, then i ≡ j (mod p). Thus

(1x)(2x) . . . ((p − 1)x) ≡ 1 2 . . . (p − 1) (mod p)