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,
The standard algjuurtest for a given modulus n (with existing primitive roots) proceeds by factoring φ(n) and
Example: modulo p = 17, φ(17) = 16 with prime factor 2. Check g = 3: compute 3^{16/2} = 3^8
Applications of algjuurtestid include cryptography (discrete logarithm foundations) and number theory investigations where knowledge of generator