Least primitive roots of consecutive primes with a sieved factorization of p-1

We compute g(p), the least positive primitive root of a prime p, for all primes p <= N. A segmented sieve factors p - 1 for every prime in a block. The quadratic character of each candidate is obtained from a table indexed by p mod 4g for g < 128 and by a Jacobi-symbol computation otherwise; perfect powers are skipped, and the remaining tests for odd prime divisors q of p - 1 are exponentiations that run 32 at a time in AVX2 lanes of 32-bit Montgomery arithmetic for p < 2^31, and by a divide-and-conquer descent with total exponent length at most (ceil(log_2 k) + 1) * log_2(p - 1) for k odd prime divisors for larger p. The cost is O(A(N) log N log log N) per prime, where A(N) is the mean of g(p) over p <= N. At N = 10^9 the C implementation takes 350 ns per prime on one core, 4.0 times less than the textbook test on the same sieved factorization, and at N = 10^8 it is 5.4 times faster than trial-division factoring (medians of three runs). A Python implementation is 3.2 times faster than SymPy at N = 10^6.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-13
DOI
https://doi.org/10.5281/zenodo.24207597
Primary Topic
Analytic Number Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Least primitive roots of consecutive primes with a sieved factorization of p-1

Mark Kim
Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
preprint

Least primitive roots of consecutive primes with a sieved factorization of p-1

Mark Kim
preprint en

Abstract

We compute g(p), the least positive primitive root of a prime p, for all primes p <= N. A segmented sieve factors p - 1 for every prime in a block. The quadratic character of each candidate is obtained from a table indexed by p mod 4g for g < 128 and by a Jacobi-symbol computation otherwise; perfect powers are skipped, and the remaining tests for odd prime divisors q of p - 1 are exponentiations that run 32 at a time in AVX2 lanes of 32-bit Montgomery arithmetic for p < 2^31, and by a divide-and-conquer descent with total exponent length at most (ceil(log_2 k) + 1) * log_2(p - 1) for k odd prime divisors for larger p. The cost is O(A(N) log N log log N) per prime, where A(N) is the mean of g(p) over p <= N. At N = 10^9 the C implementation takes 350 ns per prime on one core, 4.0 times less than the textbook test on the same sieved factorization, and at N = 10^8 it is 5.4 times faster than trial-division factoring (medians of three runs). A Python implementation is 3.2 times faster than SymPy at N = 10^6.

Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
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