Page 22 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 5

Notation:

x ≡ y (mod n)

Properties 1.1 (basic properties of congruences)
1. x ≡ y (mod n) if and only if (x mod n) = (y mod n) (Definition
1.3).
2. The relation x ≡ y (mod n) is an equivalence relation (reflexive,
symmetric, and transitive).
3. If x ≡ y (mod n) and x ≡ y (mod n), then
1 1 2 2

(x + x ) ≡ (y + y ) (mod n) (x − x )
1 2 1 2 1 2
≡ (y − y ) (mod n) (x x ) ≡ (y y ) (mod n) (1.2)
1 2 1 2 1 2
From Properties 1.1(1 and 2), it can be seen that the mod n congruence
relation partitions Z into n equivalence classes . Each equivalence
class contains exactly one element of the set {0, 1, 2, . . . , n −1}, namely
the common value (xmod n) for all elements x of the class. Furthermore,
according to Property 1.1(3), the addition, subtraction, and multiplication
of congruence classes can be defined. As a matter of fact the set of
equivalence classes is isomorphic to

Z = {0, 1, 2, . . . , n − 1}
n

where the addition, the subtraction, and the multiplication are defi-
ned by

(x + y) mod n (x − y) mod n (xy) mod n ∀ x and y in Z
n
Definition 1.7 Given two elements x and y of Z , such that xy mod n = 1,
n
then y is said to be the multiplicative inverse of x. If such an inverse
exists, it is unique.
Notation:

y = x mod n
− 1

Property 1.2 x has a multiplicative inverse if and only if gcd(x, n) = 1.
Proof If xy ≡ 1 mod n, then xy = qn + 1 so that any divisor of x and n
is also a divisor of 1. Thus, gcd(x, n) = 1.
If gcd(x, n) = 1, then (relation 1.1) there exist b and c such that
− 1
1 = bx + cn, so that x = b mod n.