alt
Reputation
Top tag
Next privilege 100 Rep.
Edit community wikis
Badges
3
Newest
Impact
~12k people reached

• 0 helpful flags
• 9 votes cast

# 3 Comments

 May30 comment How to test if a number is a primitive root? You will see in that reference that often a choice of $p$ is made so that the factorization of $p-1$ is already known. Primality testing is a separate issue, but it is well-studied. In practice, the Miller-Rabin primality test performs well. May30 comment How to test if a number is a primitive root? I am sure there is some software to do this already. If $p$ is prime, $p-1$ cannot be prime since $2 | p-1$, but $(p-1)/2$ may be prime (although this is not that likely; 'safe' primes do not have small prime factors, each should be roughly the same size). Another source: cacr.uwaterloo.ca/~dstinson/papers/cs877s10.ps‎ May30 comment How to test if a number is a primitive root? I could easily write a program for this, the question is whether it makes sense for the bit-length of $p$ that you are considering. If it is 32 bits, for example, then no problem. Any larger than that and I cannot guarantee anything.. computing the prime factorization of $p-1$ is expensive (for 64 bit $p$, it costs 2^32 work, doable but slow if you want many generators). edit: doing this now.