Cryptography Reference
In-Depth Information
Z
3
[
]
f
, i.e., the list of polynomials of
We need to build the list of elements of
x
Z
3
[
]
x
of degree less than 2. The next function builds the list of polynomials of
degree
<
n
in
Z
p
[
x
]
:
> polylist := proc(p, n)
local coeffs;
global x;
x := 'x';
coeffs := map(a -> convert(a, base, p), [$0 .. pˆn-1]);
map(l -> sort(sum(l[j]*xˆ(j-1), j=1..nops(l))), coeffs)
end proc:
The elements of
Z
3
[
x
]
f
are then the following:
> polylist(3, 2);
[0,1,2,x,x+1,x+2,2x,2x+1,2x+2]
Now, we use the already defined procedure
tabl
to build the multiplication table
of the 9-element field. As before, the elements in the preceding list correspond,
in the given order, to the files and columns of the following matrix, in which
the element in the
(
i
,
j
)
position is the result of multiplying the
i
th and the
j
th
element of the list:
> tabl(%, mult9)
⎡
⎣
⎤
⎦
0
0
0
0
0
0
0
0
0
01 2
x
x
+
1
x
+
2
x
2
x
+
12
x
+
2
02 1
x
2
x
+
22
x
+
1
x
x
+
2
x
+
1
0
x
2
x
2
x
+
22
x
+
21
x
+
12
x
+
1
0
x
+
12
x
+
2
x
+
2
x
1
x
+
12
x
0
x
+
22
x
+
12
x
+
21
x
x
+
1
x
2
02
x
x
1
x
+
1
x
+
1
2
2
x
+
2
x
+
2
02
x
+
1
x
+
2
x
+
1
2
2
x
2
x
+
2
x
1
02
x
+
2
x
+
12
x
+
1
x
2
x
+
2
1
2
x
F
p
n
,some
of which are more convenient than the polynomials we have used to define the field
structure. If to each polynomial of degree
There are several natural ways to represent the elements of the field
n
we associate the list (or the string)
of its coefficients, then we have a list of base-
p
digits that define a number in the
interval
<
p
n
of which these digits are the
p
-adic expansion. Thus we see that
we have natural bijections:
[
0
,
−
1
]
n
p
n
Z
p
[
x
]
f
←→ Z
p
←→ {
0
,
1
,...,
−
1
}=Z
p
n
,
whose composition is given by
n
−
1
i
→
n
−
1
i
0
a
i
x
i
0
a
i
p
i
, i.e., it assigns to each
=
=
polynomial its value for
x
p
. In this way we can deal with finite fields in a very
convenient form that represents the elements of
=
F
p
n
as the integers in the interval
p
n
[
F
4
,
neither the sum nor the multiplication in this field are the same as the corresponding
operations of
0
,
−
1
]
. One should be careful, however, for, as we have seen in the case of
Z
p
n
is not a field and the bijections
defined above are not (ring) isomorphisms. Indeed, the sum in
Z
p
n
when
n
>
1. In this case,
F
p
n
is given by the
“digitwise” sum in
Z
p
, i.e., to sum two elements regarded as integers, they are first
expressed as sequences of digits in base
p
and then the corresponding digits are
