Cryptography Reference
In-Depth Information
+
=
+
=
the last iteration, the equation
au
bv
x
becomes
as
bt
d
, giving the desired
result.
The extended Euclidean algorithm is implemented in Maple's function
igcdex
.
This function accepts as arguments, besides the two integers whose gcd is to be
computed, two names
's'
and
't'
where the values of the integers
s
,
t
mentioned
above are to be stored. For example:
> igcdex(387349873729876, 48962090968, 's', 't');
4
> s, t, 387349873729876*s + 48962090968*t;
-2790500723, 22076265153864, 4
As we will see, the Euclidean algorithm plays an important role in cryptology
because it is an essential step in many other interesting algorithms. It is also very
important that it is a very efficient algorithm, not only in theoretical terms but also in
practice. By working backwards in the Euclidean algorithm we may similarly show
that the complexity of the extended Euclidean algorithm is also
O
(
len
(
a
)
len
(
b
))
.
2.5 Groups, Rings and Fields
In this section we briefly recall some basic algebraic concepts that will be useful in
what follows. For more detailed accounts we refer to [45, 48].
2.5.1 Basic Concepts
·
→
Recall that a
group
(
G
,
·
)
is a set
G
together with a binary operation
G
×
G
G
which satisfies the following properties:
•
Associative law
. For all
x
,
y
,
z
∈
G
,
x
·
(
y
·
z
)
=
(
x
·
y
)
·
z
.
•
Identity element
. There is a (necessarily unique) element
e
∈
G
such that, for
every
x
∈
G
,
x
·
e
=
e
·
x
=
x
.
G
has a unique inverse
x
−
1
•
Inverse element
. Each element
x
∈
∈
G
, namely, an
element
x
−
1
that satisfies
x
x
−
1
x
−
1
·
=
·
x
=
e
.
A group is called
abelian
or
commutative
when, in addition, the operation satisfies:
•
Commutative law
. For all
x
,
y
∈
G
,
x
·
y
=
y
·
x
.
When the binary operation is understood, we often commit abuse of language and
refer to the set
G
as a group. The symbols most frequently used to denote the group
operation are
(additive group) although, of course,
the operation may not be related to the addition or the multiplication of numbers.
Additive notation is frequently used for abelian groups and when multiplicative
notation is used, the symbol
·
(multiplicative group) and
+
·
is often omitted and we write
xy
to denote the result of
