login
Prime numbers for which there is a primitive root g for which the iteration x -> g^x (mod p) generates all nonzero residues (mod p).
1

%I #36 Mar 14 2020 16:52:51

%S 3,5,23,41,59,61,107,139,149,173,181,233,239,251,269,281,311,331,349,

%T 359,389,397,439,457,461,463,467,487,509,547,577,587,647,653,719,751,

%U 769,809,811,829,877,883,907,919,941,967,1039,1069,1097,1103,1109,1213

%N Prime numbers for which there is a primitive root g for which the iteration x -> g^x (mod p) generates all nonzero residues (mod p).

%C Recent works by Holden, Pomerance et al. have established that for every prime p>2 there is a primitive root g modulo p which has a fixed point: g^x = x (mod p). This sequence shows in fact not every prime has a primitive root which generates all nonzero residues by iterated exponentiation. This sequence may have applications to random number generation, where long periods are usually required.

%H Alasdair McAndrew, <a href="/A214876/b214876.txt">Table of n, a(n) for n = 1..1884</a>

%H M. Levin, C Pomerance, and K. Soundararajan, <a href="http://www.math.dartmouth.edu/~carlp/brizolisants.pdf">Fixed points for discrete logarithms</a>, Lecture Notes in Computer Science, 2010, Volume 6197, Algorithmic Number Theory, pages 6-15.

%t testcyclic[p_] := (g = 1; out = False; While[out == False && g < p-2, g += 1; If[ MultiplicativeOrder[g, p] == p-1, x = g; c = 1; While[x != 1, x = PowerMod[g, x, p]; c += 1]; If[c == p-1, out = True]]]; Return[out]);

%t testcyclic[3] = True;

%t Reap[ Do[ If[ testcyclic[p], Print[p]; Sow[p]], {p, Prime /@ Range[200]}]][[2, 1]]

%t (* _Jean-François Alcover_, Sep 17 2012, translated from Sage *)

%o (Sage)

%o def testcyclic(p):

%o if p == 3: return True

%o g = 1

%o out = False

%o while not out and g<p-2:

%o g += 1

%o if mod(g,p).multiplicative_order()==p-1:

%o x = g

%o c = 1

%o while (x != 1):

%o x = power_mod(g,x,p)

%o c += 1

%o if c==p-1:

%o out = True

%o return out

%o for p in primes(400):

%o if testcyclic(p): print(p)

%o (PARI) has(g)=my(x=g); for(i=4,g.mod, x=g^lift(x); if(x==1, return(0))); 1

%o is(n)=if(!isprime(n), return(0)); my(r=znprimroot(n),g=1); for(k=1,n, g*=r; if(gcd(k,n-1)==1 && has(g), return(n>2))); 0 \\ _Charles R Greathouse IV_, Jul 31 2016

%K nonn,nice

%O 1,1

%A _Alasdair McAndrew_, Jul 28 2012