5.4: Indices
( \newcommand{\kernel}{\mathrm{null}\,}\)
So for some values of n∈N, there exists a primitive root a∈(Z/nZ)∗, in which case we have seen that ⟨a⟩={a, a2, … aordn(a)}=(Z/nZ)∗ . That means that any b∈(Z/nZ)∗ is some power of a. “But which power?” you cry, so we make the:
Definition: Index
If n∈N has a primitive root a, then for any b∈Z such that gcd(b,n)=1 the smallest k∈N such that b≡ak(modn) is called the index of b relative to a and is denoted inda(b). We shall also sometimes talk about inda(x) where x∈(Z/nZ)∗, meaning the index relative to a of any representative b of the congruence class x.
Example 5.4.1
Working from the previous tables (5.0.1, 5.0.2, and 5.3.1), it is easy to compute a number of examples. First, for the smaller values of the moduli, where there are few primitive roots:
n | a | b | inda(b) |
---|---|---|---|
2 | 1 | 1 | 1 |
3 | 2 | 1 | 2 |
2 | 1 | ||
4 | 3 | 1 | 2 |
3 | 1 | ||
5 | 2 | 1 | 4 |
2 | 1 | ||
3 | 3 | ||
4 | 2 | ||
5 | 3 | 1 | 4 |
2 | 3 | ||
3 | 1 | ||
4 | 2 | ||
7 | 3 | 1 | 6 |
2 | 2 | ||
3 | 1 | ||
4 | 4 | ||
5 | 5 | ||
6 | 3 | ||
5 | 1 | 6 | |
2 | 4 | ||
3 | 5 | ||
4 | 2 | ||
5 | 1 | ||
6 | 3 |
For the two larger moduli we worked out above, only n=17 has primitive roots. Since (Z/17Z)∗ has 16 elements and 8 primitive roots, we make a larger table for just this modulus:
inda(b) | b | ||||||||||||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ||
a |
3 | 16 | 14 | 1 | 12 | 5 | 15 | 11 | 10 | 2 | 3 | 7 | 13 | 4 | 9 | 6 | 8 |
5 | 16 | 6 | 13 | 12 | 1 | 3 | 15 | 2 | 10 | 7 | 11 | 9 | 4 | 5 | 14 | 8 | |
6 | 16 | 2 | 15 | 4 | 11 | 1 | 5 | 6 | 14 | 13 | 9 | 3 | 12 | 7 | 10 | 8 | |
7 | 16 | 10 | 3 | 4 | 15 | 13 | 1 | 14 | 6 | 9 | 5 | 7 | 12 | 11 | 2 | 8 | |
10 | 16 | 10 | 11 | 4 | 7 | 5 | 9 | 14 | 6 | 1 | 13 | 15 | 12 | 3 | 2 | 8 | |
11 | 16 | 2 | 7 | 4 | 3 | 9 | 13 | 6 | 14 | 5 | 1 | 11 | 12 | 15 | 10 | 8 | |
12 | 16 | 6 | 5 | 12 | 9 | 11 | 7 | 2 | 10 | 15 | 3 | 1 | 4 | 13 | 14 | 8 | |
14 | 16 | 14 | 9 | 12 | 13 | 7 | 3 | 10 | 2 | 11 | 16 | 5 | 4 | 1 | 6 | 8 |
Some things are natural to conjecture, given these examples and the simple definition of index; many of them are very easy to prove (and are exercises):
Theorem 5.4.1
Let n∈N have a primitive root a. Then
- inda(1)=ordn(a)=ϕ(n); equivalently, inda(1)≡0(modϕ(n))
- inda(a)=1
- ∀b,c∈Z such that gcd(b,n)=gcd(c,n)=1, we have inda(bc)≡inda(b)+inda(c)(modϕ(n))
- ∀b∈Z such that gcd(b,n)=1 and ∀k∈N, we have inda(bk)≡k⋅inda(b)(modϕ(n))
These properties of inda are strikingly similar to the basic properties of a logarithm with base a. For this reason, indices are called discrete logarithms in the computer science literature. For cryptological applications, it is important to note that exponentiation in some (Z/nZ)∗ is an excellent candidate one-way function:
- Given n, a, and k, fast modular exponentiation is a feasible computation of b=ak in mod n.
- Given n, a, and b, no known feasible algorithm finds a k=inda(b) such that ak≡b(modn).
We will discuss some discrete logarithm-based cryptological protocols in the next sections.
Before turning to cryptology, we explore some pure mathematical applications of indices. Like the applications of logarithms in basic algebra, the usefulness of indices comes from the above Theorem 5.4.1 enabling convenient algebraic manipulations of powers and multiplications. Here’s an example:
Example 5.4.2
We use indices to solve the congruence 3x5≡4(mod7) by first taking ind5 of both sides ind5(3)+5ind5(x)≡ind5(4)(mod6) and applying all the rules in Theorem 5.4.2. Looking in Table 5.4.1, we translate that into 5+5⋅ind5(x)≡2(mod6) or, solving: ind5(x)≡5−1⋅3≡5⋅3≡3(mod6) which means, searching through the table again, that x=6.
Just to check, notice that 3⋅65=23328≡4(mod7).
What if we solve the same equation, but use a different primitive root in our indices? Compute ind3(3)+5ind3(x)≡ind3(4)(mod6) so 1+5⋅ind5(x)≡4(mod6) and this yields the same equation ind5(x)≡5−1⋅3≡3(mod6) and thus the same solution x=6.
Caution
A common mistake with indices is to use the same modulus with the indices as with the original congruence. Instead, when the congruence is in mod n, for n∈N, the index congruence is in mod ϕ(n)!
Exercise 5.4.1
- In the modulus n=17, use indices to solve the congruences
- 4x≡11
- 5x6≡7
- x12≡13
- 8x5≡10
- 9x8≡8
- 7x≡7
- The logarithm rules in Theorem 5.4.1 are very similar to rules for the usual logarithm, except one is missing: the change of base formula. Figure out what that should be in the context of indices, make a formal statement, and prove it.
- Let p be an odd prime and a a primitive root mod p.
- Prove that inda(−1)=(p−1)/2
- If x,y∈(Z/pZ)∗ satisfy xy≡1(modp), then what is the relationship between inda(x) and inda(y)? Prove it!
- If x,y∈(Z/pZ)∗ satisfy x+y≡0(modp), then what is the relationship between inda(x) and inda(y)? Prove it!