Information Technology Reference
In-Depth Information
[Algorithm 1]
Ordinary Modular Multiplication
Input
:
a
,
b
,
f
(
x
)
Output
:
p
=
ab
mod
f
(
x
)
Initial value
:
p
(
m
)
= (
p
(
m
)
m
-1
,
p
(
m
)
m
-2
, …,
p
(
m
)
0
) = (0, 0, …, 0)
a
(
m
)
= (
a
m
-1
,
a
m
-2
, …,
a
0
)
1: for
i
=
m
-1 to 0 do
2: for
j
=
m
-1 to 0 do
3:
a
(
i
)
j
=
a
(
i
+1)
j
-1
+
a
(
i
+1)
m
-1
f
j
4:
p
(
i
)
j
=
p
(
i
+1)
j
-1
+
b
m
-1-
i
a
(
i
+1)
j
In order to perform step 3 and 4, two 1-dimensional CAs having
m
cells are used
which are gray colored in Fig. 1 (a).
a
is inputted into
m
cells of PBCA which has a
characteristic matrix with all rules 170 for step 3.
p
is inputted into
m
cells of NBCA
which all CA has the characteristics of 204 for step 4. It is possible to perform multi-
plication in
m
clock cycles with GM over
GF
(2
m
).
AOP Modular Multiplier
(AM):
Let
A
and
B
be the elements over
GF
(2
m
) and
t
(
x
) be
the modulus which uses the property of an irreducible AOP. Then each element over
extended standard basis is expressed as
A
=
A
m
α
m
+
A
m
-1
α
m
-1
+
A
m
-2
α
m
-2
+… +
A
0
,
B
=
B
m
α
m
+1
+1. From Algorithm 1, new modular
multiplication
P
=
AB
mod
t
(
x
) can be derived which applied the property of AOP as
a modulus as Algorithm 2.
CLS
() in Algorithm 2 represents a circular shifting 1-bit to
the left. After the applying the property of AOP as a modulus, modular reduction is
efficiently performed with just
CLS
() operation. Step 2 is very simplified compared
with step 3 in Algorithm 1 for GM. Fig. 1 (b) shows the proposed AOP modular mul-
tiplier. It is possible to perform multiplication in
m
+1 clock cycles over
GF
(2
m
).
m
+
B
m
-1
α
m
-1
+
B
m
-2
α
m
-2
+… +
B
0
, and
t
(
x
)
=
α
[Algorithm 2]
AOP Modular Multiplication
Input
:
A
,
B
Output
:
P
=
AB
mod α
m
+1
+1
Initial value
:
P
(
m
+1)
= (
P
(
m
+1)
m
,
P
(
m
+1)
m
-1
, …,
P
(
m
+1)
0
) = (0, 0, …, 0)
A
(
m
+1)
= (
A
m
,
A
m
-1
, …,
A
0
)
1: for
i
=
m
to 0 do
2:
A
(
i
)
=
CLS
(
A
(
i
+1)
)
3 for
j
=
m
to 0 do
4:
P
(
i
)
j
=
P
(
i
+1)
j
-1
+
B
m
-
i
A
(
i
+1)
j
3
Conclusions
This paper proposed two new modular multipliers over
GF
(2
m
). Since the proposed
multipliers have regularity, modularity and concurrency, they are suitable for VLSI
implementation. They can be used as a kernel circuit for public-key cryptosystem,
which requires exponentiation, inversion, and division as their basic operation.
