Information Technology Reference
In-Depth Information
ble if the smallest positive integer
n
for which
f
(
x
) divides
x
n
+ 1 is
n
= 2
m
-1 [4-5]. Let
f
(
x
)=
x
m
+
f
m
-1
x
m
-1
+ … +
f
1
x
1
+
f
0
be an irreducible polynomial over
GF
(2) and α be a root
of
f
(
x
). Any field element
GF
(2
m
) can be represented by a standard basis such as
a
=
a
m
-1
α
m
-1
}
is an ordinary standard basis of
GF
(2
m
). It has been shown that an AOP (All One
Polynomial) is irreducible if and only if
m
+1 is a prime and 2 is a generator of the
field
GF
(
m
+1). The values of
m
for which an AOP of degree
m
is irreducible are 2, 4,
10, 12, 18, 28, 36, 52, 58, 60, 66, 82, and 100 for
m
≤100. Let
ff
(
x
) =
x
m
+
x
m
-1
+…+
x
+
1 be an irreducible AOP over
GF
(2) and α be the root of
ff
(
x
) such that
ff
(α) = α
2
,…, α
m
-2
, α
m
-1
+
a
m
-2
α
m
-2
+… +
a
0
, where
a
i
∈
GF
(2) for 0≤
i
≤
m
-1. { 1, α, α
m
+
α
= 1. This property
of irreducible polynomial is very adaptable for PBCA architecture. If it is assumed
that { 1, α, α
m
-1
+…+ α
+ 1 = 0. Then we have α
m
= α
m
-1
+ α
m
-2
+…+ α
+ 1, α
m
+1
} is an extended standard basis, the field element
A
can also
be represented as
A
=
A
m
α
2
, α
3
,…, α
m
m
+
A
m
-1
α
m
-1
+
A
m
-2
α
m
-2
+… +
A
0
, where
A
m
= 0 and
A
i
∈
GF
(2)
for 0
m
. Here,
a
=
A
(mod
ff
(
x
)), where
ff
(
x
) is an AOP of degree
m
, then the
coefficients of
a
are given by
a
i
=
A
i
+
A
m
(mod 2), 0
≤
i
≤
≤
i
≤
m
-1.
Cellular automata
:
CA are finite state machines, defined as uniform arrays of simple
cells in
n
-dimensional space. They can be characterized by looking at four properties:
the cellular geometry, neighborhood specification, number of states per cell, and
algorithm used for computing the successor state. A cell uses an algorithm, called its
computation rule, to compute its successor state based on the information received
from its nearest neighbors. An example is shown below for 2-state 3-neighborhood 1-
dimensional CA [2-3].
Neighborhood state : 111 110 101 100 011 010 001 000
State coefficient : 2
7
2
6
2
5
2
4
2
3
2
2
2
1
2
0
Next state : 1 1 1 1 0 0 0 0 (rule 240)
In the above example, the top row gives all eight possible states of the 3-
neighboring cells at time
t
. The second row is the state coefficient, while the third
row gives the corresponding states of the
i
th cell at time
t
+1 for two illustrative CA
rules. There are various possible boundary conditions, for example, a NBCA (Null-
Boundary CA), where the extreme cells are connected to the ground level, a PBCA
(Periodic-Boundary CA), where extreme cells are adjacent, etc.
2
Modular Multiplier
This section presents two new multipliers, GM for a generalized irreducible polyno-
mial and AM for a specialized irreducible polynomial, over
GF
(2
m
).
Generalized Modular Multiplier
(GM):
Let
a
and
b
be the elements over
GF
(2
m
) and
f
(
x
) be the modulus. Then each element over ordinary standard basis is expressed as
a
=
a
m
-1
α
+… +
b
0
, and
f
(
x
)
=
x
m
+
f
m
-1
x
m
-1
+
f
m
-
2
x
m
-2
+… +
f
0
. The modular multiplication
p
=
ab
mod
f
(
x
) can be represented with the
LSB (Least Significant Bit) first fashion as follows:
m
-1
+
a
m
-2
α
m
-2
+… +
a
0
,
b
=
b
m
-1
α
m
-1
+
b
m
-2
α
m
-2
