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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Fewer multiplications for the least primitive root of every prime: a quadratic filter, character reuse and a splitting tree

Mark Kim
Zenodo (CERN European Organization for Nuclear Research)
Cryptography and Residue Arithmetic
preprint

Fewer multiplications for the least primitive root of every prime: a quadratic filter, character reuse and a splitting tree

Mark Kim
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Cryptography and Residue Arithmetic
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon