Page 19 - Hardware Implementation of Finite-Field Arithmetic

2 Cha pte r O n e

)
Definition 1.4 (integer division Given two integers x and y, with
y > 0, there exist two integers q (the quotient) and r (the remainder ) such
that

x = qy + r where 0 ≤ r < y if x ≥ 0 and −y < r ≤ 0 if x < 0
It can be proven that q and r are unique. Then (notation)

r = x rem y q = x/y

Examples 1.1
1. x = −16, y = 3:
−16 mod 3 = 2, −16 div 3 = −6, −16 = −6 3 + 2
−16 rem 3 = −1, −16/3 = −5, −16 = −5 3 + (−1)
2. x = −15, y = 3:
−15 mod 3 = 0, −15 div 3 = −5, −15 = −5 3 + 0
−15 rem 3 = 0, −15/3 = −5, −15 = −5 3 + 0

Definitions 1.5
1. Given two integers x and y, z is the greatest common divisor of
x and y if
z is a natural number (nonnegative integer),
z divides both x and y,
any other common divider of x and y is also a divider of z.
Notation: z = gcd(x, y).

2. Given two integers x and y, they are said to be relatively prime
if gcd(x, y) = 1.
3. An integer p > 1 is said to be prime if its only positive divisors
are 1 and p.

1.1.2 Euclidean Algorithms
Given two natural numbers x and y, the Euclidean algorithm for natural
numbers computes gcd(x, y). It is based on a series of integer divisions:

r (i − 1) = q (i )r (i ) + r (i + 1) where 0 ≤ r (i + 1) < r (i )
Observe that any divider of r (i − 1) and r (i ) is also a divider of
r (i ) and r (i + 1) so that
gcd(r (i − 1), r (i )) = gcd(r (i), r (i + 1))

Initially

r (0) = x and r (1) = y