21-06-2014, 01:47 PM
Modified Redundant Representation for Designing Arithmetic Circuits with Small Complexity
[attachment=65152]
Abstract
A new GF redundant representation is presented. Squaring in the representation
is almost cost-free. Based on the representation, two multipliers are proposed. The XOR gate complexity of the first multiplier is lower than a recently proposed normal basis multiplier when
CN (the complexity of the basis) is larger than 3n-1.
Introduction
Efficient GF arithmetic operations are very important in many applications, e.g., coding
theory and cryptosystems. When GF(2n) elements are represented in GF(2)-bases, polynomial bases, triangular bases, dual bases and normal bases (NB) are of particular interest. NB has received considerable attention because the squaring in NB is simply a cyclic shift of the coordinates of the element and, thus, it has found application in computing inverses and
exponentiations. Another way to represent field elements is using redundant representation. GF(2n) multiplication algorithms based on redundant representation have been proposed in [1], [2], [3], [4] and [5]. They are essentially redundant polynomial bases representations, and the number of redundant bits is often large.
In this paper, a new redundant representation of GF(2n) is presented. Field elements are represented in n+1 bits, i.e., there is only a single redundant bit. Arithmetic operations in the representation are similar to those of the NB, e.g., the squaring operation is simply a cyclic shift
of all but one coordinate. Based on this representation, we propose two GF(2n) parallel multipliers.
The first multiplier uses the redundant normal basis representation. It consists of n2 2-input AND
Redundant Normal Bases
In this section, we present a parallel multiplier based on RNB. Let M={ 20 ,21 ,...,2n 1 ,1} be a
RNB and A' n 1 2i and B' b ' n 1 2i be two field elements represented in M.
a ' a ' b '
n i n i
i 0 i 0
2 0 21 2n 1 n 1
Since N={ 2i 1. Multiplying both
, ,..., } is a NB, it is well known that Tr( )
i 0
' n 1 ' 2i
sides of this identity by an-1', we have an 1 i 0 an 1 0 . Thus A' can also be represented as:
n 2 ' ) 2i . (1)
A' (an ' an 1 ' ) (ai ' an 1
i 0
Now we define ai=ai'+an-1', where i=0,1,...,n. Please note that an-1=0. Using this definition, we
have A'=an+A, where A n 2 2i . Similarly, we have B'=bn+B, where n 2 2i .
a B b
i i
i 0 i 0
The coordinate representation of D=(d0,d1,...,dn-1,dn)=A'B' w.r.t. M can be computed by the
following formula:
Conclusions
In this article, a new redundant basis representation of GF(2n) has been presented. The main advantage of the proposed representation is that it possesses many properties of normal bases. Since there is only a single redundant bit, the proposed representation has the lowest redundancy. When a finite field processor is implemented for large value of n. True bit-parallel input/output operations are difficult. A more practical approach to these input/output operations is to split the operand into several blocks. The block size w can be 8, 16, 32, or 64 bits to make the processor chip compatible with other devices [8]. So if w n, then no additional cost is needed to transport the single redundant bit.
Based on this representation, we have proposed two GF(2n) parallel multipliers: the RNB
12
multiplier and the RPNB multiplier. The XOR gate complexity of the RNB multiplier is lower than the best known NB multiplier, namely RR_MO multiplier, when CN is larger than 3n-1. The
architecture of the RPNB multiplier is similar to the RNB multiplier. Although the RPNB
provides a new way to design GF(2n) multipliers, there is still an important problem need to be settled, i.e., how to construct a RPNB of low complexity?
[attachment=65152]
Abstract
A new GF redundant representation is presented. Squaring in the representation
is almost cost-free. Based on the representation, two multipliers are proposed. The XOR gate complexity of the first multiplier is lower than a recently proposed normal basis multiplier when
CN (the complexity of the basis) is larger than 3n-1.
Introduction
Efficient GF arithmetic operations are very important in many applications, e.g., coding
theory and cryptosystems. When GF(2n) elements are represented in GF(2)-bases, polynomial bases, triangular bases, dual bases and normal bases (NB) are of particular interest. NB has received considerable attention because the squaring in NB is simply a cyclic shift of the coordinates of the element and, thus, it has found application in computing inverses and
exponentiations. Another way to represent field elements is using redundant representation. GF(2n) multiplication algorithms based on redundant representation have been proposed in [1], [2], [3], [4] and [5]. They are essentially redundant polynomial bases representations, and the number of redundant bits is often large.
In this paper, a new redundant representation of GF(2n) is presented. Field elements are represented in n+1 bits, i.e., there is only a single redundant bit. Arithmetic operations in the representation are similar to those of the NB, e.g., the squaring operation is simply a cyclic shift
of all but one coordinate. Based on this representation, we propose two GF(2n) parallel multipliers.
The first multiplier uses the redundant normal basis representation. It consists of n2 2-input AND
Redundant Normal Bases
In this section, we present a parallel multiplier based on RNB. Let M={ 20 ,21 ,...,2n 1 ,1} be a
RNB and A' n 1 2i and B' b ' n 1 2i be two field elements represented in M.
a ' a ' b '
n i n i
i 0 i 0
2 0 21 2n 1 n 1
Since N={ 2i 1. Multiplying both
, ,..., } is a NB, it is well known that Tr( )
i 0
' n 1 ' 2i
sides of this identity by an-1', we have an 1 i 0 an 1 0 . Thus A' can also be represented as:
n 2 ' ) 2i . (1)
A' (an ' an 1 ' ) (ai ' an 1
i 0
Now we define ai=ai'+an-1', where i=0,1,...,n. Please note that an-1=0. Using this definition, we
have A'=an+A, where A n 2 2i . Similarly, we have B'=bn+B, where n 2 2i .
a B b
i i
i 0 i 0
The coordinate representation of D=(d0,d1,...,dn-1,dn)=A'B' w.r.t. M can be computed by the
following formula:
Conclusions
In this article, a new redundant basis representation of GF(2n) has been presented. The main advantage of the proposed representation is that it possesses many properties of normal bases. Since there is only a single redundant bit, the proposed representation has the lowest redundancy. When a finite field processor is implemented for large value of n. True bit-parallel input/output operations are difficult. A more practical approach to these input/output operations is to split the operand into several blocks. The block size w can be 8, 16, 32, or 64 bits to make the processor chip compatible with other devices [8]. So if w n, then no additional cost is needed to transport the single redundant bit.
Based on this representation, we have proposed two GF(2n) parallel multipliers: the RNB
12
multiplier and the RPNB multiplier. The XOR gate complexity of the RNB multiplier is lower than the best known NB multiplier, namely RR_MO multiplier, when CN is larger than 3n-1. The
architecture of the RPNB multiplier is similar to the RNB multiplier. Although the RPNB
provides a new way to design GF(2n) multipliers, there is still an important problem need to be settled, i.e., how to construct a RPNB of low complexity?