Cryptography Reference
In-Depth Information
in conjunction with
mod
(or with
modp1
) implement division in the polynomial ring
Z
p
[
]
x
, where
p
is a prime number.
Example 2.20
Suppose that wewant to compute the quotient and the remainder of the
division of
x
13
x
10
x
9
x
7
x
4
x
2
by
x
8
x
4
x
3
+
+
+
+
+
+
1
∈ Z
2
[
x
]
+
+
+
x
+
1
∈ Z
2
[
x
]
:
> f := xˆ13 + xˆ10 + xˆ9 + xˆ7 + xˆ4 + xˆ2 + 1:
g:=xˆ8+xˆ4+xˆ3+x+1:
Then we may use
Rem
which will give the remainder as output and, if provided
with a fourth optional argument '
q
', will assign the value of the quotient to the
variable
q
, so that:
> Rem(f, g, x, 'q') mod 2;
q;
xˆ7 + x
xˆ5 + xˆ2 + 1
x
7
x
5
x
2
1. Alternatively,
we can use
Quo
, in which case the output of the function is the quotient and the
remainder is optionally assigned to a variable name (
r
in our example) if it is passed
as fourth argument to the function:
This shows that, in this case,
r
=
+
x
and
q
=
+
+
> Quo(f, g, x, 'r') mod 2;
r;
xˆ5 + xˆ2 + 1
xˆ7 + x
[
]
Z
and also in this case the
greatest common divisor of polynomials can be defined and computed by means of
the Euclidean algorithm. If
f
The divisibility theory of
k
x
closely mimics that of
are polynomials, not both 0, then the
greatest
common divisor
of
f
and
g
is the unique monic polynomial
d
,
g
∈
k
[
x
]
∈
k
[
x
]
such that
d
|
f
,
d
|
g
, and if
h
∈
k
[
x
]
is such that
h
|
f
,
h
|
g
, then
h
|
d
. Moreover,
d
can be expressed
in the form
d
=
sf
+
tg
with
s
,
t
∈
k
[
x
]
(see, e.g., [131, Theorem 1.55]).
Remark 2.6
The requirement that the gcd be a monic polynomial is purely technical
and its purpose is to make the gcd unique. Otherwise the gcd would be defined only
up to units of
k
[
x
]
, i.e., up to multiplication by nonzero elements of
k
.
We shall not go into the details of the Euclidean algorithm for polynomials because
it is practically the same as the Euclidean algorithm for integers, just replacing inte-
ger division by polynomial division. Starting with
f
and
g
the analogous sequence
of divisions is performed until reaching a zero remainder. Then the previous remain-
der, multiplied by the inverse in
k
of its leading coefficient (in order to make the
polynomial monic) is the gcd of
f
and
g
. There is also a version of the extended
Euclidean algorithm for
k
[
x
]
, which computes, in addition to
d
=
gcd
(
f
,
g
)
, poly-
nomials
s
,
t
∈
k
[
x
]
such that
d
=
sf
+
tg
. As in the integer case, when
d
=
1,
f
and
g
aresaidtobe
relatively prime
.
Example 2.21
We use Maple to compute the greatest common divisor of the two
polynomials of
Z
2
[
x
]
we used in Example 2.20:
