Readings:
Recall that in a ring R the units are the invertible elements. These elements form a group - the group of units. We will examine the structure of this group for the ring ZN, denoting the group of units ZN*.
Thm: In ZN*, a is a unit iff gcd(a, N) = 1.
Defn: (The Euler φ Function) φ(N) (also called the totient function) is defined as the number of positive integers a < N such that gcd(a, N) = 1. Equivalently, φ(N) is the number of elements in the group of units mod N.
Thm: (Euler's extension to Fermat's Little Thm, circa 1760)
If gcd(a, N) = 1 then
aφ(N) ≡ 1 (mod N)
proof: if gcd(a, N) = 1 then
(xa ≡ ya ⇔ x ≡ y)
Also, gcd(a, N) = 1 and gcd(x, N) = 1 implies that gcd(xa, N) = 1
So the map [x] → [xa] permutes the elements of ZN*
Thus {ax: x∈ZN*} is just a permutation of the elements ofZN*
So ∏xx ≡ ∏xxa ≡ aφ(N)∏xx
So aφ(N) ≡ 1 (mod N) as desired. ♠
Algorithm: (Finding Primitive Elements)
There is currently no deterministic method of finding primitive elements mod some prime p. It is true that if a single primitive element a is found, then others are easily generated, as ae is then primitive for any value of e which is coprime to p.
The lack of a deterministic algorithm for finding primitive elements is not of serious practical concern, as a large percentage of randomly chosen elements are primitive. Thus the simple algorithm of randomly choosing an element, checking it for primitivity and if it is not primitive trying again, is usually good enough.
Of more serious concern is the requirement to factor p-1 in order to check an element for primitivity mod p. This factoring step can prove to be a serious impediment in various algorithms which require primitive elements, such as proving the primality of p [appendix].
Another question is how many primitive elements there are modulo some prime p.
Thm: Given a cyclic group of order ω there are φ(ω) elements of the group which can generate it. (i.e. there are φ(ω) elements g such that G = ⟨g⟩.)
Corr: If p is prime then there are φ(φ(p)) primitive elements modulo p.
Defn: (The Carmichael λ Function)
λ(N) is defined as the smallest positive
integer such that
Thm: λ(N) | φ(N)
proof: Certainly λ(N) ≤ φ(N) from the definition of λ and Euler's extension of FLittleT
If λ does not divide φ then the division algorithm
gives a value r < λ such that r = xλ + yφ
So ar ≡
We would now like a (comparatively) simple way of computing &lamba;(N), as we have with φ(N). Not surprisingly, this will require factoring N, so for very large N this may not be practical, and a similar proof shows that computing λ(N) is equivalent to factoring N. The following theorem outlines a (conceptually) simple method for computing λ(N).
Thm:
Thm: If there is an element a which has order p-1 mod p then p is prime.
Algorithm: (Proving Primality)
Factor p-1 as q1e1q2e2...qnen
a larr; 2
label checkPrim
for i from 1 to n {
if ( aφ(p)/qi ≡ 1) {
a larr; a + 1
goto checkPrim
}
}
print "p is prime as a is primitive mod p"
Note that this seemingly simple algorithm has several hidden complexities. The factorization of p-1 can be very difficult. After the factorization we trust that each of the qi is itself prime. In order to be sure of this we should apply this primality proof algorithm to each qi, so our algorithm is now recursive, with each step examining a larger number of smaller primes. At the leaf nodes of this tree of primes should be some which are known to be prime, perhaps from some precomputed table of smallish primes.
In[1]:= EulerPhi[1221]
Out[1]= 720
In[2]:= CarmichaelLambda[1221]
Out[21]= 180
In[3]:= Needs["NumberTheory`"]
In[4]:= PrimitiveRoot[17^3]
Out[4]= 3
In[5]:= CarmichaelLambda[17^3]
Out[5]= 4624
In[6]:= FactorInteger[CarmichaelLambda[17^3]] (* Show that 3 is primitive *)
Out[6]= {{2, 4}, {17, 2}}
In[7]:= PowerMod[3,4624,17^3]
Out[7]= 1
In[8]:= PowerMod[3,4624/2,17^3]
Out[8]= 4912
In[9]:= PowerMod[3,4624/17,17^3]
Out[9]= 2891
> with(numtheory);
> phi(1221);
720
> lambda(1221);
180
> primroot(17^3);
3
> lambda(17^3);
4624
> ifactor(lambda(17^3)); (* Show that 3 is primitive *)
(2)^4 (17)^2
> Power(3,4624) mod 17^3;
1
> Power(3,4624/2) mod 17^3;
4912
> Power(3,4624/17) mod 17^3;
2891