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
}
Search WWH ::




Custom Search