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 gp − 1 − 1 is not divisible by p2 and then g mod pn will be a primitive root forpn if it is divisible by p2 , just take g+p and that will be a generator mod pn 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 p2. 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 264 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 ke 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)
