Page 78 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 3

mod m Operations

lgorithms for executing arithmetic operations over the finite
ring Z are presented, and the corresponding circuits are syn-
m
Athesized. The operations under consideration are the addition,
subtraction, multiplication, and exponentiation mod m. Obviously a
straightforward solution consists of executing the same operations
with integers, and then reducing mod m (Chap. 2) the previously ob-
tained results. Nevertheless more efficient algorithms can be used.
Among others the Montgomery arithmetic is introduced and applied
to the multiplication and exponentiation operations. All the mentioned
algorithms have been synthesized and implemented within field pro-
grammable components.

3.1 Addition mod m
Given two natural numbers x and y belonging to Z = {0, 1, . . . , m − 1},
m
compute z = (x + y) mod m. Taking into account that
0 ≤ x + y < 2m
z must be equal to either x + y or x + y − m. The following algorithm
computes z.

Algorithm 3.1—mod m addition
z1 := x + y; z2 := z1 - m;
if z2 >= 0 then z := z2; else z := z1; end if;

Algorithm 3.1 is slightly modified in order to get a more efficient
circuit. Assume that m is a k-bit natural and define
k
k
z = (z mod 2 ) + (2 − m) (3.1)
2 1
(instead of z − m). Then, consider three cases:
1
k
k
k
k
1. If z < m, so that z < 2 , then z = z + (2 − m) < m + (2 − m) = 2 ;
1 1 2 1
k
k
k
k
2. If m ≤ z < 2 then z = z + (2 − m) ≥ m + (2 − m) = 2 , and z
1 2 1 2
mod 2 = z − m;
k
1
k
k
k
3. If 2 ≤ z , so that m < z , then z = (z – 2 ) + (2 − m) = z – m <
1 1 2 1 1
k
k
2m – m = m < 2 , and z mod 2 = z − m.
2 1
61