Talk:Primitive root modulo n

From Wikipedia, the free encyclopedia

[edit] An algorithm

I am no expert on the subject, but as I am reading from Leveque, there is sort of an algorithm for finding primitive roots for higher powers of a prime when you already have a primitive root for odd p

let g be an integer, such that g mod p generates all elements of the field mod p, except zero

now either g^{p − 1} − 1 is not divisible by p² and then g mod pⁿ will be a primitive root forpⁿ if it is divisible by p² , just take g+p and that will be a generator mod pⁿ what do you think?

Evilbu 21:43, 15 February 2006 (UTC)

I'm not sure what the question is. If this is a theorem given by Leveque, its certainly appropriate to add it to the article. If this theorem has a name, that's even better: the section gets called 'so-and-so's theorem'. If you are saying "I just discovered a new algorithm; is it correct?" then I'll say "I don't know if its correct", and "don't add it to the article". linas 22:27, 15 February 2006 (UTC)

Well Leveque first proves this theorem of how orders mod p and mod p^n on an integer are related. Next he just says and this implies existence of primitive root, just do this. He doesn't make a fuss about the construction, it has no name, it's just part of his proof of existence of primitive root.

Another thing I forgot, and I am quite sure of this, when x (integer) is mod p^n a primitive root, then, if x is odd, it is also such for mod p^n,and otherwise x+p^n will be a primitive root mod p^n

that way it really comes down to finding primitive roots mod p?

Evilbu 22:47, 15 February 2006 (UTC)

This is a kind of Hensel's lemma application, I think. You can refine a 'solution' mod p to mod p². etc. The lemma is Newton's method, really, while this case is simple enough to do directly. Charles Matthews 23:04, 15 February 2006 (UTC)

[edit] Algorithms

In order to make algorithms such as the number-theoretic transform work, one has to compute, in practice, a nth root of the unit in Z/pZ where n divides p-1, and n is most often a power of two. This is done easily provided one has a generator of Z/pZ*. Thus, it would be interesting to discuss algorithms for finding this generator, or primitive roots. David.Monniaux 08:31, 14 October 2006 (UTC)

Probabilistic? Assuming one has factorised p − 1 already?. The chance that 2, or 3, or 5 is a primitive root is not small. Charles Matthews 12:19, 14 October 2006 (UTC)

For the cases I'm interested in p is likely to be in the range of 2⁶⁴ at most, so it will be easily factorizable. Do you suggest I factor p, then compute φ(p), try k^φ(p) for such values of k as 2, 3 or 5, then check for k^e where e is a divisor of φ(p)? Er... It may work, indeed! David.Monniaux 13:46, 14 October 2006 (UTC)

Yes, this might be practical. According to Artin's conjecture on primitive roots, 2 is a primitive root with a probability like 37%. And in most cases where you are unlucky it is because 2 is a quadratic residue mod p, which is a trivial calculation for rejection, as I guess you know, and will affect 50% of choices. Charles Matthews 16:36, 14 October 2006 (UTC)