Algjuurtestid

Algjuurtestid are mathematical procedures used to determine whether a number is a primitive root modulo a given modulus. A primitive root modulo n is an integer g whose powers modulo n generate the entire multiplicative group of units modulo n; equivalently, the order of g modulo n equals Euler’s totient φ(n).

Existence of primitive roots is restricted. Primitive roots exist only for n in the set {1, 2, 4, p^k, 2 p^k}, where p is an odd prime and k is a positive integer. When primitive roots exist for n, there are φ(φ(n)) primitive roots modulo n.

The standard algjuurtest for a given modulus n (with existing primitive roots) proceeds by factoring φ(n) and testing powers of the candidate g. Let φ(n) = ∏ q_i^{e_i} with distinct prime factors q_i. Then g is a primitive root modulo n if and only if for every distinct prime factor q_i of φ(n) the congruence g^{φ(n)/q_i} ≠ 1 (mod n). If any such power equals 1, g is not a primitive root. This test reduces to modular exponentiation and requires factoring φ(n); for prime moduli p, φ(p) = p−1.

Example: modulo p = 17, φ(17) = 16 with prime factor 2. Check g = 3: compute 3^{16/2} = 3^8 (mod 17). If 3^8 ≠ 1 (mod 17), then 3 is a primitive root modulo 17.

Applications of algjuurtestid include cryptography (discrete logarithm foundations) and number theory investigations where knowledge of generator elements of modular groups is useful.