Page 24 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 7

As the p − 1 above multiples of x are distinct and nonzero, they
must be congruent to 1, 2, 3, . . . , p − 1 in some order.
So
(p − 1)!x p − 1 ≡ ( p − 1)! (mod p)
or
( p − 1)!(x p − 1 − 1) ≡ 0 (mod p)

As p does not divide (p − 1)!,
(x p − 1 − 1) ≡ 0 (mod p)

that is,

p
x p − 1 ≡ 1 (mod p) and x ≡ x (mod p)
p
If x is divisible by p, then x ≡ x ≡ 0 (mod p).
Corollary 1.1 Let p be a prime. If x is not divisible by p and if r ≡ s
(mod p − 1), then

r
s
x ≡ x (mod p)
Proof Assume that r > s. Then r = q(p − 1) + s and 1 ≡ 1 ≡ (x p − 1 q r − s
) ≡ x
q
r
s
(mod p), so that x ≡ x (mod p).
Definitions 1.9
1. The order of an element x of Z * is the least positive integer t
n
t
such that x ≡ 1 (mod n).
2. If the order of x is equal to the number φ (n) of elements in Z *,
n
then x is said to be a generator or primitive element of Z *.

n
3. If Z * has a generator, then Z * is said to be cyclic.
n n
1
3
Observe that if x is a generator, then Z * = {x , x , x , . . . , x φ(n) }.
2
n
Example 1.4
Z = {0, 1, 2, 3, 4, 5, 6} and Z * = {1, 2, 3, 4, 5, 6};
7 7
7 is prime and φ (7) = 6;
3
3
1
6
1 ≡ 1 (mod 7), 2 ≡ 1 (mod 7), 3 ≡ 1 (mod 7), 4 ≡ 1 (mod 7),
6
5 ≡ 1 (mod 7), 6 ≡ 1 (mod 7);
2
there are two generators: 3 and 5; for example:
4
1
2
3
3 ≡ 3 (mod 7), 3 ≡ 2 (mod 7), 3 ≡ 6 (mod 7), 3 ≡ 4 (mod 7),
5
6
3 ≡ 5 (mod 7), 3 ≡ 1 (mod 7).