Primitive Root

Context: FIT1058_MOC · a generator of ${\mathbb{Z}}_n^{\ast }$ · powers reach $1$ only at the full exponent $\varphi (n)$ · gives the largest range for a one-way function

Quick Revision

• 🎯 Objective: $x$ whose powers reach 1 no earlier than $k=\varphi (n)$ ➔ a generator of ${\mathbb{Z}}_n^{\ast }$.
• 📦 Core Components: order $\varphi (n)$ ➔ powers exhaust ${\mathbb{Z}}_n^{\ast }$ ➔ $\varphi (\varphi (n))$ of them.
• ⚡ Key Constraint: exists only for $n=1,2,4,p^k,2p^k$; no efficient algorithm to find one.

📝 Core

1. The Definition

• Primitive root ➔ $x^k\not\equiv 1(\mathrm{mod}n)$ for all $k<\varphi (n)$.
• Generator ➔ then $x,x^2,\dots ,x^{\varphi (n)}$ run through all of ${\mathbb{Z}}_n^{\ast }$.
• Example ➔ 3 mod 7 gives $3,2,6,4,5,1$ (all six); 2 gives $2,4,1,\dots$ (only $\{1,2,4\}$, not primitive).

2. Existence

• Theorem ➔ primitive roots exist exactly for $n=1,2,4,p^k,2p^k$ ($p$ odd prime).
• No root ➔ 8 has none (${\mathbb{Z}}_8^{\ast }$ each squares to 1).
• Must be in ${\mathbb{Z}}_n^{\ast }$ ➔ non-units’ powers hit 0 and stick.

3. Count & Difficulty

• How many ➔ exactly $\varphi (\varphi (n))$ if any exist.
• Finding ➔ no known polynomial-time algorithm.

Key identities:

$x\text{ primitive}⟺x^k\not\equiv 1(\mathrm{mod}n)\text{ for }k<\varphi (n)$ $3\mathrm{mod}7:3,2,6,4,5,1(\text{first }1\text{ at }k=6=\varphi (7))\Rightarrow \text{primitive}$

⚖️ Core Decision Matrix

$n$	Primitive root?	Reason
prime $p$	yes	$\varphi (p)=p-1$, maximal
$p^k,2p^k$	yes	characterisation
8 ($=2^3$)	no	excluded form
count	$\varphi (\varphi (n))$	if any exist

When It Flips: a primitive root's powers cover all of ${\mathbb{Z}}_n^{\ast }$ — the widest spread — making $x\mapsto a^x$ hardest to invert, so a primitive root of a large prime is chosen for the One-Way Function behind Diffie-Hellman Key Agreement.

📊 Exam Execution Trace

Manual Execution Trace

Powers of 2 mod 11 ($\varphi =10$):

Step / State	$k$	$2^k\mathrm{mod}11$
0 (Init)	—	—
1	1–5	2,4,8,5,10
2	6–10	9,7,3,6,1
3	first 1	$k=10=\varphi (11)$

⚠️ Common Mistakes

• 💡 Existence restricted ➔ only $n=1,2,4,p^k,2p^k$ have primitive roots; 8 does not (all of ${\mathbb{Z}}_8^{\ast }$ have order $\le 2<4$).

🧠 Active Recall

Define a primitive root and verify 3 is one mod 7 but 2 is not.

• Hint: Order = $\varphi (n)$.

Answer

• Short answer: Powers reach 1 only at $k=\varphi (n)$; $3\mathrm{mod}7$ gives all six, $2$ hits 1 at $k=3<6$.
• Why: Generator ➔ 3’s powers exhaust ${\mathbb{Z}}_7^{\ast }$; 2’s cover only $\{1,2,4\}$.

Why does 8 have no primitive root, and why are primitive roots wanted in cryptography?

• Hint: Existence form + max range.

Answer

• Short answer: ${\mathbb{Z}}_8^{\ast }$ each square to 1 (order $\le 2<4$); only $1,2,4,p^k,2p^k$ have roots.
• Why: Widest spread ➔ powers span all of ${\mathbb{Z}}_n^{\ast }$, making $a^x$ hardest to invert.