Page 21 - Hardware Implementation of Finite-Field Arithmetic

4 Cha pte r O n e

Algorithm 1.1—Extended Euclidean algorithm
if x = 0 then z := y; b := 0; c := 1;
elsif y = 0 then z := x; b := 1; c := 0;
else
r_i := x; r_iplus1 := y; b_i := 1; c_i := 0; b_iplus1 :=
0; c_iplus1 := 1;
while r_iplus1 > 0 loop
q := r_i/r_iplus1; r_iplus2 := r_i mod r_iplus1;
b_iplus2 := b_i - b_iplus1*q; c_iplus2 := c_i - c_
iplus1*q;
r_i := r_iplus1; r_iplus1 := r_iplus2;
b_i := b_iplus1; b_iplus1 := b_iplus2;
c_i := c_iplus1; c_iplus1 := c_iplus2;
end loop;
z := r_i; b := b_i; c := c_i;
end if;
Example 1.3 Let r = x = 230490; r = y = 43290; b = c = 1; b = c = 0;
i i + 1 i i + 1 i + 1 i
Step 1

q = 230490/43290 = 5; r = 230490 mod 43290 = 14040
i + 2
b = 1– 0 ⋅ 5 = 1; c = 0 – 1 ⋅ 5 = −5
i + 2 i + 2
r = 43290; r = 14040
i i + 1
b = 0; b = 1
i i + 1
c = 1; c = −5
i i + 1
Step 2
q = 43290/14040 = 3; r = 43290 mod 14040 = 1170
i + 2
b = 0 − 1 ⋅ 3 = −3; c = 1 + 5 ⋅ 3 = 16
i + 2 i + 2
r = 14040; r = 1170
i i + 1
b = 1; b = −3
i i + 1
c = −5; c = 16
i i + 1
Step 3
q = 14040/1170 = 12; r = 14040 mod 1170 = 0
i + 2
b = 1 + 3 ⋅ 12 = 37; c = −5 − 16 ⋅ 12 = −197
i + 2 i + 2
r = 1170; r = 0
i i + 1
b = −3; b = 37
i i + 1
c = 16; c = −197
i i + 1
b = b = −3; c = c = 16; gcd(230490, 432900) = z = r = 1170
i i i
= −3 ⋅ 230490 + 16 ⋅ 43290
1.1.3 Congruences
Definition 1.6 Given two integers x and y, and a positive integer n, x
is congruent to y modulo n if n divides the difference (x − y).