密码学/数学背景

请参阅讨论页面获取其他建议。

简介

现代公钥（非对称）密码学基于一个称为数论的数学分支，该分支专门处理仅产生整数结果的方程的求解。这类方程被称为丢番图方程，以希腊数学家丢番图（约公元 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}^{*}$ 都成立，被称为 卡迈克尔数。