Cryptography Reference
In-Depth Information
If one is talking about a cryptographic system, then one is often talking about
one or several algorithms. The term algorithm,
1
in turn, is best defined as suggested
in Definition 1.1.
Definition 1.1 (Algorithm)
An
algorithm
is a well-defined computational proce-
dure that takes a variable input and generates a corresponding output.
Consequently, an algorithm is simply a computational procedure that is well
defined and that turns a variable input into a corresponding output (according
to the computational procedure it defines). It is sometimes also required that an
algorithm halts within a reasonable amount of time (for any meaningful definition
of “reasonable”). In either case, Definition 1.1 is rather vague and mathematically
unprecise. It neither says what the computational model for the algorithm is, nor does
it say anything about the problem the algorithm is supposed to solve (e.g., computing
a mathematical function). Consequently, from a theoretical viewpoint, an algorithm
can be more precisely defined as a well-defined computational procedure for a well-
defined computational model for solving a well-defined problem. This definition,
however, is a little bit clumsy, and we use the simpler (and more intuitive) definition
given in Definition 1.1.
In either case, it is important to distinguish between deterministic and proba-
bilistic algorithms:
•
An algorithm is
deterministic
if its behavior is completely determined by the
input. Consequently, the algorithm always generates the same output for the
same input (if it is executed multiple times).
•
An algorithm is
probabilistic
(or
randomized
) if its behavior is not completely
determined by the input, meaning that the algorithm internally uses and
takes advantage of some randomly (or pseudo-randomly) generated values.
Consequently, a probabilistic algorithm may generate a different output each
time it is executed with the same input (if it is executed multiple times).
There are different types of probabilistic algorithms, and in Section 6.6.3 we
distinguish between Las Vegas, Monte Carlo, and Atlantic City algorithms.
An algorithm may be implemented by a computer program that is written in
a specific programming language (e.g., Pascal, C, or Java). Whenever we describe
algorithms in this topic, we don't use a specific programming language; we use
a formal notation instead. The notation used to describe algorithms is sketched
in Algorithm 1.1. The input and output parameters of an algorithm are written in
brackets at the beginning and at the end of the algorithm description. The body of
1 et rm
algorithm
is derived from the name of the mathematician Mohammed ibn-Musa al-
Khwarizmi, who was part of the royal court in Baghdad and lived from about 780 to 850.
