Cryptography Reference
In-Depth Information
2
Basic algorithmic number theory
The aim of this chapter is to give a brief summary of some fundamental algorithms for
arithmetic in finite fields. The intention is not to provide an implementation guide; instead,
we sketch some important concepts and state some complexity results that will be used
later in the topic. We do not give a consistent level of detail for all algorithms; instead, we
only give full details for algorithms that will play a significant role in later chapters of the
topic.
More details of these subjects can be found in Crandall and Pomerance [ 150 ], Shoup
[ 497 ], Buhler and Stevenhagen [ 106 ], Brent and Zimmermann [ 95 ], Knuth [ 308 ], von zur
Gathen and Gerhard [ 220 ], Bach and Shallit [ 21 ] and the handbooks [ 16 , 376 ].
The chapter begins with some remarks about computational problems, algorithms and
complexity theory. We then present methods for fast integer and modular arithmetic. Next
we present some fundamental algorithms in computational number theory such as Euclid's
algorithm, computing Legendre symbols and taking square roots modulo p . Finally, we
discuss polynomial arithmetic, constructing finite fields and some computational problems
in finite fields.
2.1 Algorithms and complexity
We assume the reader is already familiar with computers, computation and algorithms.
General references for this section are Chapter 1 of Cormen et al .[ 136 ], Davis and
Weyuker [ 154 ], Hopcroft and Ullman [ 265 ], Section 3.1 of Shoup [ 497 ], Sipser [ 509 ]
and Talbot and Welsh [ 539 ].
Rather than using a fully abstract model of computation, such as Turing machines, we
consider all algorithms as running on a digital computer with a typical instruction set, an
infinite number of bits of memory and constant-time memory access. This is similar to
the random access machine (or register machine) model; see Section 3.6 of [ 21 ], [ 129 ],
Section 2.2 of [ 136 ], Section 7.6 of [ 265 ] or Section 3.2 of [ 497 ]. We think of an algorithm
as a sequence of bit operations, though it is more realistic to consider word operations.
A computational problem is specified by an input (of a certain form) and an output
(satisfying certain properties relative to the input). An instance of a computational problem
Search WWH ::




Custom Search