密碼學/數學背景

請參閱討論頁面獲取其他建議。

簡介

現代公鑰（非對稱）密碼學基於一個稱為數論的數學分支，該分支專門處理僅產生整數結果的方程的求解。這類方程被稱為丟番圖方程，以希臘數學家丟番圖（約公元 200 年）命名，他在其著作算術中討論了需要這種整數解的問題。

最古老的丟番圖問題之一被稱為畢達哥拉斯問題，該問題在給出直角三角形的其他兩條邊的長度時，根據以下方程給出直角三角形的一條邊的長度：

$a^{2}+b^{2}=c^{2}\$

其中$c\$ 是斜邊的長度。雖然兩條邊可能是已知的整數，但得到的第三條邊很可能是無理數。畢達哥拉斯問題的解並不超出範圍，但超出了本章的目的。因此，這裡將簡單地給出整數解的示例（稱為畢達哥拉斯三元組）。尋找其他解，無論是透過蠻力還是推導，都留給讀者作為練習。

畢達哥拉斯三元組

$a\$	$b\$	$c\$
3	4	5
5	12	13
7	24	25
8	15	17

素數

描述

非對稱金鑰演算法在操作中嚴重依賴於素數的使用，通常是極長的素數。根據定義，素數只能被自身和 1 整除。換句話說，用符號 | 表示可除性（即 - $a|b$ 表示“$b$ 可以整除 $a$”），素數嚴格遵守以下數學定義

$p\$ | $b\$ 其中 $b=1\$ 或僅 $p\$

算術基本定理 指出所有整數都可以分解成唯一的素數分解。任何大於 1 的整數都被認為是素數或合數。合數由不止一個素因子組成

$c\$ | $b\$ 最終其中 $b=p_{0}^{e_{0}}p_{1}^{e_{1}}\cdot \cdot \cdot p_{n}^{e_{n}}\$

其中 $p_{n}\$ 是一個唯一的素數，而 $e_{n}\$ 是指數。

數值示例

543,312 = 24 $\cdot$ 32 $\cdot$ 50 $\cdot$ 73 $\cdot$ 111
553,696 = 25 $\cdot$ 30 $\cdot$ 50 $\cdot$ 70 $\cdot$ 113 $\cdot$ 131

如您所見，根據這種系統分解，每個分解都是唯一的。

為了確定性地驗證一個整數 $a\$ 是素數還是合數，只需要檢查素數 $p\leq {\sqrt {c}}\$。這種系統的、徹底的檢查被稱為窮舉法。素數和合數在密碼學研究中值得注意，因為通常公鑰是一個合數，它是兩個或多個素數的乘積。這些素數中的一個（或多個）可能構成私鑰。

素數有幾種型別和類別，其中三種對密碼學很重要，將在下面簡要討論。

費馬素數

費馬數 採用以下形式

$F_{n}=2^{2^{n}}+1\$

如果F_n 是素數，則稱為費馬素數。

數值示例

$F_{0}=2^{2^{0}}+1=3\$
$F_{1}=2^{2^{1}}+1=5\$
$F_{2}=2^{2^{2}}+1=17\$
$F_{3}=2^{2^{3}}+1=257\$
$F_{4}=2^{2^{4}}+1=65,537\$
$F_{5}=2^{2^{5}}+1=4,294,967,297\$

已知唯一的費馬素數是 $F_{0}-F_{4}\$。此外，尤拉證明了所有費馬數的素性都是錯誤的，他證明了 $F_{5}=641\cdot 6,700,417$。

梅森素數

梅森素數 - 另一種公式化的素數生成方法 - 遵循以下形式

$M_{p}=2^{p}-1\$

其中 $p\$ 是一個素數。 [1] Wolfram Alpha 引擎報告梅森素數，例如輸入請求為“第 4 個梅森素數”。

數值示例

前四個梅森素數如下

$M_{2}=2^{2}-1=3\$
$M_{3}=2^{3}-1=7\$
$M_{5}=2^{5}-1=31\$
$M_{7}=2^{7}-1=127\$

M_p = 2^p 形式的數，不考慮素數要求，被稱為梅森數。並非所有的梅森數都是素數，例如 M₁₁ = 2¹¹−1 = 2047 = 23 · 89。

互素數（相對素數）

如果兩個數的最大公約數為 1，則稱這兩個數為互素數。從數學上講，這可以寫成

$\gcd(a,b)=1\$

其中 $\gcd \$ 是最大公約數。可以從上述定義中推匯出兩條規則

如果 $ab\$ | $c\$ 並且 $\gcd(b,c)=1\$，則 $a\$ | $c\$

如果 $ab=c^{2}\$ 並且 $\gcd(a,b)=1\$，則 $a\$ 和 $b\$ 都是平方數，即 - $a=a_{0}^{2}\$，$b=b_{0}^{2}\$

素數定理

素數定理估計了隨機選擇的任何整數是素數的機率。估計如下，其中 $\pi (x)\$ 定義為小於或等於 $x\$ 的素數數量。

$\pi (x)\approx {\frac {x}{\ln x}}\$

$\pi (x)\$ 是 ${\frac {x}{\ln x}}\$ 的漸近線，也就是說 $\quad \lim _{x\to \infty }{\frac {\pi (x)}{\frac {x}{\ln x}}}=1\$。這意味著，一般來說，隨機選擇的數字是素數的機率約為 ${\tfrac {1}{\ln x}}\$。

歐幾里得演算法

簡介

歐幾里得演算法用於發現兩個整數的最大公約數。在密碼學中，它最常用於確定兩個整數是否互素，即 - $\gcd(a,b)=1\$。

為了高效地找到$\gcd(a,b)\$，其中$a>b\$，尤其是在處理密碼系統等涉及非常大的數字時，存在一種方法可以實現。歐幾里得演算法的運作方式如下：首先，用$b\$除$a\$，得到商$q_{1}\$和餘數$r_{1}\$。注意，這可以用方程的形式寫成$a=q_{1}b+r_{1}\$。接下來，使用$b\$替換$a\$的位置，執行相同的操作：$b=q_{2}r_{1}+r_{2}\$。繼續這種模式，直到最後的餘數為零。後面的數值示例和正式演算法將使這種內在的模式更加清晰。

數學描述

$a=q_{1}b+r_{1}\$
$b=q_{2}r_{1}+r_{2}\$
$r_{1}=q_{3}r_{2}+r_{3}\$
$r_{2}=q_{4}r_{3}+r_{4}\$
$\cdot \$
$\cdot \$
$\cdot \$
$r_{n-2}=q_{n}r_{n-1}+r_{n}\$

當$r_{n}=0\$時，停止，並有$\gcd(a,b)=r_{n-1}\$.

數值示例

示例 1 - 尋找 gcd(17,043,12,660)

17,043 = 1 $\cdot$ 12,660 + 4383
12,660 = 2 $\cdot$ 4,383 + 3894
 4,383 = 1 $\cdot$ 3,894 + 489
 3,894 = 7 $\cdot$ 489 + 471
   489 = 1 $\cdot$ 471 + 18
   471 = 26 $\cdot$ 18 + 3
    18 = 6 $\cdot$ 3 + 0

gcd (17,043,12,660) = 3

示例 2 - 尋找 gcd(2,008,1,963)

2,008 = 1 $\cdot$ 1,963 + 45
1,963 = 43 $\cdot$ 45 + 28
   45 = 1 $\cdot$ 28 + 17
   28 = 1 $\cdot$ 17 + 11
   17 = 1 $\cdot$ 11 + 6
   11 = 1 $\cdot$ 6 + 5
    6 = 1 $\cdot$ 5 + 1
    5 = 5 $\cdot$ 1 + 0

gcd (2,008,1963) = 1 注：這兩個數字互質。

演算法表示

Euclidean Algorithm(a,b)
Input:     Two integers a and b such that a > b
Output:    An integer r = gcd(a,b)
  1.   Set a0 = a, r1 = r
  2.   r = a0 mod r1
  3.   While(r1 mod r $\neq$ 0) do:
  4.      a0 = r1
  5.      r1 = r
  6.      r = a0 mod r1
  7.   Output r and halt

擴充套件歐幾里得演算法

為了解決由貝祖恆等式表示的方程式型別，如下所示

$au+bv=\gcd(a,b)\$

當 $a\$，$b\$，$u\$ 和 $v\$ 是整數，通常使用 _擴充套件歐幾里得演算法_ 會很有用。 上述形式的方程出現在 RSA（Rivest-Shamir-Adleman）等公鑰加密演算法中，形式為 $ed+w(p-1)(q-1)=1\$，其中 $\gcd(e,(p-1)(q-1))=1\$。 實現擴充套件歐幾里得演算法有兩種方法：_迭代法_ 和 _遞迴法_。

例如，我們將解決一個 RSA 金鑰生成問題，其中 _e_ = 2¹⁶ + 1，_p_ = 3,217，_q_ = 1,279。 因此，62,537_d_ + 51,456_w_ = 1。

方法

迭代法

此方法計算形式為 $r_{i}=ax_{i}+by_{i}$ 的表示式，用於歐幾里得演算法每一步 $i$ 中的餘數。 每個 模數 可以用前兩個餘數及其整數商表示，如下所示

$r_{i}=r_{i-2}-\left\lfloor {\frac {r_{i-2}}{r_{i-1}}}\right\rfloor \cdot r_{i-1}$

透過替換，這給出了

$r_{i}=(ax_{i-2}+by_{i-2})-\left\lfloor {\frac {r_{i-2}}{r_{i-1}}}\right\rfloor \cdot (ax_{i-1}+by_{i-1})$

$r_{i}=a(x_{i-2}-\left\lfloor {\frac {r_{i-2}}{r_{i-1}}}\right\rfloor \cdot x_{i-1})+b(y_{i-2}-\left\lfloor {\frac {r_{i-2}}{r_{i-1}}}\right\rfloor \cdot y_{i-1})$

前兩個值是演算法的初始引數

$r_{1}=a=a(1)+b(0)\$

$r_{2}=b=a(0)+b(1)\$

最後一個非零餘數的表示式給出了所需的結果，因為這種方法計算了每個餘數，並用*a* 和 *b* 表示，正如預期的那樣。

例子

步驟	商	餘數	代入	合併項
1		4,110,048 = *a*		4,110,048 = 1*a* + 0*b*
2		65,537 = *b*		65,537 = 0*a* + 1*b*
3	62	46,754 = 4,110,048 - 65,537 $\cdot$ 62	46,754 = (1*a* + 0*b*) - (0*a* + 1*b*) $\cdot$ 62	46,754 = 1*a* - 62*b*
4	1	18,783 = 65,537 - 46,754 $\cdot$ 1	18,783 = (0*a* + 1*b*) - (1*a* - 62*b*) $\cdot$ 1	18,783 = -1*a* + 63*b*
5	2	9,188 = 46,754 - 18,783 $\cdot$ 2	9,188 = (1*a* - 62*b*) - (-1*a* + 62*b*) $\cdot$ 2	9,188 = 3*a* - 188*b*
6	2	407 = 18,783 - 9,188 $\cdot$ 2	407 = (-1*a* + 63*b*) - (3*a* - 188*b*) $\cdot$ 2	407 = -7*a* + 439*b*
7	22	234 = 9,188 - 407 $\cdot$ 22	234 = (3*a* - 188*b*) - (-7*a* + 439*b*) $\cdot$ 22	234 = 157*a* - 9,846*b*
8	1	173 = 407 - 234 $\cdot$ 1	173 = (-7*a* + 439*b*) - (157*a* - 9,846*b*) $\cdot$ 1	173 = -164*a* + 10,285*b*
9	1	61 = 234 - 173 $\cdot$ 1	61 = (157*a* - 9,846*b*) - (-164*a* + 10,285*b*) $\cdot$ 1	61 = 321*a* + 20,131*b*
10	2	51 = 173 - 61 $\cdot$ 2	51 = (-164*a* + 10,285*b*) - (321*a* +20,131*b*) $\cdot$ 2	51 = -806a + 50,547b
11	1	10 = 61 - 51 $\cdot$ 1	61 = (321a +20,131b) - (-806a + 50,547b) $\cdot$ 1	10 = 1,127a - 70,678b
12	5	1 = 51 -10 $\cdot$ 5	1 = (-806a + 50,547b) - (1,127a - 70,678b) $\cdot$ 5	1 = -6,441a + 403,937b
13	10	0	演算法結束

將等式還原成原始形式 $ed+w(p-1)(q-1)=1\$ 可以得到 $(65,537)(403,937)+(-6,441)(3,217-1)(1,279-1)=1\$，可以證明 $d=403,937\$ 以及 $w=-6,441\$。在 RSA 加密金鑰生成過程中，w 的值會被丟棄，而 d 則保留為私鑰的值。在這種情況下

d = 0x629e1 = 01100010100111100001

遞迴方法

這是一種用於求解形式為 $au+bv=\gcd(a,b)\$ 的丟番圖方程的直接方法。使用這種方法，被除數和除數在一系列步驟中被簡化。在最後一步，一個平凡值被代入等式，然後反向操作，直到得到解。

例子

使用前面的 RSA 值 $(p-1)(p-1)=4,110,048\$ 和 $e=2^{16}+1=65,537\$

歐幾里得展開	合併項		代入	逆向替換	解出 dx
4,110,048	w0	+ 65,537d0 = 1
(62 $\cdot$ 65,537 + 46,754)	w0	+ 65,537d0 = 1
65,537	(62w0 + d0)	+ 46,754w0 = 1	w1 = 62w0 + d0	4,595 = (62)(-6441) + d0	d0 = 403,937
65,537	w1	+ 46,754d1 = 1	d1 = w0		w1 = -6,441
(1 $\cdot$ 46,754 + 18,783)	w1	+ 46,754d1 = 1
46,754	(w1 + d1)	+ 18,783w1 = 1	w2 = w1 + d1	-1,846 = 4,595 + d1	d1 = -6,441
46,754	w2	+ 18,783d2 = 1	d2 = w1
(2 $\cdot$ 18,783 + 9,188)	w2	+ 18,783d2 = 1
18,783	(2w2 + d2)	+ 9,188w2 = 1	w3 = 2w2 + d2	903 = (2)(-1,846) + d2	d2 = 4,595
18,783	w3	+ 9,188d3 = 1	d3 = w2
(2 $\cdot$ 9,188 + 407)	w3	+ 9,188d3 = 1
9,188	(2w3 + d3)	+ 407w3 = 1	w4 = 2w3 + d3	-40 = (2)(903) + d3	d3 = -1846
9,188	w4	+ 407d4 = 1	d4 = w3
(22 $\cdot$ 407 + 234)	w4	+ 407d4 = 1
407	(22w4 + d4)	+ 234w4 = 1	w5 = 22w4 +d4	23 = (22)(-40) + d4	d4 = 903
407	w5	+ 234d5 = 1	d5 = w4
(1 $\cdot$ 234 + 173)	w5	+ 234d5 = 1
234	(w5 + d5)	+ 173w5 = 1	w6 = w5 +d5	-17 = 23 + d5	d5 = -40
234	w6	+ 173d6 = 1	d6 = w5
(1 $\cdot$ 173 + 61)	w6	+ 173d6 = 1
173	(w6 + d6)	+ 61w6 = 1	w7 = w6 +d6	6 = -17 + d6	d6 = 23
173	w7	+ 61d7 = 1	d7 = w6
(2 $\cdot$ 61 + 51)	w7	+ 61d7 = 1
61	(2w7 + d7)	+ 51w7 = 1	w8 = 2w7 +d7	-5 = (2)(6) + d7	d7 = -17
61	w8	+ 51d8 = 1	d8 = w7
(1 $\cdot$ 51 + 10)	w8	+ 51d8 = 1
51	(w8 + d8)	+ 10w8 = 1	w9 = w8 +d8	1 = -5 + d8	d8 = 6
51	w9	+ 10d9 = 1	d9 = w8
(5 $\cdot$ 10 + 1)	w9	+ 10d9 = 1
10	(5w9 + d9)	+ 1w9 = 1	w10 = 5w9 +d9	0 = (5)(1) + d9	d9 = -5
10	w10	+ 1d10 = 1	d10 = w9
(1 $\cdot$ 10 + 0)	w10	+ 1d10 = 1
1	(10w10 + d10)	+ 0w10 = 1	w11 = 10w10 +d10	1 = (10)(0) + d10	d10 = 1
1	w11	+ 0d11 = 1	d11 = w10	w11 = 1, d11 = 0

尤拉的totient函式

在密碼學中至關重要，totient函式（有時被稱為phi函式）被定義為小於$n\$且與$n\$互質的非負整數$a\$的數量。從數學上講，這表示為

$\phi (n)=\left|{\bigg \{}0\leq a\leq n|\gcd(a,n)=1{\bigg \}}\right|$

這立即表明對於任何素數$p\$

$\phi (p)=p-1\$

任何指數化素數的totient函式的計算方式如下

$\phi (p^{\alpha })\$

$=p^{\alpha }-p^{\alpha -1}\$

$=p^{\alpha }\left(1-{\tfrac {1}{p}}\right)\$

尤拉函式也是乘法的

$\phi (ab)=\phi (a)\phi (b)\$

其中 $\gcd(a,b)=1\$

有限域和生成器

一個域只是一組 $\mathbb {F}$，它包含受熟悉的加法和乘法運算約束的數值元素。存在幾種不同型別的域；例如，$\mathbb {R}$，實數域，以及$\mathbb {Q}$，有理數域，或者 $\mathbb {C}$，複數域。通用域通常用 $\mathbb {F}$ 表示。

有限域

密碼學主要利用有限域，這些域幾乎完全由整陣列成。最顯著的例外是形式為$a+bi\$的高斯數，它們是實部和虛部為整數的複數。有限域的定義如下

$\left(\mathbb {Z} /n\mathbb {Z} \right)=\mathbb {Z} _{n}\$ 模 $n\$ 的整數集

$\left(\mathbb {Z} /p\mathbb {Z} \right)=\mathbb {Z} _{p}\$ 模素數 $p\$ 的整數集

由於密碼學與丟番圖方程的解有關，因此所使用的有限域主要基於整數，並用整數域的符號 $\mathbb {Z}$ 表示。

有限域 $\mathbb {F} _{n}\$ 包含精確的 $n\$ 個元素，其中有 $n-1\$ 個非零元素。 $\mathbb {Z} _{n}\$ 的擴充套件是 $\mathbb {Z} _{n}\$ 的乘法群，記為 $\left(\mathbb {Z} /n\mathbb {Z} \right)^{*}=\mathbb {Z} _{n}^{*}\$，包含以下元素

$a\in \mathbb {Z} _{n}^{*}\$ 使得 $\gcd(a,n)=1\$

換句話說，$\mathbb {Z} _{n}^{*}\$ 包含與 $n\$ 互質的元素

有限域在乘法方面構成一個阿貝爾群，由以下性質定義

$\centerdot$ The product of two nonzero elements is nonzero $\left(ab=c|c\neq 0\right)\$
$\centerdot$ The associative law holds $\left(\left(ab\right)c=a\left(bc\right)\right)\$
$\centerdot$ The commutative law holds $\left(ab=ba\right)\$
$\centerdot$ There is an identity element $\left(I\cdot a=a\right)\$
$\centerdot$ Any nonzero element has an inverse $\left(a\cdot a^{-1}=1\right)\$

在域符號後的下標表示模 $n\$ 的整數集，這些整數從 $0\$ 到 $n-1\$，如下例所示

$\mathbb {Z} _{12}=\{0,1,2,3,4,5,6,7,8,9,10,11\}\$

的乘法階$\mathbb {Z} _{n}$ 用$\mathbb {Z} _{n}^{*}$ 表示，它包含所有元素$a\in \mathbb {Z} _{n}$，使得$\gcd(a,n)=1\$。下面給出了一個例子$\mathbb {Z} _{12}$

$\mathbb {Z} _{12}^{*}=\{1,5,7,11\}\$

如果$p\$ 是素數，則集合$\mathbb {Z} _{p}^{*}$ 包含所有整數$a\$，使得$1\leq a\leq p\$。例如

合數n	素數p
$\mathbb {Z} _{9}=\{0,1,2,3,4,5,6,7,8\}$	$\mathbb {Z} _{11}=\{0,1,2,3,4,5,6,7,8,9,10\}$
$\mathbb {Z} _{9}^{*}=\{1,2,4,5,7,8\}$	$\mathbb {Z} _{11}^{*}=\{1,2,3,4,5,6,7,8,9,10\}$

生成器

每個有限域都有一個生成元。生成元$g\$ 可以透過對生成元$g\,{\bmod {\,}}n\$ 進行求冪來生成集合$\mathbb {Z} _{n}$ 中的所有元素。假設$g\$ 是$\mathbb {Z} _{n}^{*}$ 的生成元，那麼$\mathbb {Z} _{n}^{*}$ 包含元素$g^{i}\,{\bmod {\,}}n\$，其中$0\leq i\leq \phi (n)-1$。如果$\mathbb {Z} _{n}^{*}$ 有生成元，則$\mathbb {Z} _{n}$ 被稱為迴圈域。

生成元的總數由以下公式給出

$\phi \left(\phi \left(n\right)\right)$

示例

For $n=p=13\$ (Prime)

$\mathbb {Z} _{13}=\{0,1,2,3,4,5,6,7,8,9,10,11,12\}$
$\mathbb {Z} _{13}^{*}=\{1,2,3,4,5,6,7,8,9,10,11,12\}$

Total number of generators $\phi \left(\phi \left(13\right)\right)=\phi \left(12\right)=4$ generators

Let $g=2\$, then $g=\{2,4,8,3,6,12,11,9,5,10,7,1\}\$, $g=2\$ is a generator

Since $2\$ is a generator, check if $\gcd(i,p-1)=1\$
$2^{2}=4\$, and $i=2\$, $\gcd \left(2,12\right)=2\neq 1\$, therefore, $4\$ is not a generator
$2^{3}=8\$, and $i=3\$, $\gcd \left(3,12\right)=3\neq 1\$, therefore, $4\$ is not a generator

Let $g=6\$, then $g=\{6,10,8,9,2,12,7,3,5,4,11,1\}\$, $g=6\$ is a generator
Let $g=7\$, then $g=\{7,10,5,9,11,12,6,3,8,4,2,1\}\$, $g=7\$ is a generator
Let $g=11\$, then $g=\{11,4,5,3,7,12,2,9,8,10,6,1\}\$, $g=11\$ is a generator

There are a total of $4\$ generators, $\left(2,6,7,11\right)$ as predicted by the formula $\phi \left(\phi \left(n\right)\right).$

For $n=10\$ (Composite)

$\mathbb {Z} _{9}=\{0,1,2,3,4,5,6,7,8,9\}\$
$\mathbb {Z} _{9}^{*}=\{1,3,7,9\}\$

Total number of generators $\phi \left(\phi \left(10\right)\right)=\phi \left(4\right)=2\$ generators

Let $g=3\$, then $g=\{3,9,7,1,3,9,7,1,3\}\$, $g=3\$ is a generator
Let $g=7\$, then $g=\{7,9,3,1,7,9,3,1,7\}\$, $g=7\$ is a generator

There are a total of $2\$ generators $\left(3,7,\right)\$ as predicted by the formula $\phi \left(\phi \left(n\right)\right).$

同餘

描述

數論包含一個被稱為同餘理論的獨立代數系統。同餘的數學概念是由卡爾·弗里德里希·高斯在算術研究（1801 年）中引入的。

定義

如果$a\$ 和$b\$ 是兩個整數，它們的差能被$m\$ 整除，則可以用以下符號表示

$\left(a-b\right)|m\$

這可以用同餘符號表示為

$a\equiv b\,{\bmod {\,}}m$

其中，除數 $m\$ 稱為同餘模。 $a\equiv b\,{\bmod {\,}}m$ 可以等效地寫成

$a-b=mk\$

其中 $k\$ 是一個整數。

注意在示例中，對於所有 $a\equiv 0\,{\bmod {\,}}m$ 的情況，都表明了 $a|m\$。 考慮到這一點，請注意

$a\equiv 0\,{\bmod {\,}}2$ 表示 $a\$ 是一個偶數。

$a\equiv 1\,{\bmod {\,}}2$ 表示 $a\$ 是一個奇數。

示例

$a\equiv b\,{\bmod {\,}}m$	$a-b=mk\$
$14\equiv 5\,{\bmod {\,}}3$	$14-5=3\cdot 3\$
$-13\equiv 7\,{\bmod {\,}}4$	$(-13)-7=4\cdot (-5)\$
$90\equiv 0\,{\bmod {\,}}18$	$90-0=18\cdot 5\$

同餘的性質

所有同餘 (具有固定 $m\$) 具有以下共同性質

$a\equiv a\,{\bmod {\,}}m$

$a\equiv b\,{\bmod {\,}}m$ 當且僅當 $b\equiv a\,{\bmod {\,}}m$

如果 $a\equiv b\,{\bmod {\,}}m$ 並且 $b\equiv c\,{\bmod {\,}}m$ 那麼 $a\equiv c\,{\bmod {\,}}m$

給定 $a\equiv a\,{\bmod {\,}}m$ 存在唯一一個 $b\$ 使得 $0\leq b\leq m-1\$

這些性質表示一個等價類，意味著任何整數模 $m\$ 等價於有限域 $\mathbb {Z} _{m}$ 中的某個特定整數。

同餘作為餘數

如果整數 $m>2\$ 的模數，那麼對於每個整數 $a\$

$a=mk+r\,\left(r\in \mathbb {Z} _{m}\right)$

可以理解為 $r\$ 是 $a\$ 除以 $m\$ 的餘數，或者作為同餘

$a\equiv r\,{\bmod {\,}}m$

兩個在模 $m\$ 下不同餘的數一定有不同的餘數。因此，可以看出任何同餘式 $a\equiv b\,{\bmod {\,}}m$ 成立當且僅當 $a\$ 和 $b\$ 是被 $m\$ 除後有相同餘數的整數。

例子

$10\equiv 3\,{\bmod {\,}}7$ is equivalent to
$10=\left(7\cdot 1\right)+3\$ implies
$3\$ is the remainder of $10\$ divided by $7\$

同餘式的代數

假設在本節中我們有兩個同餘式，$a\equiv b\,{\bmod {\,}}m$ 和 $c\equiv d\,{\bmod {\,}}m$。這些同餘式可以以下列方式相加或相減

$a+c\equiv b+d\,{\bmod {\,}}m$

$a-c\equiv b-d\,{\bmod {\,}}m$

如果這兩個同餘式相乘，則得到以下同餘式

$ac\equiv bd\,{\bmod {\,}}m$

或者特殊情況，其中 $c=d\$

$ac\equiv bc\,{\bmod {\,}}m$

注意：以上並不意味著同餘式存在除法運算。只有在 $c\$ 和 $m\$ 互質時，才能簡化以上內容。在數學上，這表示為

$ac\equiv bc\,{\bmod {\,}}m$ 意味著 $a\equiv b\,{\bmod {\,}}m$ 當且僅當 $\gcd \left(c,m\right)=1$

以上定義的等價類集合構成一個交換環，這意味著餘類可以相加、相減和相乘，並且運算滿足結合律、交換律，並具有加法逆元。

模m 運算的簡化

在處理同餘式 $a\equiv b\,{\bmod {\,}}m$ 時，我們通常需要進行運算，其中 $b>m\$，而我們想要得到一個新的整數 $d\$，使得 $0\leq d\leq m-1\$，並且得到的 $d\$ 是該同餘式的模 $m\$ 的最小非負剩餘。對同餘式進行模 $m\$ 運算基於同餘式的性質，並且在同餘式的冪運算中經常需要使用。

演算法

Input: Integers $b\$ and $m\$ from $a\equiv b\,{\bmod {\,}}m$ with $b>m\$
Output: Integer $d\$ such that $0\leq d\leq m-1\$

1. Let $q=\left\lfloor {\tfrac {b}{m}}\right\rfloor$
2.     $c=qm\$
3.     $d=b-c\$
4. Output $d\$

例子

Given $289\equiv 49\,{\bmod {\,}}5$

$9=\left\lfloor {\tfrac {49}{5}}\right\rfloor$
$45=9\cdot 5\$
$4=49-45\$

∴ $289\equiv 49\equiv 4\,{\bmod {\,}}5$

請注意 $4\$ 是模 $5\$ 的最小非負剩餘。

冪運算

假設我們從 $a\equiv b\,{\bmod {\,}}m$ 開始。當我們將這個同餘式乘以自身時，結果是 $a^{2}\equiv b^{2}\,{\bmod {\,}}m$。概括這個結果，假設 $n\$ 是一個正整數

$a^{n}\equiv b^{n}\,{\bmod {\,}}m$

例子

$9\equiv 4\,{\bmod {\,}}13$
$81\equiv 16\,{\bmod {\,}}13$
$729\equiv 64\,{\bmod {\,}}13$

This simplifies to

$81\equiv 16\,{\bmod {\,}}13$ implies $16\equiv 3\,{\bmod {\,}}13$
$729\equiv 64\,{\bmod {\,}}13$ implies $256\equiv 9\,{\bmod {\,}}13$

重複平方法

有時我們需要知道模 $m\$ 的最小非負剩餘，其中一個數被冪運算為 $a^{2}\equiv \,{\bmod {\,}}m$。為了找到這個數，我們可以使用重複平方法，其工作原理如下

1. Begin with $a\equiv \,{\bmod {\,}}m$
2. Square $a\$ and $b\$ so that $a^{2}\equiv b^{2}\,{\bmod {\,}}m$
3. Reduce $b\$ modulo $m\$ to obtain $a^{\equiv }b_{1}\,{\bmod {\,}}m$
4. Continue with steps 2 and 3 until $a^{2^{n}}\equiv b_{n}\,{\bmod {\,}}m$ is obtained.
   Note that $n\$ is the integer where $2^{n+1}\$ would be just larger than the exponent desired
5. Add the successive exponents until you arrive at the desired exponent
6. Multiply all $b_{i}\$'s associated with the $a\$'s of the selected powers
7. Reduce the resulting $b\,{\bmod {\,}}m$ for the desired result

例子

To find $6^{149}{\bmod {\,}}11$:

$6\equiv 6\,{\bmod {\,}}11$
$6^{2}=36\equiv 3\,{\bmod {\,}}11$
$6^{4}\equiv 9\,{\bmod {\,}}11$
$6^{8}\equiv 81\equiv 4\,{\bmod {\,}}11$
$6^{16}\equiv 16\equiv 5\,{\bmod {\,}}11$
$6^{32}\equiv 25\equiv 3\,{\bmod {\,}}11$
$6^{64}\equiv 9\,{\bmod {\,}}11$
$6^{128}\equiv 81\equiv 4\,{\bmod {\,}}11$

Adding exponents:

$128+16+4+1\$

Multiplying least nonnegative residues associated with these exponents:

$4\cdot 5\cdot 9\cdot 6=1080\$
$1080\,{\bmod {\,}}11=2$

Therefore: 

$6^{149}\equiv 2\,{\bmod {\,}}11$

同餘的逆

描述

雖然找到正確的對稱或非對稱金鑰是加密明文訊息所必需的，但是計算這些金鑰的逆對於成功解密生成的密文至關重要。這可以在從簡單的仿射變換

$C\equiv aP+b\,{\bmod {\,}}N$

到 RSA 公鑰加密，其中一個解密（私有）金鑰是

$P\equiv a^{-1}C+b^{-1}\,{\bmod {\,}}N$

的各種密碼系統中都可以看到。

$d_{A}=e_{A}^{-1}\,{\bmod {\,}}\phi \left(n_{A}\right)$

定義

對於元素 $a\in \mathbb {Z} _{m}$ 其中 $\gcd \left(a,m\right)=1$，存在 $b\in \mathbb {Z} _{m}$ 使得 $ab\equiv 1\,{\bmod {\,}}m$。因此，$b\$ 被稱為 $a\$ 的 *逆*，記為 $a^{-n}\,{\bmod {\,}}m$ 其中 $n\$ 是整數 $b\$ 的 *n 次方*，其中 $ab\equiv 1\,{\bmod {\,}}m$。

例子

Find $633^{-1}\,{\bmod {\,}}2801$

This is equivalent to saying $633b\equiv 1\,{\bmod {\,}}2801$

First use the Euclidean algorithm to verify $\gcd \left(633,2801\right)=1\$.
Next use the Extended Euclidean algorithm to discover the value of $b\$.
In this case, the value is $177\$.

Therefore, $633^{-1}\,{\bmod {\,}}2801=177$

It is easily verified that $\left(633\right)\left(177\right)\equiv 1\,{\bmod {\,}}2801$

費馬小定理

定義

其中 $p\$ 定義為素數，任何整數都滿足以下關係

$a^{p}\equiv a\,{\bmod {\,}}p$

例子

當 $a=2\$ 且 $p=19\$

$2^{2}\equiv 23\,{\bmod {\,}}19$

$2^{4}\equiv 529\equiv 16\,{\bmod {\,}}19$

$2^{8}\equiv 256\equiv 9\,{\bmod {\,}}19$

$2^{16}\equiv 81\equiv 5\,{\bmod {\,}}19$

$16+2+1=19\$ 意味著 $5\cdot 23\cdot 2=230\equiv 2\,{\bmod {\,}}19$

條件和推論

一個額外的條件指出，如果 $a\$ 不能被 $p\$ 整除，則以下等式成立

$a^{p-1}\equiv 1\,{\bmod {\,}}p$

費馬小定理還有一個推論，它指出如果 $a\$ 不能被 $p\$ 整除，且 $n\equiv m\,{\bmod {\,}}\left(p-1\right)$ 那麼

$a^{n}\equiv a^{m}\,{\bmod {\,}}p$

尤拉推廣

如果 $\gcd \left(a,m\right)=1\$，那麼 $a^{\phi \left(m\right)}\equiv 1\,{\bmod {\,}}m$

中國剩餘定理

如果想要解決一個具有不同模數的同餘方程組，可以按照以下步驟進行

$x\equiv a_{1}\,{\bmod {\,}}m_{1}$

$x\equiv a_{2}\,{\bmod {\,}}m_{2}$

$\cdots$

$x\equiv a_{k}\,{\bmod {\,}}m_{k}$

一個同時的解 $x\$ 存在當且僅當 $\gcd \left(m_{i},m_{j}\right)=1$，其中 $\left(i\neq j\right)\$，並且任何兩個解都彼此模 $M=m_{1}m_{2}\ldots m_{k}\$ 同餘。

使用中國剩餘定理尋找同時解的步驟如下

1. 計算 $M\$

2. 計算 $M_{i}=M/m_{i}\$ 對於每一個不同的 $i\$

3. 找到 $M_{i}\,{\bmod {\,}}m_{i}$ 的逆元 $N\$ 對於每一個 $i\$ 使用擴充套件歐幾里得演算法

4. 將 $a_{i}M_{i}N_{i}\$ 乘開，對每個 $i\$ 都進行一次。

5. 將所有 $a_{i}M_{i}N_{i}\$ 相加。

6. 計算 $\sum _{i=1}^{k}a_{i}M_{i}N_{i}\,{\bmod {\,}}M$ 以獲得最小的非負餘數。

例子

Given:

$x\equiv 1\,{\bmod {\,}}11$
$x\equiv 2\,{\bmod {\,}}7$
$x\equiv 3\,{\bmod {\,}}5$
$x\equiv 4\,{\bmod {\,}}9$

$M=3465\$

$M_{11}=315\$
$M_{7}=495\$
$M_{5}=693\$
$M_{9}=385\$

Using the Extended Euclidean algorithm:

$315N\equiv 1\,{\bmod {\,}}11\,\,\,N=-3$
$315N\equiv 1\,{\bmod {\,}}7\,\,\,N=3$
$315N\equiv 1\,{\bmod {\,}}5\,\,\,N=2$
$315N\equiv 1\,{\bmod {\,}}9\,\,\,N=4$

$\sum _{i=1}^{4}={\begin{cases}1\cdot 315\cdot \left(-3\right)=-945\\2\cdot 495\cdot 3=2970\\3\cdot 639\cdot 2=4158\\4\cdot 385\cdot 4=6160\end{cases}}$

$\sum =12343$

$x=12343\,{\bmod {\,}}3465=1948$

二次剩餘

如果 $p\$ 是素數，並且 $>2\$，檢查 $\mathbb {Z} _{p}=\{1,2,\ldots ,p-1\}$ 中的非零元素，有時需要知道哪些元素是平方數。如果對於某個 $a\in \mathbb {Z} _{p}^{*}$，存在一個平方數，使得 $b^{2}=a\$。那麼，對於 $\mathbb {Z} _{p}^{*}$ 的所有平方數可以透過 $b^{2}\,{\bmod {\,}}p$ 來計算，其中 $b=1,2,\ldots ,\left(p-1\right)/2\$。 $a\in \mathbb {Z} _{n}^{*}$ 是模 $n\$ 的二次剩餘，如果存在一個 $x\in \mathbb {Z} _{n}^{*}$ 使得 $a\equiv x^{2}\,{\bmod {\,}}n$。如果不存在這樣的 $x\$，那麼 $a\$ 是模 $n\$ 的二次非剩餘。 $a\$ 是模素數 $p\$ 的二次剩餘，當且僅當 $a^{\tfrac {p-1}{2}}\,\mod \,p=1$。

例子

For the finite field $\mathbb {Z} _{19}$, to find the squares $\mathbb {Z} _{19}=\{1,2,\ldots ,9\},$, proceed as follows:

${\begin{matrix}1^{2}=1&2^{2}=4&3^{2}=9\\4^{2}=16&5^{2}=6&6^{2}=2\\7^{2}=11&8^{2}=7&9^{2}=5\end{matrix}}$

上面的值是二次剩餘。剩下的（在本例中）9 個值被稱為二次非剩餘。完整的列表如下。

$p=19\$
Quadratic residues: $1,2,4,5,6,7,9,11,16\$
Quadratic nonresidues: $3,8,10,12,13,14,15,17,18\$

勒讓德符號

勒讓德符號表示 $a\$ 是否為模素數 $p\$ 的二次剩餘，並且僅對素數 $p\$ 和整數 $a\$ 定義。 $a\$ 相對於 $p\$ 的勒讓德符號用符號 $L\left({\tfrac {a}{p}}\right)$ 表示。請注意，這並不意味著 $a\$ 除以 $p\$。 $L\left({\tfrac {a}{p}}\right)$ 有三種值之一： $0,1,-1\$。

$L\left({\tfrac {a}{p}}\right){\begin{cases}0,&{\mbox{if }}p{\mbox{ divides }}a{\mbox{ evenly}}\\1,&{\mbox{if }}a{\mbox{ is a quadratic residue modulo }}p\\-1,&{\mbox{if }}a{\mbox{ is a quadratic nonresidue modulo }}p\end{cases}}$

雅可比符號

雅可比符號適用於所有奇數 $n>3\$，其中 $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\ldots p_{m}^{e_{m}}\$，則

$J\left({\tfrac {a}{n}}\right)=L\left({\tfrac {a}{p_{1}}}\right)^{e_{1}}L\left({\tfrac {a}{p_{2}}}\right)^{e_{2}}\ldots L\left({\tfrac {a}{p_{m}}}\right)^{e_{m}}$

如果 $n\$ 是素數，那麼雅可比符號等於勒讓德符號（這是 Solovay-Strassen 素性測試的基礎）。

素性測試

描述

在密碼學中，使用演算法快速有效地測試給定數字是否為素數對於密碼系統的成功至關重要。存在幾種素性測試方法（例如費馬或 Solovay-Strassen 方法），但本節討論的演算法將是 Miller-Rabin（或 Rabin-Miller）素性測試。目前，Miller-Rabin 測試是一種無條件的機率（蒙特卡洛）演算法。將展示如何將 Miller-Rabin 轉換為確定性（拉斯維加斯）演算法。

偽素數

請記住，如果 $p\$ 是素數並且 $gcd\left(b,m\right)=1$，費馬小定理指出

$a^{p-1}\equiv 1\,{\bmod {\,}}p$

但是，在某些情況下，$p\$ 可以滿足上述條件並且是非素數。這些數字類別被稱為偽素數。

$m\$ 是以 $a\$ 為底的偽素數，其中 $gcd\left(a,m\right)=1$ 當且僅當 $a\$ 的最小正冪等於 $1{\bmod {\,}}p$ 平均地除以 $p-1\$.

如果費馬小定理對於任何奇合數整數 $p\$ 都成立，那麼 $p\$ 被稱為偽素數。這構成了素性測試的基礎。透過測試不同的 $a\$'s，我們可以機率性地對所討論數字的素性更有信心。

以下三個條件適用於奇合數整數

I. 如果 $a\$ 的最小正冪與 $1\,{\bmod {\,}}n$ 同餘，並且能整除 $n-1\$（即 $a\$ 在 $\mathbb {Z} _{n}^{*}$ 中的階），那麼 $n\$ 是一個偽素數。

II. 如果 $n\$ 對基底 $a_{1}\$ 和 $a_{2}\$ 是偽素數，那麼 $n\$ 也是對基底 $a_{1}a_{2}\,{\bmod {\,}}n$ 和 $a_{1}a_{2}^{-1}\,{\bmod {\,}}n$ 的偽素數。

III. 如果 $n\$ 不滿足 $a^{p-1}\equiv 1\,{\bmod {\,}}p$，對於任何單個基底 $a\in \mathbb {Z} _{p}^{*}$，那麼 $n\$ 不滿足 $a^{p-1}\equiv 1\,{\bmod {\,}}p$ 至少對於一半的基底 $a\in \mathbb {Z} _{p}^{*}$ 來說。

對於任何滿足 $a^{p-1}\equiv 1\,{\bmod {\,}}p$ 的奇合數，其中 所有 $a\in \mathbb {Z} _{p}^{*}$ 都成立，被稱為 卡邁克爾數。