TABLE OF CONTENTS This chapter discusses several fundamental number theoretic algorithms such as the greatest common divisor, least common multiple, and Jacobi symbol computation. These algorithms arise as essential components in several key cryptographic algorithms such as the RSA public key algorithm and various sieve-based factoring algorithms.
The greatest common divisor of two integers a and b, often denoted as ( a, b) , is the largest integer k that is a proper divisor of both a and b. That is, k is the largest integer such that 0 ? a (mod k) and 0 ? b (mod k) occur simultaneously.
The most common approach [1, pp. 337] is to reduce one operand modulo the other operand. That is, if a and b are divisible by some integer k and if qa + r = b, then r is also divisible by k. The reduction pattern follows ? a, b ? ? ? b, a mod b ?.
This algorithm will quickly converge on the greatest common divisor since the residue r tends to diminish rapidly (Figure 9.1). However, divisions are relatively expensive operations to perform and should ideally be avoided. There is another approach based on a similar relationship of greatest common divisors. The faster approach is based on the observation that if k divides both a and b, it will also divide a
