Editing Primitive root modulo n (section)

==Finding primitive roots==

No simple general formula to compute primitive roots modulo {{mvar|n}} is known.{{efn|"One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots. {{Harvnb|von zur Gathen|Shparlinski|1998|pp=15–24}} }}{{efn|"There is no convenient formula for computing [the least primitive root]." {{Harvnb|Robbins|2006|p=159}} }} There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the [[multiplicative order]] (its [[Torsion group|exponent]]) of a number {{mvar|m}} modulo {{mvar|n}} is equal to [[Euler's phi function|<math>\varphi(n)</math>]] (the order of <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}), then it is a primitive root. In fact the converse is true: If {{mvar|m}} is a primitive root modulo {{mvar|n}}, then the multiplicative order of {{mvar|m}} is <math>\varphi(n) = \lambda(n)~.</math> We can use this to test a candidate {{mvar|m}} to see if it is primitive.

For <math>n > 1</math> first, compute <math>\varphi(n)~.</math> Then determine the different [[prime factor]]s of <math>\varphi(n)</math>, say {{mvar|p}}<sub>1</sub>, ..., {{mvar|p{{sub|k}}}}. Finally, compute
:<math>g^{\varphi(n)/p_i}\bmod n \qquad\mbox{ for } i=1,\ldots,k</math>
using a fast algorithm for [[modular exponentiation]] such as [[exponentiation by squaring]]. A number {{mvar|g}} for which these {{mvar|k}} results are all different from 1 is a primitive root.

The number of primitive roots modulo {{mvar|n}}, if there are any, is equal to<ref>{{OEIS|A010554}}</ref>
:<math>\varphi\left(\varphi(n)\right)</math>
since, in general, a cyclic group with {{mvar|r}} elements has <math>\varphi(r)</math> generators.

For prime {{mvar|n}}, this equals <math>\varphi(n-1)</math>, and since <math>n / \varphi(n-1) \in O(\log\log n)</math> the generators are very common among {2, ..., {{mvar|n}}&minus;1} and thus it is relatively easy to find one.<ref name=Knuth-1998/>

If {{mvar|g}} is a primitive root modulo {{mvar|p}}, then {{mvar|g}} is also a primitive root modulo all powers {{mvar|p{{sup|k}}}} unless {{mvar|g}}<sup>{{mvar|p}}−1</sup> ≡ 1 (mod {{mvar|p}}<sup>2</sup>); in that case, {{mvar|g}} + {{mvar|p}} is.<ref name="Cohen1993"/>

If {{mvar|g}} is a primitive root modulo {{mvar|p{{sup|k}}}}, then {{mvar|g}} is also a primitive root modulo all smaller powers of {{mvar|p}}.

If {{mvar|g}} is a primitive root modulo {{mvar|p{{sup|k}}}}, then either {{mvar|g}} or {{mvar|g}} + {{mvar|p{{sup|k}}}} (whichever one is odd) is a primitive root modulo 2{{mvar|p{{sup|k}}}}.<ref name="Cohen1993"/>

Finding primitive roots modulo {{mvar|p}} is also equivalent to finding the roots of the ({{mvar|p}} − 1)st [[cyclotomic polynomial]] modulo {{mvar|p}}.