Chapter 19. Algorithms in Number Theory

GCD and extended Euclidean — through the LLP lens.

This page: LLP forms. View classical forms »

Number theory and lattices

The natural numbers under divisibility form a distributive lattice, making number-theoretic problems a natural fit for the LLP framework. LLP-GCD searches this lattice by descending: reducing values via mod until they converge on the greatest common divisor.

LLP-GCD

The LLP algorithm for the greatest common divisor of two numbers. The state vector $G$ starts as a copy of the input pair $A = [a, b]$. Forbidden detects $G[j] > G[i]$ for some $i$; advancing reduces $G[j]$ via the Euclidean reduction (mod). At termination, both entries equal $\gcd(a, b)$ — exactly the trace of Euclid's algorithm.

Time complexity: $O(\log M)$ arithmetic operations, where $M = \max(a, b)$; $O((\log M)^2)$ bit operations with schoolbook arithmetic.

LLP-ExtGCD (Extended Euclidean)

Computes integers $x, y$ with $a \cdot x + b \cdot y = \gcd(a, b)$. The state $(G, H)$ tracks the current remainder pair together with their Bézout coefficients. Forbidden detects $G[0] \neq G[1]$; advancing performs one Euclidean reduction on the larger side and propagates the same combination to $H$. At termination $G[0] = G[1] = \gcd(a, b)$ and the corresponding row of $H$ holds $(x, y)$.

Time complexity: $O(\log \min(a, b))$.

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[j]$ represents and the negation of the forbidden clause from the matching .llp source.