Thread: generator of Z*p

if p,q are primes with p=2q+1, and we pick a random number g in Z*p, what is the probability that g is a generator of Z*p?

is cyclic of order and so has generators. The probability of picking a generator is thus

note that if q is very large this is "nearly" 1/2 (even for the relatively small q = 3 it's already 1/3 (approx. 33%) and for q = 5 it's jumped to 2/5 (40%)). these odds are good enough that it often suffices to check 2,3,5 and 7 as possible generators for small values of p (i think 109 is the first prime where you have to use something else, and 6 works there, 191 is the smallest prime that has a relatively "large" smallest primitive element (19)...note that both of these are not of the form considered here since neither 54 nor 95 is prime).

this is good news, since it's not always easy to tell if a given number *is* a generator. as far as i know, trial-and-error is still the best method.