Primitive Roots

Jim Hefferon · Elementary Number Theory · Ch. 7

A primitive root mod p is a number whose powers cycle through all nonzero residues. Every prime has one. Finding discrete logarithms (inverting this cycle) is believed to be hard, which is the foundation of Diffie-Hellman key exchange.

Order of an element

The order of a mod n is the smallest positive integer k such that a^k ≡ 1 (mod n). A primitive root mod p has order p - 1: its powers hit every nonzero residue exactly once.

Scheme

; Order of an element and primitive roots
(define (mod-pow base exp mod)
  (cond ((= exp 0) 1)
        ((even? exp)
         (let ((half (mod-pow base (quotient exp 2) mod)))
           (modulo (* half half) mod)))
        (else (modulo (* base (mod-pow base (- exp 1) mod)) mod))))

(define (order a n)
  (let loop ((k 1))
    (if (= 1 (mod-pow a k n)) k (loop (+ k 1)))))

; Powers of 2 mod 13 (primitive root, order = 12)
(display "Powers of 2 mod 13: ")
(let loop ((k 0))
  (when (< k 12)
    (display (mod-pow 2 k 13)) (display " ")
    (loop (+ k 1))))
(newline)
(display "order(2, 13) = ") (display (order 2 13)) (newline)

; 3 is NOT a primitive root mod 13 (order = 3)
(display "order(3, 13) = ") (display (order 3 13)) (newline)
(display "Powers of 3 mod 13: ")
(let loop ((k 0))
  (when (< k 6)
    (display (mod-pow 3 k 13)) (display " ")
    (loop (+ k 1))))

The discrete logarithm problem

Given g, h, p where g is a primitive root mod p, find x such that g^x ≡ h (mod p). Going forward (computing g^x) is fast. Going backward (finding x from h) is believed to be hard for large p. This asymmetry is the basis of Diffie-Hellman and related cryptosystems.

Scheme

; Discrete logarithm by brute force (only feasible for small p)
(define (mod-pow base exp mod)
  (cond ((= exp 0) 1)
        ((even? exp)
         (let ((half (mod-pow base (quotient exp 2) mod)))
           (modulo (* half half) mod)))
        (else (modulo (* base (mod-pow base (- exp 1) mod)) mod))))

(define (discrete-log g h p)
  (let loop ((x 0))
    (cond ((>= x p) #f)
          ((= h (mod-pow g x p)) x)
          (else (loop (+ x 1))))))

; g=2, p=13: find x such that 2^x = h mod 13
(display "2^x = 8 mod 13: x = ")
(display (discrete-log 2 8 13)) (newline)   ; 3

(display "2^x = 5 mod 13: x = ")
(display (discrete-log 2 5 13)) (newline)   ; 9

(display "2^x = 7 mod 13: x = ")
(display (discrete-log 2 7 13))             ; 11

Neighbors

→ Cryptography Ch.5 — Diffie-Hellman key exchange relies on the hardness of discrete logarithms
🔐 Cryptography Ch.5 — Diffie-Hellman key exchange is the discrete logarithm problem
🔗 Abstract Algebra Ch.1 — cyclic groups are the algebraic structure of primitive roots

← Quadratic Residues by june.kim Continued Fractions →