N1H111SM's Miniverse

2020/03/06 Share

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)$：

# 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):

## Key generation

• 选取两个大质数 $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)$ 进行解密：