PARALLEL MULTIPLICATION IN F

USING CONDENSED

MATRIX REPRESENTATION

Christophe Negre

Equipe DALI, LP2A, Universit

e de Perpignan

avenue P. Alduy, 66 000 Perpignan, France

Keywords:

Finite ﬁeld, multiplication, matrix representation, irreducible trinomial.

Abstract:

In this paper we explore a matrix representation of binary ﬁelds F

deﬁned by an irreducible trinomial

P = X

+ X

+ 1. We obtain a multiplier with time complexity of T

+ (⌈log

(n)⌉)T

and space

complexity of (2n − 1)n AND and (2n − 1)(n − 1) XOR . This multiplier reaches the lower bound on time

complexity. Until now this was possible only for binary ﬁeld deﬁned by AOP (Silverman, 1999), which are

quite few. The interest of this multiplier remains theoretical since the size of the architecture is roughly two

times bigger than usual polynomial basis multiplier (Mastrovito, 1991; Koc and Sunar, 1999).

1 INTRODUCTION

A binary ﬁeld F

= F

[X]/(P ) is a set of 2

ele-

ments in which we can do all the basic arithmetic op-

eration like addition, subtraction, multiplication and

inversion modulo an irreducible binary polynomial P .

Finite ﬁeld arithmetic is widely used in cryptographic

applications (Miller, 1985) and error-correcting code

(Berlekamp, 1982). For these applications, the most

important ﬁnite ﬁeld operation is the multiplication.

The representation of binary ﬁeld elements have a

big inﬂuence on the efﬁciency of ﬁeld arithmetic. Un-

til now, ﬁeld elements were represented as sum of ba-

sis elements: the basis is composed by n elements

, . . . , B

∈ F

, in this situation an element U

in F

is written as U = u

, + · · · + u

with

∈ {0, 1}.

The most used bases are polynomial bases (Mas-

trovito, 1991; Koc and Sunar, 1999; Chang et al.,

2005) and normal bases (Wu and Hasan, 1998; Koc

and Sunar, 2001).

Our purpose here is to investigate a new represen-

tation: the matrix representation. We will focus on

ﬁeld deﬁned by a trinomial F

= F

[X]/(P ) with

P = X

+ X

+ 1. In the matrix representation an

element U of F

is represented by the n

coefﬁcients

of a n × n matrix M

. The additions of two elements

U and V simply consists to add the two matrices M

and M

and to multiply U and V it consists to multi-

ply the matrix product M

· M

This gives a faster multiplication than multiplica-

tion using basis representation: a parallel multiplier

associated to a matrix representation has a time com-

plexity of T

+ (⌈log

(n)⌉)T

, whereas in basis rep-

resentation, for ﬁeld deﬁned by a trinomial (Koc and

Sunar, 1999; Mastrovito, 1991), the time complexity

is generally equal to T

+ (2 + ⌈log

(n)⌉)T

. The

major drawback of this method is due to the length of

the representation which requires n

coefﬁcients, and

provides parallel multiplier with a cubic space com-

plexity in n. But if we carefully select a subset of the

matrix coefﬁcients, the number of distinct coefﬁcients

in each matrix M

becomes small: in our situation it

is equal to (2n − 1). In other words we condense the

matrix representation in (2n − 1) distinct coefﬁcients

to decrease the space complexity.

The paper is organized as follows : in the ﬁrst sec-

tion we recall the method of Koc and Sunar (Koc and

Sunar, 1999) for ﬁnite ﬁeld multiplication modulo tri-

nomial. They perform the reduction modulo the trino-

mial on a matrix and then compute a matrix-vector to

get the product of two elements. In the second section

we study the possibility to use the matrix constructed

with Koc and Sunar’s method to represent ﬁnite ﬁeld

elements. After that we evaluate the complexity of a

parallel multiplier in this matrix representation. Next,

we study a condensed matrix representation and the

associated multiplier. We ﬁnally give a small exam-

ple of our matrix multiplier and ﬁnish by a complexity

comparison and a brief conclusion.

254

Negre C. (2006).

PARALLEL MULTIPLICATION IN F2n USING CONDENSED MATRIX REPRESENTATION.

In Proceedings of the International Conference on Security and Cryptography, pages 254-259

DOI: 10.5220/0002096402540259

 SciTePress

2 MATRIX REPRESENTATION IN

POLYNOMIAL BASIS

Let P = X

+ X

+ 1 be an irreducible polynomial

in F

[X]. Without loss of generality we can assume

k ≤

since when X

+ X

+ 1 is irreducible, the

reciprocal polynomial X

+ X

n−k

+ 1 is also irre-

ducible. Furthermore, in this paper we will always

suppose for simplicity k ≥ 2.

An element U ∈ F

= F

[X]/(P ) is a polyno-

mial of degree n − 1. To compute the product of two

elements U and V in F

we ﬁrst compute the product

of polynomial

W = UV =

n−1

i=0

n−1

i=0

. (1)

This product can be done by a matrix vector prod-

uct N

· V where N

is given below

1 →

X →

n−2

→

n−1

→

n−1

→

2n−2

→

2n−1

→

0 · · · 0 0

· · · 0 0

n−2

n−3

· · · u

n−1

n−2

· · · u

0 u

n−1

· · · u

0 0 · · · u

0 0 · · · 0 u

n−1

0 0 · · · 0 0

The product W = UV contains monomials X

with larger degree than n, i.e., with n ≤ i ≤ 2n − 2.

These monomials must be reduced modulo P =

+ X

+ 1. To perform this reduction we will

use the following identity modulo P for each i ≥ n

= X

i−(n−k)

+ X

i−n

mod P. (2)

For example if P = X

+1 then we have X

+ 1 mod P and in the same way X

= X

+ X

mod P and so on.

Koc and Sunar in (Koc and Sunar, 1999) have pro-

posed to perform the reduction modulo P on the line

of the matrix N

instead of performing the reduction

on the polynomial W = UV .

To describe this reducing process we need to state

some notations. If M is a n × 2n matrix, we denote

by (M )

the top part of the matrix M constituted by

the n ﬁrst lines. We will denote also (M )

the matrix

constituted by the n last lines. And ﬁnally, we will

denote M[↑ s] the matrix shifted up by s rows from

M, and M[↓ s] the matrix shifted down by s rows.

From equation (2) the line corresponding to X

for

i ≥ n are pushed up to the lines corresponding to

i−n

and X

i−n+k

. Using the previous notation, this

procedure modiﬁes the matrix N

as follows

)

← (N

)

+ (N

)

+ (N

)

[↓ k] (3)

)

← (N

)

[↑ (n − k)] (4)

If we denote by S the low part of N

, and by T the

top part of N

S =







0 u

n−1

n−2

· · · u

0 0 u

n−1

· · · u

0 0 0 · · · u

n−1

0 0 0 0 0







, T =







0 · · · 0

· · · 0

n−1

n−2

· · ·u







we can rewrite equation (3) and (4) as

)

= T + S + S[↓ k],

)

= S[↑ (n − k)].

(5)

Now, since we assumed k ≥ 2, in the

new expression of N

, the lines corresponding

to X

, . . . , X

n+k−2

contains non-zero coefﬁcients.

Thus, we have to reduce a second time N

with the

same method. We set S

′

= S[↑ (n − k)] = (N

)

and the second reduction provides

)

= T + S + S

′

+ (S + S

′

)[↓ k]

)

= 0.

(6)

We ﬁnally have the expression of M

= (N

)

the

reduced form of N

n−1

· · · · · · · · · u

′

k−1

. . . . . . u

′

n−1

· · · · · · · · · u

′

k−1

. . . u

′

k−2

· · · · · · u

n−1

· · · · · · · · · u

′

k−1

k−2

· · · · · · u

n−1

· · · · · · · · · u

′

k−1

′

k−2

· · · · · · u

′

′′

n−1

· · · · · · u

′′

k+1

′

k−1

· · · · · · · · · u

′

′′

n−1

· · · u

′′

k+2

n−2

· · · · · · u

′

k−1

· · · · · · · · · u

′

′′

n−1

· · · · · · · · · u

′

k−1

· · · · · · · · · u

′

(7)

where

′

= u

+ u

i+(n−k)

for 0 ≤ i < k,

′′



+ u

i−k

+ u

i+n−2k

for k ≤ i < 2k,

+ u

i−k

for 2k ≤ i < n.

The method of Koc and Sunar (Koc and Sunar,

1999) to compute the product UV mod P , ﬁrst con-

sists to compute the coefﬁcients u

′

and u

′′

of M

and

after that to perform the matrix-vector product M

·V

to obtain U V mod P . This multiplier computes the

product in time T

+ (⌈log

(n)⌉ + 2)T

using a par-

allel architecture.

If we know the coefﬁcients u

, u

′

and u

′′

we avoid

the delay to compute these coefﬁcients. In this sit-

uation the product could be done in time T

PARALLEL MULTIPLICATION IN F2n USING CONDENSED MATRIX REPRESENTATION

255

⌈log

(n)⌉T

. This remark pushed us to try to keep

the ﬁeld elements U ∈ F

expressed by the matrix

(i.e., in this case we always know the coefﬁcients

, u

′

and u

′′

, and we don’t have to compute it before

the multiplication) and try to use this representation

to implement ﬁnite ﬁeld arithmetic.

Deﬁnition (Matrix Representation). Let F

[X]/(P ) where P = X

+ X

+ 1 with 2 ≤

k ≤

. The matrix representation of an element

U =

n−1

i=0

of the ﬁeld F

is the matrix given

in equation (7) expressed in term of the coefﬁcients

, u

′

and u

′′

The next section is devoted to explain how to add

and multiply ﬁeld elements in matrix representation.

3 FIELD ARITHMETIC IN

MATRIX REPRESENTATION

Let F

= F

[X]/(P ) where P is an irreducible tri-

nomial P = X

+ X

+ 1 with 2 ≤ k ≤

The following Theorem shows that, if the elements

U ∈ F

are represented by their associated matrix

, ﬁnite ﬁeld arithmetic corresponds to classical

n × n matrix arithmetic.

Theorem 1. Let F

= F

[X]/(P ) where P is an

irreducible trinomial P = X

+ X

+ 1 with 2 ≤

k ≤

. Let U =

n−1

i=0

and V =

n−1

i=0

be two elements in F

and M

their cor-

responding matrix deﬁned in (7). If W

= U + V

mod P and W

= UV mod P we have

= M

+ M

, (8)

= M

· M

. (9)

Proof. Using equation 7, it is clear that to show the

assertion for W

, it is sufﬁcient to show that

= u

+ v

′

= u

′

+ v

′

′′

= u

′′

+ v

′′

The identity on w

is trivial since W

= U + V

mod P . For w

′

we have

′

= w

i+(n−k)

= (u

)+(u

i+(n−k)

By rearranging this expression, we get

′

= (u

+ u

i+(n−k)

) + (v

+ v

i+(n−k)

) = u

′

+ v

′

A similar proof can be done to show that w

′′

= u

′′

For the assertion on M

it is a little bit more dif-

ﬁcult. We remark that from the result of section 2, for

every elements Z ∈ F

the product V Z in F

given by M

· Z and the product W

Z by M

· Z.

Thus we get for every Z ∈ F

that

· Z = W

Z = U V Z

= M

· (V Z) = M

· (M

· Z)

= (M

· M

) · Z

This implies that (M

−M

)·Z = 0 for each

Z in F

, but this means that (M

− M

) is the

zero matrix. In other words we have M

= M

·M

as required.

For a more general proof see (Lidl and Niederreiter,

1986). The following example illustrates the Theo-

rem 1.

Example 1. We consider the ﬁeld F

[X]/(X

+ X

+ 1) and let U =

n−1

i=0

an element of F

. From equation (7) we get the fol-

lowing expression of M







′

′′

′

′′

′

′′

′

′′

′







with u

′

= u

+ u

, u

′

= u

+ u

, u

′

= u

+ u

and

′′

= u

′

, u

′′

= u

, u

′′

= u

For U = 1 + X + X

and V = X

+ X

obtain the following matrices







1 0 0 1 0 0 1

1 1 0 0 1 0 0

0 1 1 0 0 1 0

0 0 1 0 0 0 0

1 0 0 1 0 0 0

0 1 0 0 1 0 0

0 0 1 0 0 1 0







, M







0 0 1 0 1 1 1

0 0 0 1 0 1 1

1 0 0 0 1 0 1

1 1 1 0 1 0 1

0 1 1 1 0 1 0

1 0 1 1 1 0 1

0 1 0 1 1 1 0







Now we add M

and M

to get the matrix M

+ M

of W

= U + V = X

+ X

+ X + 1 mod P and we multiply M

and M

to get the matrix M

= M

· M

of W

= UV =

+ X

+ 1 mod P







1 0 1 1 1 1 0

1 1 0 1 1 1 1

1 1 1 0 1 1 1

1 1 0 0 1 0 1

1 1 1 0 0 1 0

1 1 1 1 0 0 1

0 1 1 1 1 0 0







, M







1 0 0 1 1 0 0

0 1 0 0 1 1 0

0 0 1 0 0 1 1

1 0 0 0 1 0 1

1 1 0 0 0 1 0

0 1 1 0 0 0 1

0 0 1 1 0 0 0







4 PARALLEL MULTIPLICATION

IN MATRIX REPRESENTATION

Let us now study the architecture of the multiplier as-

sociated to the matrix representation. We ﬁx U, V ∈

SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY

256

and M

their associated matrix. Let

W = UV be the product of U and V in F

and

its associated matrix . We will note L

) for

i = 0, . . . , n − 1 the line of M

and C

) for

j = 0, . . . , n − 1 the columns of M

The coefﬁcient Coeff

i,j

) of index (i, j) of

is then computed as a line-column matrix prod-

uct (in the sequel we will call this operation a scalar

product)

Coeff

i,j

) = L

) · C

)

n−1

ℓ=0

Coeff

i,ℓ

)Coeff

ℓ,j

)

(10)

A scalar product (10) can be done in time T

⌈log

(n)⌉T

, where T

is the delay for an AND gate

and T

for an XOR gate, using parallel AND gates

and a binary tree of XOR.

Consequently, if all these scalar products are done

in parallel, one can compute the product M

of M

and M

in time T

+ ⌈log

(n)⌉T

. So at this point

we reach the lower bound on time complexity in bi-

nary ﬁeld multiplication.

The major drawback of this approach is that

we have to compute n

coefﬁcients Coeff

i,j

The space complexity is thus roughly n

AND and

XOR which is widely too big and not practical.

But in fact, we did not use the fact that the number

of distinct coefﬁcients in each matrix M

, M

and

is quite small. A lot of scalar products can be

avoided, this motivates the use of a condensed matrix

representation.

5 CONDENSED MATRIX

REPRESENTATION

The set of coefﬁcients of the matrix M

for a given U

is quite small: it consists of the n bits u

, the k bits u

′

and the (n− k − 1) bits u

′′

. The matrix representation

can be condensed in this three set of coefﬁcients.

Deﬁnition (Condensed Matrix Representation). We

consider the ﬁeld F

= F

[X]/(P ) where P is an

irreducible trinomial, and let U =

n−1

i=0

be an

element of F

. The condensed matrix representation

of U is CMR(U) = (U, U

′′

, U

′′′

) such that

U = (u

, . . . , u

n−1

′

= (u

′

, . . . , u

′

k−1

), where u

′

= u

+ u

i+(n−k)

′′

= (u

′′

, . . . , u

′′

), where

• u

′′

= u

+ u

i−k

+ u

i+n−2k

for i = k +

1, . . . , 2k − 1,

• u

′′

= u

+ u

i−k

for i = 2k, . . . , n − 1.

The condensed matrix representation of U contains

all the distinct coefﬁcients of the matrix M

. We can

thus reconstruct each line and each column of matrix

Construction of the lines of M

. We note L

)

the line of M

for i = 0, . . . , n − 1. Using the

expression of M

of equation (7), we get the fol-

lowing expression of these lines of M

in term of

the CMR of U in the Table 1.

Table 1: Lines of M

i=0,...,k−2 L

[

i−1

···u

n−1

···u

′

k−1

...u

′

i+1

]

i=k−1 L

k−1,A

[

k−1

k−2

···u

n−1

···u

]

i=k,...n−2 L

[

...u

′

k−1

...u

′

′′

n−1

...u

′′

i+1

]

i=n−1 L

[

n−1

...u

′

k−1

...u

′

]

Construction of the columns of M

. We note

) the columns of M

for j = 0, . . . , n − 1.

From (7) we get the Table 2 of the columns of M

where the expression of C

) are given in term

of the CM representation of U.

Now using these descriptions of the lines and the

columns of the matrix M

we can easily express the

multiplication in the condensed matrix representation.

5.1 Multiplication in Condensed

Matrix Representation

Let U and V be two elements of F

given

by their respective condensed matrix representa-

tion CMR(U) = (U, U

′

, U

′′

) and CMR(V ) =

(V, V

′

, V

′′

). As stated in the previous section, with

the CMR representation of U and V we can easily

construct the lines and columns of M

and M

. We

want to compute the coefﬁcients of the condensed

matrix representation of the product W = U V in

= F

[X]/(X

+ X

+ 1). To do this ﬁrst re-

call that, from Theorem 1, for each 0 ≤ i, j ≤ n − 1

we have

Coeff

i,j

) = L

) · C

). (11)

To get the CMR of W we need only to compute the

coefﬁcients W, W

′

, W

′′

of M

• Computing the coefﬁcients of W . The coefﬁcients

of CMR(W ) are in the ﬁrst column of M

This means that

= Coeff

0,j

) = L

) · C

• Computing the coefﬁcients of W

′

and W

′′

. If we

look at equation (7) we can see that W

′

and W

′′

appears in the line L

), i.e.,

′

= Coeff

k,j

) for 1 ≤ j ≤ k,

′′

= Coeff

k,j

) for k + 1 ≤ j ≤ n − k.

PARALLEL MULTIPLICATION IN F2n USING CONDENSED MATRIX REPRESENTATION

257

Table 2: The columns of M

j = 0 C

) =

[

· · ·· · ·· · ·u

n−1

]

j = 1, . . . , k − 1 C

) =



n−j

· · ·u

n−1

· · ·u

k−j−1

′

k−j

· · ·u

′

k−1

· · ·u

n−j−1



j = k, . . . , n − k C

) =



n−j

· · ·u

n−j+k−1

′′

n−j+k

· · ·u

′′

n−1

′

· · ·u

′

k+1

· · ·u

n−j−1



j = n − k + 1, . . . , n − 1 C

) =



′

n−j

· · ·u

′

k−1

· · ·u

n−j+k−1

′′

n−j+k

· · ·u

′′

n−1

′

· · ·u

′

n−j−1



Now using (11) we get the following expression for

′

and w

′′

′

= L

) · C

) for 1 ≤ j ≤ k,

′′

= L

) · C

) for k + 1 ≤ j < n.

These operations can be done in a parallel hardware

architecture. Specially each coefﬁcient w

, w

′

and w

′

we perform in parallel a scalar product through paral-

lel AND gates, and a binary tree of XOR.

Complexity. Let us evaluate the complexity of this

multiplier. It consists in (2n−1) scalar products done

in parallel:

• n for the coefﬁcients w

, j = 0, . . . , n − 1,

• n − 1 for the w

′

, with j = 0, . . . , k − 1 and w

′′

with j = k + 1, . . . , n − 1.

Since one scalar product requires n AND and (n − 1)

XOR, the overall space complexity of the multiplier is

equal to (2n − 1)n AND and (2n − 1)(n − 1) XOR .

For the time complexity, since the computation of the

coefﬁcients of CMR(W) are done in parallel, the time

complexity is equal to the delay of only one scalar

product. But this delay is equal to T

+⌈log

(n)⌉T

6 EXAMPLE

We consider the ﬁeld F

= F

[X]/(X

+ X

+ 1).

Let U = u

+ u

X + u

+ u

∈ F

The condensed matrix representation of U is given by

the three vectors

U = (u

, u

′

= (u

′

, u

′

), U

′′

= (u

′′

, u

′′

where the u

′

and u

′′

are deﬁned by

′

= u

+ u

, u

′

= u

+ u

′′

= u

+ u

, u

′′

= u

+ u

Using the general formula (7) for M

we get that

is as follows







′

′′

′

′′

′







Now if U = 1 + X

+ X

and V = X + X

their

condensed matrix representation are

CMR(U) =



U = (1, 0, 0, 1, 1),

′

= (0, 1), U

′′

= (0, 1).

CMR(V ) =



V = (0, 1, 1, 0, 0),

′

= (0, 1), V

′′

= (1, 1).

Using the vectors U, U

′

, U

′′

we can construct M

and

with the vectors V, V

′′

and V

′′

we can construct M







1 1 1 0 1

0 1 1 1 0

0 1 0 1 0

1 0 1 0 1

1 1 0 1 0







, M







0 0 0 1 1

1 0 0 0 1

1 1 0 1 1

0 1 1 0 1

0 0 1 1 0







Let W = U V be the product of U and V in F

We compute the condensed matrix representation of

W by multiplying well chosen line of M

and well

chosen line of M

as described in the previous sec-

tion.

We compute w

by multiplying L

) the ﬁrst

line of M

with C

) the ﬁrst column of M

= L

) · C

)

= [

1 1 1 0 1

] ·

[

0 1 1 0 0

] = 0

For w

, i = 1, 2, 3, 4 we have

= L

) · C

) = 0,

= L

) · C

) = 1,

= L

) · C

) = 1,

= L

) · C

) = 1.

For the coefﬁcients w

′

we do

′

= L

) · C

) = 1,

′

= L

) · C

) = 1.

And ﬁnally for the coefﬁcients w

′′

we have

′′

= L

) · C

) = 0,

′′

= L

) · C

) = 0.

We can easily check that the coefﬁcients w

, w

′

and

′′

are the correct coefﬁcients of the condensed ma-

trix representation of the product of U and V in F

SECRYPT 2006 - INTERNATIONAL CONFERENCE ON SECURITY AND CRYPTOGRAPHY

258

Table 3: Complexity.

Algorithm Space complexity Time complexity

# AND # XOR

CMR for X

+ X

+ 1 (2n − 1)n (2n − 1)(n − 1) T

+ (⌈log

(n)⌉)T

with 2 ≤ k ≤

(this paper)

PB for X

+ X

+ 1 with 2 ≤ k ≤

− k) T

+ (2 + ⌈log

(n)⌉)T

(Koc and Sunar, 1999)

PB for X

+ X + 1 n

− 1) T

+ (1 + ⌈log

(n)⌉)T

(Koc and Sunar, 1999)

PB for AOP (Chang et al., 2005) (

+ 2n + 1)

3(n+2)

+ (1 + ⌈log

(n)⌉)T

NB of Type I (Wu and Hasan, 1998) n

− 1) T

+ (1 + ⌈log

(n)⌉)T

NB of type II (Koc and Sunar, 2001) n

− n)

+ (1 + ⌈log

(n)⌉)T

7 CONCLUSION

We have presented in this paper a new multiplier ar-

chitecture for binary ﬁeld F

generated by a trino-

mial X

+1 with 2 ≤ k ≤

using a condensed

matrix representation. This multiplier is highly paral-

lelizable.

In Table 3 we give the complexity of our architec-

ture, and also the complexity of different multiplier

architectures proposed in the literature for ﬁeld F

We see that the use of a condensed matrix repre-

sentation provides a multiplication which is the faster

among all previously proposed multiplier known by

the author. The gain on time complexity for multipli-

cation modulo trinomials X

+ X

+ 1 with crypto-

graphic size n ∼ 160 is around 20% when k ≥ 2

compared to polynomial basis multiplier and 10%

compared to normal basis multiplier or AOP polyno-

mial bases. But we have to pay a big price for this

improvement : the condensed matrix representation

parallel multiplier has a space complexity which is

roughly two times bigger than classical polynomial

and normal basis multiplier.

REFERENCES

Berlekamp, E. (1982). Bit-serial Reed-Solomon encoder.

IEEE Trans. Information Theory, IT-28:869–874.

Chang, K.-Y., Hong, D., and Cho, H.-S. (2005). Low com-

plexity bit-parallel multiplier for GF(2

) deﬁned by

all-one polynomials using redundant representation.

IEEE Trans. Comput., 54(12):1628–1630.

Koc, C. and Sunar, B. (1999). Mastrovito Multiplier for

All Trinomials. IEEE Transaction on Computers,

48(5):522–52.

Koc, C. and Sunar, B. (2001). An Efﬁcient Optimal Normal

Basis Type II Multiplier. IEEE Trans. on Computers,

50:83–87.

Lidl, R. and Niederreiter, H. (1986). Introduction to Finite

Fields and Their Applications. Cambridge Univ Press.

Mastrovito, E. (1991). VLSI architectures for computations

in Galois ﬁelds. PhD thesis, Dep.Elec.Eng.,Linkoping

Univ.

Miller, V. (1985). Uses of elliptic curves in cryptography.

Advances in Cryptology, proceeding’s of CRYPTO’85,

Lecture Note in Computer Science 218.

Silverman, J. H. (1999). Fast Multiplication in Finite Fields

GF(2

). In Crytographic Hardware and Embedded

Systems - CHES’99, volume 1717 of LNCS, pages

122–134.

Wu, H. and Hasan, M. (1998). Low-Complexity Multipliers

Bit-Parallel for a Class of Finite Fields. IEEE Trans.

Computers, 47:883–887.

PARALLEL MULTIPLICATION IN F2n USING CONDENSED MATRIX REPRESENTATION

259