TABLE OF CONTENTS 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 University 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 microprocessors, public-key cryptography uses computation in algebraic structures. These classical structures are reviewed here.
[1]See http://www.maplesoft.com.
[2]See http://pari.math.u-bordeaux.fr.
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 ? A Two sets are equal if they have exactly the same elements. We let ? 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 ? 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
