Number Theoretic Algorithms
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.
9.1 Greatest Common Divisor
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 ...
Get BigNum Math now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
