Page 42 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 2

mod m Reduction

rithmetic operations over the finite ring Z = {0, 1, . . . , m − 1}
m
are used as computation primitives for executing numerous
Acryptographic algorithms, especially those related with the
use of public keys (asymmetric cryptography). Classical examples
are ciphering/deciphering, authentication, and digital signature
protocols based on RSA-type or elliptic-curve algorithms. One of the
basic operations is the modulo m reduction. Given two naturals x and
m, it computes z = x mod m. Combined with operations over the set Z
of integers (sum, subtraction, product, and so on) it allows one to
perform the same operations over Z .
m
In this chapter several algorithms are described, namely, the integer
ik
k
division, the reduction mod B − a, the precomputation of B mod m, and
the Barrett algorithm. All the mentioned algorithms have been synthe-
sized and implemented within field programmable components.

2.1 Integer Division
A straightforward method for computing z = x mod m consists in
performing the integer division of x by m, that is,

x = qm + z z < m
For that purpose, any division algorithm can be used.

2.1.1 Digit Recurrence Algorithms
Digit recurrence algorithms ([Par00], [EL04], [DBS06]) are based on
the following property:

Property 2.1 Given a natural y and an integer s belonging to the
range −2y ≤ s < 2y, the equation

s = qy + r (2.1)

has at least one solution with q ∈ { − 1, 0, 1} and − y ≤ r < y.
Proof The possible values of q and r, in function of s and y, are
shown in Fig. 2.1, a so-called Robertson diagram.
25