Cryptography Reference
In-Depth Information
6
Algorithmic Algebra
Content
Group theory:
isomorphism, construction
The ring Z
n
:
Euclid algorithm, exponentiation, Chinese Remainder Theorem
Finite fields:
generators, construction
Quadratic residuosity
Elliptic curves
Basic notions of number theory are briefly exposed in this chapter, as well as a
number of useful algorithms on number theory. We encourage the reader to experiment
with the algorithms using a symbolic computing software (e.g. Maple, from the Univer-
sity of Waterloo,
1
or Pari/GP from the University of Bordeaux
2
). While conventional
cryptography uses simple operations on bitstrings which are built in all microproces-
sors, public-key cryptography uses computation in algebraic structures. These classical
structures are reviewed here.
6.1
Basic Group Theory
6.1.1 Basic Set Theory
We briefly remind here some basic notions and notations from set theory.
A
set
consists of a collection of
elements
. If an element
x
is in a set
A
we write
x
be the empty
set, i.e. the set which has no element. If
A
and
B
are two sets, their
intersection
is the
set denoted
A
∈
A
. Two sets are equal if they have exactly the same elements. We let
∅
B
of all
x
which are elements of both
A
and
B
. The
union
of
A
and
B
is the set denoted
A
∩
∪
B
of all
x
which are elements of either
A
or
B
. If all elements of
A
are systematically elements of
B
we say that
A
is a
subset
of
B
and write
A
⊆
B
.In
order to denote the set of all elements
x
of
A
which satisfy a predicate
P
(
x
), we write
{
x
∈
A
;
P
(
x
)
}
, or simply
{
x
;
P
(
x
)
}
when
A
is clear from the context.
A
function f
may map an element
x
of
A
to an element
f
(
x
)ofaset
B
. We write
f
:
A
B
to denote that
f
takes elements of
A
and maps them into elements of
B
.
We write
f
:
x
→
y
. In this case we say that
y
is the
image
of
x
by
f
and that
x
is a
preimage
of
y
by
f
.If
I
→
y
to denote that
f
(
x
)
=
⊆
A
,welet
f
(
I
) denote the set of
1
See http://www.maplesoft.com.
2
See http://pari.math.u-bordeaux.fr.
Search WWH ::
Custom Search