Materials
Euler’s totient function
Definition (Euler’s totient function). In number theory, Euler’s totient function $\phi(n)$ counts the positive integers up to a given integer $n$ that are relatively prime to $n$. The Euler’s totient function is computed by the following formula:
where the product is over the distinct prime numbers dividing $n$.
Derivation
When $(n=1)$：
When $(n=p)$：
When $(n=p^k)$：
When $(n=p_1p_2)$：
因为任意一个整数$n$都能够表示成$n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$的形式，所以根据以上四种情况的结论我们有：
Euler’s theorem
In number theory, Euler’s theorem (also known as the Fermat–Euler theorem or Euler’s totient theorem) states that if $n$ and $a$ are coprime positive integers, then
RSA Algorithm
The RSA algorithm involves four steps: key generation, key distribution, encryption and decryption.
A basic principle behind RSA is the observation that it is practical to find three very large positive integers $e$, $d$ and $n$ such that with modular exponentiation for all integers $ m$ (with 0 ≤ m < n):
上面的式子里，$e$ 是进行加密的public key, $d$ 是用来解密的private key。
Key generation
假设Alice和Bob是需要加密通信的两个主人公。Alice可以通过以下步骤生成public key & private key：
- 选取两个大质数 $p$ 和 $q$，计算$N=pq$
- 计算 $N$ 的欧拉函数值 $r=\varphi(N)=(p-1)(q-1)$
- 找到一个小于 $r$ 并与 $r$ 互质的整数 $e$，同时求出 $e$ 关于 $r$ 的模的逆元，即 $ed \equiv 1 \pmod r$
- 将两个大质数 $p, q$ 的记录销毁
- 得到公钥$(N,e)$和私钥$(N,d)$。
- 将公钥发送给Bob，Alice自己保管私钥不被公开。
Encryption
Bob对明文 $m$ 通过公钥$(N,e)$进行加密并发送给Alice：
Decryption
Alice将收到的密文 $c$ 通过私钥 $(N,d)$ 进行解密：