Cryptography Reference
In-Depth Information
=
Definition 2.24
Let
R
be a commutative ring with identity 1
0. A
polynomial
in
one variable over
R
, is a formal expression
a
n
x
n
a
n
−
1
x
n
−
1
f
(
x
)
=
+
+···+
a
1
x
+
a
0
,
where
n
is a non-negative integer,
x
is the
variable
(also called an
indeterminate
)
and the
a
i
n
,arethe
coefficients
. The set of all the polynomials in
the variable
x
over
R
is denoted by
R
∈
R
,
i
=
1
,...,
[
x
]
.
We are going to identify the set
{
0
,
1
,
2
,
3
}
with the set
{
0
,
1
,
x
,
x
+
1
}
of poly-
nomials of
, with the identification done by means of the bijection that maps
the latter to the former by just substituting
x
Z
2
[
x
]
=
2:
> subs(x = 2, [0, 1, x, x+1]);
[0, 1, 2, 3]
Then we define a multiplication in this set of polynomials as follows:
> mult4 := (f,g) -> Rem(f*g, xˆ2+x+1, x) mod 2:
The preceding operation takes two polynomials in the variable
x
, multiplies them,
and computes the remainder of dividing their product by the polynomial
x
2
1
(see Sect.
2.8.2
for the definition of these operations), where all the polynomials are
considered with coefficients in
+
x
+
Z
2
. Now we use the function
tabl
above to compute
the table of this operation in matrix form:
> tabl([0, 1, x, x+1], mult4);
⎡
⎣
⎤
⎦
0 0 0 0
01
xx
+
1
0
11
0
x
+
11
x
xx
+
If we want to see this multiplication viewed as defined on the set
{
0
,
1
,
2
,
3
}
,we
substitute
x
=
2 into the preceding matrix:
> subs(x = 2, %);
⎡
⎣
⎤
⎦
0000
0123
0231
0312
We see that the operation defined with the help of the polynomials is indeed the
same as the multiplication we had previously defined on
{
0
,
1
,
2
,
3
}
.
Exercise 2.30
UseMaple to define thismultiplication explicitly on the set
}
and build the corresponding table using
tabl
. In order to do it, define the map
{
{
0
,
1
,
2
,
3
whose inverse is given by
f -> subs(x = 2, f)
(this map can be defined more generally for any positive integer: the coefficients of
the polynomial corresponding to one of these integers are just its binary digits).
0
,
1
,
2
,
3
}→{
0
,
1
,
x
,
x
+
1
}