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:
“Love has its own instinct, finding the way to the heart, as the feeblest insect finds the way to its flower, with a will which nothing can dismay nor turn aside.”
—Honoré De Balzac (1799–1850)
“It was a purely wild and primitive American sound, as much as the barking of a chickaree, and I could not understand a syllable of it.”
—Henry David Thoreau (1817–1862)
“Though of erect nature, man is far above the plants. For man’s superior part, his head, is turned toward the superior part of the world, and his inferior part is turned toward the inferior world; and therefore he is perfectly disposed as to the general situation of his body. Plants have the superior part turned towards the lower world, since their roots correspond to the mouth, and their inferior parts towards the upper world.”
—Thomas Aquinas (c. 1225–1274)