5.4: Indices

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

So for some values of \(n\in\NN\), there exists a primitive root \(a\in(\ZZ/n\ZZ)^*\), in which case we have seen that \[\left<a\right>=\left\{a,\ a^2,\ \dots\ a^{\ord_n(a)}\right\}=(\ZZ/n\ZZ)^*\ .\] That means that any \(b\in(\ZZ/n\ZZ)^*\) is some power of \(a\). “But which power?” you cry, so we make the:

Definition: Index

If \(n\in\NN\) has a primitive root \(a\), then for any \(b\in\ZZ\) such that \(\gcd(b,n)=1\) the smallest \(k\in\NN\) such that \(b\equiv a^k\pmod{n}\) is called the index of \(b\) relative to \(a\) and is denoted \(\ind_a(b)\). We shall also sometimes talk about \(\ind_a(x)\) where \(x\in(\ZZ/n\ZZ)^*\), meaning the index relative to \(a\) of any representative \(b\) of the congruence class \(x\).

Example \(\PageIndex{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:

Table 5.4.1: Index Values for Moduli \(n=2,\ 3,\ 4,\ 5,\ 7\)

\(n\)	\(a\)	\(b\)	\(\ind_a(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 \((\ZZ/17\ZZ)^*\) has \(16\) elements and \(8\) primitive roots, we make a larger table for just this modulus:

Table 5.4.2: Index Values for Modulus \(n=17\)

\(\text{ind}_a (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 \(\PageIndex{1}\)

Let \(n\in\NN\) have a primitive root \(a\). Then

1. \(\ind_a(1)=\ord_n(a)=\phi(n)\); equivalently, \(\ind_a(1)\equiv0\pmod{\phi(n)}\)
2. \(\ind_a(a)=1\)
3. \(\forall b,c\in\ZZ\) such that \(\gcd(b,n)=\gcd(c,n)=1\), we have \[\ind_a(bc)\equiv\ind_a(b)+\ind_a(c)\pmod{\phi(n)}\]
4. \(\forall b\in\ZZ\) such that \(\gcd(b,n)=1\) and \(\forall k\in\NN\), we have \[\ind_a(b^k)\equiv k\cdot\ind_a(b)\pmod{\phi(n)}\]

These properties of \(\ind_a\) 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 \((\ZZ/n\ZZ)^*\) is an excellent candidate one-way function:

• Given \(n\), \(a\), and \(k\), fast modular exponentiation is a feasible computation of \(b=a^k\) in mod \(n\).
• Given \(n\), \(a\), and \(b\), no known feasible algorithm finds a \(k=\ind_a(b)\) such that \(a^k\equiv b\pmod{n}\).

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 \(\PageIndex{2}\)

We use indices to solve the congruence \[3x^5\equiv4\pmod{7}\] by first taking \(\ind_5\) of both sides \[\ind_5(3)+5\ind_5(x)\equiv\ind_5(4)\pmod{6}\] and applying all the rules in Theorem 5.4.2. Looking in Table 5.4.1, we translate that into \[5+5\cdot\ind_5(x)\equiv2\pmod{6}\] or, solving: \[\ind_5(x)\equiv5^{-1}\cdot3\equiv5\cdot3\equiv3\pmod{6}\] which means, searching through the table again, that \(x=6\).

Just to check, notice that \(3\cdot6^5=23328\equiv4\pmod{7}\).

What if we solve the same equation, but use a different primitive root in our indices? Compute \[\ind_3(3)+5\ind_3(x)\equiv\ind_3(4)\pmod{6}\] so \[1+5\cdot\ind_5(x)\equiv4\pmod{6}\] and this yields the same equation \[\ind_5(x)\equiv5^{-1}\cdot3\equiv3\pmod{6}\] 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\in\NN\), the index congruence is in mod \(\phi(n)\)!

Exercise \(\PageIndex{1}\)

1. In the modulus \(n=17\), use indices to solve the congruences
   1. \(4x\equiv11\)
   2. \(5x^6\equiv7\)
   3. \(x^{12}\equiv13\)
   4. \(8x^5\equiv10\)
   5. \(9x^8\equiv8\)
   6. \(7^x\equiv7\)
2. 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.
3. Let \(p\) be an odd prime and \(a\) a primitive root mod \(p\).

• Prove that \(\ind_a(-1)=(p-1)/2\)
• If \(x,y\in(\ZZ/p\ZZ)^*\) satisfy \(xy\equiv1\pmod{p}\), then what is the relationship between \(\ind_a(x)\) and \(\ind_a(y)\)? Prove it!
• If \(x,y\in(\ZZ/p\ZZ)^*\) satisfy \(x+y\equiv0\pmod{p}\), then what is the relationship between \(\ind_a(x)\) and \(\ind_a(y)\)? Prove it!