Page 149 - Hardware Implementation of Finite-Field Arithmetic

132 Cha pte r F i v e

when 2 => current_state <= 3; --capture operands
when 3 => current_state <= 4; --start operations
when 4 => if (done_sq = ‘1’ and
(ee(0)= ‘0’ or done_mult = ‘1’)) then current_state
<= 5; end if;
when 5 => if count = N-1 then current_state <= 0;
else current_state <= 3; end if;
end case;
end if;
end process control_unit;

5.4 Optimal Extension Fields
Optimal extension fields (OEFs) are a family of extension fields GF(p )
m
with special properties defined as follows ([BP01], [Bai98], [GG03],
[GKP04]):

m
Definition 5.1 An optimal extension field is a finite field GF(p ) such
that:
1. The prime p is a pseudo-Mersenne prime of the form p = 2 ± b
n

with log (b) ≤⎣n/2⎦.
2
m
2. An irreducible binomial f(x) = x – c exists over GF(p).
The following theorem from [LN83] describes the cases when an
irreducible binomial exists:
Theorem 5.1 Let m ≥ 2 be an integer and c ∈ GF(p). Then the
binomial x − c is irreducible in GF(p) if and only if the following
m
two conditions are satisfied: (i) each prime factor of m divides the
order e of c over GF(p), but not (p − 1)/e; (ii) p ≡ 1 mod 4 if m ≡ 0
mod 4.
An important corollary is also given in [Jun93]:

Corollary 5.1 Let c be a primitive element for GF(p) and let m be a
m
divisor of p − 1. Then the polynomial x − c is irreducible.
It must be noted that irreducible binomials do not exist over
GF(2). Furthermore, the following corollary follows directly from the
above, since p − 1 is always an even number [Bai98]:

2
Corollary 5.2 Let c be a primitive element for GF(p). Then x − c is
irreducible over GF(p).
There are two special cases of OEFs which yield additional
arithmetic advantages, called Type I and Type II OEFs [BP01]. A
n
Type I OEF has p = 2 ± 1. This OEF allows subfield modular reduc-
tion with low complexity. For Elliptic Curve Cryptography (ECC),