Computation of the least primitive root

McGown, Kevin; Sorenson, Jonathan

doi:10.1090/mcom/4003

Computation of the least primitive root
HTML articles powered by AMS MathViewer

by Kevin J. McGown and Jonathan P. Sorenson;

Math. Comp. 94 (2025), 909-917

DOI: https://doi.org/10.1090/mcom/4003

Published electronically: July 24, 2024

HTML | PDF | Request permission

Abstract:

Let $g(p)$ denote the least primitive root modulo $p$, and $h(p)$ the least primitive root modulo $p^2$. We computed $g(p)$ and $h(p)$ for all primes $p\le 10^{16}$. As a consequence we are able to prove that $g(p)<p^{5/8}$ for all primes $p>3$ and that $h(p)<p^{2/3}$ for all primes $p$. More generally, we provide values of $p_\alpha$ where $g(p)<p^\alpha$ when $p>p_\alpha$, for various values of $\alpha$ with $1/2<\alpha <5/8$. Additionally, we give a log-histogram of $g(p)$ when $g(p)\ge 100$ and empirical evidence that $g(p)\ll (\log p)(\log \log p)^2$.

References

Eric Bach, Comments on search procedures for primitive roots, Math. Comp. 66 (1997), no. 220, 1719–1727. MR 1433261, DOI 10.1090/S0025-5718-97-00890-9
D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179–192. MR 132732, DOI 10.1112/plms/s3-12.1.179
Bo Chen, Explicit upper bound on the least primitive root modulo $p^2$, Int. J. Number Theory 18 (2022), no. 2, 389–395. MR 4390666, DOI 10.1142/S1793042122500233
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Stephen D. Cohen, Tomás Oliveira e Silva, and Tim Trudgian, On Grosswald’s conjecture on primitive roots, Acta Arith. 172 (2016), no. 3, 263–270. MR 3460815, DOI 10.4064/aa8109-12-2015
Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
P. D. T. A. Elliott and Leo Murata, On the average of the least primitive root modulo $p$, J. London Math. Soc. (2) 56 (1997), no. 3, 435–454. MR 1610435, DOI 10.1112/S0024610797005310
P. Erdös and M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math. 62 (1940), 738–742. MR 2374, DOI 10.2307/2371483
E. Grosswald, On Burgess’ bound for primitive roots modulo primes and an application to $\Gamma (p)$, Amer. J. Math. 103 (1981), no. 6, 1171–1183. MR 636957, DOI 10.2307/2374229
Emil Grosswald, On the parabolic generators of the principal congruence subgroups of the modular group, Amer. J. Math. 74 (1952), 435–443. MR 49937, DOI 10.2307/2372008
Bryce Kerr, Kevin J. McGown, and Tim Trudgian, The least primitive root modulo $p^2$, J. Number Theory 215 (2020), 20–27. MR 4125902, DOI 10.1016/j.jnt.2020.01.002
Kevin McGown, Enrique Treviño, and Tim Trudgian, Resolving Grosswald’s conjecture on GRH, Funct. Approx. Comment. Math. 55 (2016), no. 2, 215–225. MR 3584569, DOI 10.7169/facm/2016.55.2.5
Kevin J. McGown and Tim Trudgian, Explicit upper bounds on the least primitive root, Proc. Amer. Math. Soc. 148 (2020), no. 3, 1049–1061. MR 4055934, DOI 10.1090/proc/14800
Peter L. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), no. 170, 519–521. MR 777282, DOI 10.1090/S0025-5718-1985-0777282-X
A. Paszkiewicz, A new prime $p$ for which the least primitive root (mod $p$) and the least primitive root (mod $p^2$) are not equal, Math. Comp. 78 (2009), no. 266, 1193–1195. MR 2476579, DOI 10.1090/S0025-5718-08-02090-5
Guy Robin, Estimation de la fonction de Tchebychef $\theta$ sur le $k$-ième nombre premier et grandes valeurs de la fonction $\omega (n)$ nombre de diviseurs premiers de $n$, Acta Arith. 42 (1983), no. 4, 367–389 (French). MR 736719, DOI 10.4064/aa-42-4-367-389
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Victor Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), no. 197, 369–380. MR 1106981, DOI 10.1090/S0025-5718-1992-1106981-9
Jonathan P. Sorenson, Two compact incremental prime sieves, LMS J. Comput. Math. 18 (2015), no. 1, 675–683. MR 3418033, DOI 10.1112/S1461157015000194