Finding Primitive Roots
No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates.
If the multiplicative order of a number m modulo n is equal to (the order of Zn×), then it is a primitive root. In fact the converse is true: If m is a primitive root modulo n, then the multiplicative order of m is . We can use this to test for primitive roots.
First, compute . Then determine the different prime factors of, say p1, ..., pk. Now, for every element m of Zn*, compute
using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number m for which these k results are all different from 1 is a primitive root.
The number of primitive roots modulo n, if there are any, is equal to
since, in general, a cyclic group with r elements has generators.
If g is a primitive root modulo p, then g is a primitive root modulo all powers pk unless g p – 1 ≡ 1 (mod p2); in that case, g + p is.
If g is a primitive root modulo pk, then g or g + pk (whichever one is odd) is a primitive root modulo 2pk.
Finding primitive roots modulo p is also equivalent to finding the roots of the (p-1)th cyclotomic polynomial modulo p.
Read more about this topic: Primitive Root Modulo n
Famous quotes containing the words finding, primitive and/or roots:
“To have no son, no wife,
No house or land still seemed quite natural.
Only a numbness registered the shock
Of finding out how much had gone of life,
How widely from the others.”
—Philip Larkin (1922–1986)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“Our roots are in the dark; the earth is our country. Why did we look up for blessing—instead of around, and down? What hope we have lies there. Not in the sky full of orbiting spy-eyes and weaponry, but in the earth we have looked down upon. Not from above, but from below. Not in the light that blinds, but in the dark that nourishes, where human beings grow human souls.”
—Ursula K. Le Guin (b. 1929)