Cryptography Reference
In-Depth Information
Chapter 2
Basic Concepts from Probability, Complexity,
Algebra and Number Theory
In this chapter we study the basic notions from mathematics and computer science
that we will be using throughout the topic. Its purpose is not to give a comprehensive
account of these concepts but, rather, to study them from the point of view of their
applications to cryptography, emphasizing the algorithmic aspects. For this task we
will be using Maple as a tool to implement the relevant algorithms and to experiment
with them. Bearing in mind these premises, we include here the required concepts
and results from probability, complexity theory and modular arithmetic, including
quadratic residues and modular square roots, and we also give a brief introduction
to the relevant aspects of group theory and finite fields. Thus, for readers already
familiar with these subjects, this chapter will hopefully serve as a refresher of the
topics mentioned in the Preface (with the exception of linear algebra which is not
included here) and, at the same time, as an introduction to the use of Maple to explore
the algorithms discussed. Even for readers not familiar with these subjects we hope
that sufficient information is included here to allow them to profitably read the rest
of the topic. We include proofs of most of the algorithmic and mathematical results
mentioned, with pointers to the literature for the reader who wishes to go deeper on
these topics and, at the same time, we will be introducing here a great deal of the
notation used throughout the topic.
2.1 Basic Probability Theory
Randomness plays a crucial role in cryptology and in order to deal with this concept
we need some basic notions from probability theory. We assume the reader already
knows the elements of this theory but, in order to fix the notation, we recall here
some of the most important probability-related concepts that we will use. We refer
to any introductory text on (discrete) probability such as, for example, [94, 167] for
more detailed information on these topics.
