Cryptography Reference
In-Depth Information
CHAPTER 10
Basic Number-Theoretic
Functions
I am dying to hear about it, since I always thought
number theory was the Queen of Mathematics—the
purest branch of mathematics—the one branch of
mathematics which has NO applications!
—D. R. Hofstadter,
Gödel, Escher, Bach
N
OW THAT WE ARE FITTED
out with a sturdy tool box of arithmetic functions that we
developed in the previous chapters, we turn our attention to the implementation
of several fundamental algorithms from the realm of number theory. The number-
theoretic functions discussed in the following chapters form a collection that
on the one hand exemplifies the application of the arithmetic of large numbers
and on the other forms a useful foundation for more complex number-theoretic
calculations and cryptographic applications. The resources provided here can be
extended in a number of directions, so that for almost every type of application
the necessary tools can be assembled with the demonstrated methods.
The algorithms on which the following implementations are based are drawn
primarily from the publications [Cohe], [HKW], [Knut], [Kran], and [Rose], where
as previously, we have placed particular value on efficiency and on as broad a
range of application as possible.
The following sections contain the minimum of mathematical theory required
to explicate the functions that we present and their possibilities for application.
We would like, after all, to have some benefit from all the effort that will be
required in dealing with this material. Those readers who are interested in a more
thoroughgoing introduction to number theory are referred to the topics [Bund]
and [Rose]. In [Cohe] in particular the algorithmic aspects of number theory
are considered and are treated clearly and concisely. An informative overview of
applications of number theory is offered by [Schr], while cryptographic aspects of
number theory are treated in [Kobl].
In this chapter we shall be concerned with, among other things, the
calculation of the greatest common divisor and the least common multiple
of large numbers, the multiplicative properties of residue class rings, the
identification of quadratic residues and the calculation of square roots in
