Notes Cryptography Mathematical Foundations of Cryptography Totient Function and Euler's Theorem

Totient Function and Euler's Theorem

17 Dec 2021

§ Motivation

The Totient function is used in cryptosystems like RSA and is useful in computing number theoretic problems.

§ Euler's Totient Function

Euler's Totient Function

Euler's totient function is typically denoted using $\varphi(x)$ , defined as

\varphi(n) = \vert\{0 \leq k \lt n : (k, n) = 1\}\vert.

Or, $\varphi(n)$ is the number of non-negative numbers strictly less than $n$ that are co-prime with $n$ .

Properties:

If $p \in \mathbb{P}$ , then $\varphi\left(p\right) = p-1$
If $p \in \mathbb{P}$ $p \in P$ , then $\varphi\left(p^k\right) = p^{k-1}(p-1)$ $φ (p^{k}) = p^{k - 1} (p - 1)$
- In the case that $p = 2$ , it simply becomes $p^{k-1}$ . This fact is useful in implementing the Totient function as it allows us to use bit operations.
If $p, q \in \mathbb{N}$ and $(p, q) = 1$ , then $\varphi(pq) = \varphi(p)\cdot\varphi(q)$ (multiplicative)

Multiplicative Property

To reiterate: If $p, q \in \mathbb{N}$ and $(p, q) = 1$ , then

\varphi(p \cdot q) = \varphi(p)\cdot\varphi(q).

Any number $a \in \mathbb{N}$ can be written as a factorization of $m$ primes,

a = \prod_{i = 0}^{m} q_i^{e_i}.

Then, $\varphi(a)$ can be computed as:

\begin{align*} \varphi(a) &= \prod_{i = 0}^{m} \varphi\left(q_i^{e_i}\right)\\ &= \prod_{i = 0}^{m} \left[(q_i)^{e_i - 1}(q_i - 1)\right] \end{align*}

§ Euler's Theorem

The following lemma is used in the proof of Euler's theorem.

If $(a, b) = 1$ and $(b, c) = 1$ , then $(ac, b) = 1$ .

Write all three numbers in terms of their prime factorization and observe that $ac$ shares no common prime factors with $b$ .

Euler's Theorem

Let $(a, n) = 1$ , then

a^{\varphi(n)} \equiv_n 1.

Consider the numbers $ka \pmod{n}$ where $(k, n) = 1$ and $1 \leq k \lt n$ . If $ja \equiv_n ka$ , then another way to say this is $n \vert (j-k)a$ . Since $(a, n) = 1$ , we get that $n \vert (j - k)$ , which means $j - k = 0$ , so $j$ must equal $k$ . Hence, the elements in the sequence given by:

ka \pmod{n}, \text{ where } (k, n) = 1 \text{ and } 1 \leq k \lt n,

are all distinct, meaning

\prod_{(j,n) = 1} ka \equiv_n \prod_{(l, n) = 1} l

for $l, j \in [0\dots n)$ , since each element $ja$ is congruent to a remainder $l$ with $(l, n) = 1$ .

Notice that the left hand side is just $\left(\prod_{(j,n)=1} l\right)a^{\varphi(n)}$ . Since each term in the product is coprime with $n$ , we can cancel $\prod_{(j,n)=1} l$ from both sides and obtain

a^{\varphi(n)} \equiv_n 1.

Fermat's Little Theorem

In the specific case of Euler's theorem where $p$ is prime, we get that

a^{p-1} \equiv 1 \pmod{p}.

One example of Euler's theorem being applied is in exponentation:

g^x \pmod{n}

in cases where $x > \varphi(n)$ , we can reduce this problem to be

g^{x} \equiv g^{(x \mod{\varphi(n)})} \pmod{n}.

Furthermore, observe

g^{a^b} \equiv g^{(a \mod{\varphi(n)})^{\scriptstyle(b \mod{\varphi^2(n)})}} \pmod{n},

where $\varphi^2(n) \triangleq \varphi(\varphi(n)).$

§ Carmichael's Totient Function

We didn't talk about the Carmichael function in our MATH-470, however, this becomes useful in discussing the RSA algorithm.

Carmichael's Totient Function

Carmichael's totient uses the notation $\lambda(n)$ , and is defined to be the smallest positive integer $m$ satisfying

a^{m} \equiv 1 \pmod{n},

for all $a \in [1\dots n)$ such that $(a, n) = 1$ .

§ Computing the Carmichael Function

Using results from Carmichael's theorem, we can find that $\lambda(n)$ can be computed in terms of Euler's totient function.

\lambda\left(p^r\right) = \begin{cases} \varphi\left(p^r\right) & \text{if } p \in \mathbb{P}, \text{or } p = 4\\ \frac{1}{2}\varphi\left(p^r\right) & \text{if } p = 2 \text{ and } r \geq 3 \end{cases}