加密訊息時，RSA 把訊息看成一個大數，而加密本質上就是大數的乘法。因此要理解 RSA 如何運作，我們得知道它操作的是哪種大數，以及乘法在這些數上如何運作。

RSA 把它所加密的明文視為介於 1 與 n − 1 之間的正整數，其中 n 是一個稱為模數（modulus）的大數。這些數相乘會得到另一個同樣滿足此條件的數——我們說它們構成一個群，記為 Zn*，稱為模 n 整數乘法群。

兩個小例子#

Z4*#

回想群必須包含單位元（也就是 1），且群中每個數 x 都必須有反元素——一個滿足 x × y = 1 的數 y。

• 0 不在群中：任何數乘以 0 永遠得不到 1，所以 0 沒有反元素。
• 1 在群中：1 × 1 = 1，1 是自己的反元素。
• 2 不在群中：無法用 Z4* 中另一個元素乘上 2 得到 1。原因是 2 與 4 不互質（4 和 2 共有因數 2）。
• 3 在群中：3 × 3 = 9 = 1 mod 4，3 是自己的反元素。

因此 Z4* = {1, 3}。

Z5*#

5 是質數，而 1、2、3、4 都與 5 互質，所以 Z5* = {1, 2, 3, 4}。驗證一下：

2 × 3 mod 5 = 1     → 2 與 3 互為反元素
4 × 4 mod 5 = 1     → 4 是自己的反元素
1 × 1 mod 5 = 1     → 1 是自己的反元素

歐拉函數#

要在 n 不是質數時算出群 Zn* 的元素個數，我們使用歐拉函數（Euler’s totient function），寫作 φ(n)。這個函式給出與 n 互質的元素個數，也就是 Zn* 中的元素個數。

一般規則：若 n 是質數的乘積 n = p₁ × p₂ × ... × pm，則群 Zn* 中的元素個數為：

φ(n) = (p₁ − 1)(p₂ − 1) ... (pm − 1)

RSA 的情況#

對應的群 Zn* 因此包含：

φ(n) = (p − 1)(q − 1)

個元素。

展開這個式子，我們得到等價的定義：

φ(n) = n − p − q + 1
     = (n + 1) − (p + q)

後者更直觀地表達了 φ(n) 相對於 n 的值。