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 search space for LLP-GCD is a bounded product of chains of natural numbers, ordered componentwise by the usual numerical order. Its meet and join are componentwise minimum and maximum. Divisibility appears in the feasibility predicate; this is not the divisibility lattice. LLP-GCD moves downward in the componentwise order by Euclidean reductions until the two coordinates agree.

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(\min(a, b)))$ arithmetic operations.

LLP-ExtGCD (Extended Euclidean)

Computes integers $x, y$ with $a \cdot x + b \cdot y = \gcd(a, b)$. Alongside the remainder pair $G$, two further state arrays $X, Y$ track the Bézout coefficients, maintaining the invariant $G[k] = X[k] \cdot a + Y[k] \cdot b$. Forbidden detects $G[j] > G[i]$ for some $i$; advancing reduces $G[j]$ via the same Euclidean quotient as LLP-GCD and applies the identical combination to $X[j], Y[j]$. At termination $G[0] = G[1] = \gcd(a, b)$ and $(X[0], Y[0])$ is a Bézout pair.

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

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.