Primality Testing & Number Theory: Euler’s Totient, Primitive Roots, Miller-Rabin

TAKEAWAYS:

• Primality testing (trial division, Fermat, Miller-Rabin) determines if a number is prime, critical for generating cryptographic keys.
• Euler’s Totient function $\varphi (n)$ counts integers coprime to $n$, used in RSA encryption.
• Primitive roots enable efficient modular arithmetic in cryptographic protocols like Diffie-Hellman.
• Modular arithmetic ($a\equiv b\mathrm{mod}n$) underpins symmetric/asymmetric encryption and digital signatures.
• Number theory (GCD, LCM, Euler’s theorem) solves real-world problems like secure key exchange and password hashing.
• Miller-Rabin test is a probabilistic primality test faster than trial division, used in practice (e.g., Bitcoin).

Core Concepts: Why Number Theory Matters in Security

Cryptography relies on hard mathematical problems to secure data. This unit covers:

1. Primality testing: How to check if a number is prime efficiently (critical for RSA key generation).
2. Euler’s Totient function: Counts numbers coprime to $n$, used in RSA encryption/decryption.
3. Primitive roots: Simplify modular exponentiation in cryptographic protocols.
4. Modular arithmetic: The "math of clocks" that enables secure key exchange.

1. Primality Testing: Is It Prime?

A prime number has no divisors other than 1 and itself. Primes are the "atoms" of cryptography—used to generate keys in RSA, Diffie-Hellman, and blockchain.

Methods to Test Primality

Example: Trial Division

Question: Is 37 prime? Steps:

1. Check divisibility by primes ≤ $\sqrt{37}\approx 6.08$: 2, 3, 5.
2. 37 ÷ 2 = 18.5 → not divisible.
3. 37 ÷ 3 ≈ 12.33 → not divisible.
4. 37 ÷ 5 = 7.4 → not divisible. Conclusion: 37 is prime.

Miller-Rabin Primality Test (Probabilistic)

Algorithm:

1. Write $n-1$ as $d\cdot 2^s$ (e.g., for $n=341$, $340=4\cdot 2^4$).
2. Pick a random $a$ (1 < $a$ < $n-1$).
3. Compute $x=a^d\mathrm{mod}n$.
4. If $x\equiv 1$ or $x\equiv n-1$, $n$ might be prime.
5. Square $x$ up to $s-1$ times. If never $n-1$, $n$ is composite.

Worked Example: Test if 341 is prime (using $a=2$):

1. $340=4\cdot 2^4$ → $d=4$, $s=4$.
2. $x=2^4\mathrm{mod}341=16$.
3. $16\ne 1$ or $340$. Square $x$:
   • $16^2\mathrm{mod}341=256$.
   • $256^2\mathrm{mod}341=112$.
   • $112^2\mathrm{mod}341=340$ (now $n-1$). Result: 341 is not prime (since it passed, but we know $341=11\times 31$).

2. Euler’s Totient Function $\varphi (n)$

Counts integers up to $n$ that are coprime to $n$ (i.e., $\gcd (k,n)=1$).

Formula:

For $n=p_1^{k_1}{p}_2^{k_2}\dots p_m^{k_m}$: $$\varphi (n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\dots \left(1-\frac{1}{p_m}\right)$$

Example:

Compute $\varphi (30)$:

1. Factorize: $30=2\times 3\times 5$.
2. Apply formula: $$\varphi (30)=30\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=30\times \frac{1}{2}\times \frac{2}{3}\times \frac{4}{5}=8$$ Verification: Numbers coprime to 30 ≤ 30 are {1, 7, 11, 13, 17, 19, 23, 29} → 8 numbers.

Why It Matters:

• Used in RSA decryption: $c^d\mathrm{mod}n$ relies on $\varphi (n)$.
• Diffie-Hellman key exchange: Ensures shared secrets are unique.

3. Primitive Roots and Modular Arithmetic

A primitive root $g$ modulo $n$ is a number whose powers generate all numbers coprime to $n$.

Example:

For $n=7$, $g=3$ is a primitive root because: $$\begin{gathered} 3^1\mathrm{mod}7=3 \\ {3}^2\mathrm{mod}7=2 \\ {3}^3\mathrm{mod}7=6 \\ {3}^4\mathrm{mod}7=4 \\ {3}^5\mathrm{mod}7=5 \\ {3}^6\mathrm{mod}7=1 \end{gathered}$$ All residues {1, 2, 3, 4, 5, 6} are covered.

Application in Diffie-Hellman:

Alice and Bob agree on a prime $p$ and primitive root $g$. They exchange:

• Alice sends $A=g^a\mathrm{mod}p$.
• Bob sends $B=g^b\mathrm{mod}p$. Shared secret: $s=A^b\mathrm{mod}p=B^a\mathrm{mod}p=g^{ab}\mathrm{mod}p$.

4. Modular Arithmetic: The "Clock Math" of Crypto

Modular arithmetic solves $a\equiv b\mathrm{mod}n$ (i.e., $a-b$ is divisible by $n$).

Key Properties:

1. $(a+b)\mathrm{mod}n=[(a\mathrm{mod}n)+(b\mathrm{mod}n)]\mathrm{mod}n$.
2. $(a\times b)\mathrm{mod}n=[(a\mathrm{mod}n)\times (b\mathrm{mod}n)]\mathrm{mod}n$.
3. Euler’s Theorem: If $\gcd (a,n)=1$, then $a^{\varphi (n)}\equiv 1\mathrm{mod}n$.

Example: RSA Encryption

• Public key: $(e,n)$, where $e$ is coprime to $\varphi (n)$.
• Private key: $d$, where $d\equiv e^{-1}\mathrm{mod}\varphi (n)$.
• Encryption: $c=m^e\mathrm{mod}n$.
• Decryption: $m=c^d\mathrm{mod}n$.

In the Real World

1. eSewa/Khalti (Nepal):

   • Uses RSA (relying on primality testing) to encrypt payment data between your phone and their servers.
   • Example: When you pay a bill, your card number is split into primes, encrypted, and sent securely.

2. Bitcoin (Blockchain):

   • Elliptic Curve Cryptography (ECC) depends on hard number-theoretic problems (e.g., discrete logarithms).
   • Miners solve primality tests to validate transactions.

3. Ncell/NTC SIM Activation:

   • When you register a new SIM, the network uses Diffie-Hellman (primitive roots) to exchange a secret key with your phone’s chip, ensuring no eavesdropper can intercept your IMEI.

4. WhatsApp End-to-End Encryption:

   • Uses Signal Protocol, which relies on Euler’s Totient and modular arithmetic to generate session keys.

Visual: RSA Key Generation Flow

flowchart TD
    A["Choose two large primes\np, q (e.g., 61, 59)"] --> B["Compute n = p × q\n(e.g., 3599)"]
    B --> C["Compute φ(n) = (p-1)(q-1)\n(e.g., 3480)"]
    C --> D["Choose e coprime to φ(n)\n(e.g., 17)"]
    D --> E["Compute d ≡ e⁻¹ mod φ(n)\n(e.g., 2753)"]
    E --> F["Public Key: (e, n)\nPrivate Key: (d, n)"]

Visual: Miller-Rabin Test Steps

sequenceDiagram
    participant Tester
    participant Number as n
    participant Witness as a
    Tester->>Number: Write n-1 = d·2ˢ
    Tester->>Witness: Pick random a (1 < a < n-1)
    Tester->>Number: Compute x = aᵈ mod n
    alt x ≡ 1 or x ≡ n-1
        Tester->>Number: n is probably prime
    else
        loop s-1 times
            Tester->>Number: x = x² mod n
            alt x ≡ n-1
                Tester->>Number: n is probably prime
                break
            else
                Tester->>Number: n is composite
                break
            end
        end
    end

Visual: Euler’s Totient in RSA

classDiagram
    class Totient {
        +φ(n) = n × (1 - 1/p₁) × ... × (1 - 1/pₖ)
        +Used in RSA decryption: d ≡ e⁻¹ mod φ(n)
    }
    class RSA {
        +Public Key: (e, n)
        +Private Key: (d, n)
        +Encryption: c = mᵉ mod n
        +Decryption: m = cᵈ mod n
    }
    Totient --> RSA : "φ(n) enables d calculation"

Exam Tip

1. Primality Testing:

   • For trial division, always check up to $\sqrt{n}$.
   • For Miller-Rabin, remember the steps: decompose $n-1$, pick $a$, square until $n-1$ or composite.
   • Common pitfall: Forgetting to square $x$ up to $s-1$ times in Miller-Rabin.

2. Euler’s Totient:

   • Memorize the formula for prime powers: $\varphi (p^k)=p^k-p^{k-1}$.
   • Shortcut: For $n=p\times q$, $\varphi (n)=(p-1)(q-1)$.

3. Modular Arithmetic:

   • Practice computing $a^b\mathrm{mod}n$ using exponentiation by squaring (e.g., $3^{10}\mathrm{mod}7$).
   • Exam trick: If $\gcd (a,n)\ne 1$, Euler’s theorem doesn’t apply.

4. Real-World Links:

   • Always relate primality tests to RSA key generation or Diffie-Hellman.
   • Example answer starter: "In eSewa’s payment system, primality testing ensures that the public-private key pairs used to encrypt transactions are generated from large primes, preventing brute-force attacks."

Primality tests validate blockchain transactions (Image: Xiangfu, CC BY-SA 4.0, via Wikimedia Commons) Primitive roots enable secure key sharing (Image: de:Benutzer:DaMutz, CC BY-SA 4.0, via Wikimedia Commons)