Fewer multiplications for the least primitive root of every prime: a quadratic filter, character reuse and a splitting tree
For a prime p let g(p) and h(p) be the least primitive roots modulo p and modulo p^2. We give an exact algorithm that computes g(p) and decides g(p) = h(p) for every prime p with 3.5 times fewer modular multiplications per prime than the algorithm that tests each prime divisor q of p - 1 by its own exponentiation, and 2.5 to 3.2 times shorter running time for p < 2^32. The algorithm combines a table-driven quadratic filter, evaluation of composite candidates from the characters of their prime factors, a splitting tree that produces all values a^((p-1)/q) from one exponentiation chain, and, for p < 2^32, a fusion of the Wieferich test g^(p-1) != 1 (mod p^2) into the tree. For all primes 3 <= p < 2*10^9 it takes 56 s on one core and reproduces the 24 record values of g(p) and the only exception g(p) != h(p) in this range, p = 40487.
Authors
- Mark Kim (ORCID: https://orcid.org/0000-0001-7601-831X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-14
- DOI
- https://doi.org/10.5281/zenodo.24219446
- Primary Topic
- Cryptography and Residue Arithmetic
- Type
- preprint