密码学数学基础 – 同余关系与模运算-171主机测评

在上一章中，我们探讨了整数关系的基本概念，这些工具为我们理解数字之间的关系奠定了基础。而在本章中，我们将进入一个更深层次的领域：同余关系与模运算。这些概念不仅是数论中的重要内容，也是密码学中不可或缺的工具。

同余关系和模运算为我们提供了一种新的视角来看待整数之间的关系。它们让我们能够在一个有限的范围内进行计算，这对于设计和分析加密算法来说至关重要。无论是经典的凯撒密码，还是现代的 RSA 加密算法，同余关系和模运算都在其中扮演着重要的角色。

这个章节初步认识模这个重要概念，一定要跟上哦~~~🚀

模运算与同余关系 🥰

模运算是一种数学运算，它将一个数除以另一个数，并返回余数。我们用符号

mod

$m o d$ 来表示模运算。设

a=bq+r

$a = b q + r$ ，其中

$r$ 是余数，那么我们说

≡

a \\equiv r \\mod b

$a \equiv r mod b$ 。例如，

7 \\mod 3

$7 mod 3$ 的结果是

$1$ ，因为

$7$ 除以

$3$ 的商是

$2$ ，余数是

$1$ 。

可以看出，模和整除是密切相关的。模运算可以看作是整除的一种扩展，它不仅告诉我们一个数是否能被另一个数整除，还告诉我们在不能整除的情况下，余数是什么。因此，模运算将整数映射到一个有限的范围内，这个范围由模数决定。模为数

$n$ 定义了一个整数集合

{

…

−

}

\\{0, 1, 2, \\ldots, n-1\\}

${0, 1, 2, \dots, n - 1}$ ，在这个集合中进行的运算称为模运算。

特殊的，负数的模运算结果也可以通过添加模数来得到。例如，

−

-1 \\mod 3

$- 1 mod 3$ 的结果是

$2$ ，因为

−

-1 + 3 = 2

$- 1 + 3 = 2$ 。

同余关系是指两个整数在模运算下具有相同的余数。我们用符号

≡

\\equiv

$\equiv$ 来表示同余关系。例如，

≡

7 \\equiv 1 \\mod 3

$7 \equiv 1 mod 3$ ，因为

$7$ 和

$1$ 在模

$3$ 下具有相同的余数。

同余关系具有一些重要的性质：

反身性：对于任何整数

\\equiv a \\mod n a≡amodn

对称性：如果

\\equiv b \\mod n a≡bmodn，则 b ≡ a m o d n b \\equiv a \\mod n b≡amodn。

传递性：如果

\\equiv b \\mod n a≡bmodn 且 b ≡ c m o d n b \\equiv c \\mod n b≡cmodn，则 a ≡ c m o d n a \\equiv c \\mod n a≡cmodn

加法：如果

\\equiv b \\mod n a≡bmodn 和 c ≡ d m o d n c \\equiv d \\mod n c≡dmodn，则 a ± c ≡ b ± d m o d n a \\pm c \\equiv b \\pm d \\mod n a±c≡b±dmodn

乘法：如果

\\equiv b \\mod n a≡bmodn 和 c ≡ d m o d n c \\equiv d \\mod n c≡dmodn，则 a c ≡ b d m o d n ac \\equiv bd \\mod n ac≡bdmodn

指数：如果

\\equiv b \\mod n a≡bmodn，则对于任何非负整数 k k k，都有 a k ≡ b k m o d n a^k \\equiv b^k \\mod n ak≡bkmodn

逆元（模反元素） 😗

在模运算中，逆元（也称为模反元素）是指对于一个整数

$a$ 和一个模数

$n$ ，如果存在一个整数

$x$ 使得

≡

ax \\equiv 1 \\mod n

$a x \equiv 1 mod n$ ，那么我们称

$x$ 是

$a$ 的逆元，记作

−

a^{-1} \\mod n

$a^{- 1} mod n$ 。换句话说，逆元是一个数，使得它与原数的乘积在模运算下等于 1，在范围

$0$ 到

−

n-1

$n - 1$ 之间是唯一的。

我们可以使用扩展欧几里得算法计算逆元

$x$ 。

≡

ax \\equiv 1 \\mod n

$a x \equiv 1 mod n$ 可以写作

ax = 1 + kn

$a x = 1 + kn$ ，其中k是某个整数。根据裴蜀定理，存在整数

$x$ 和

$y$ 使得

ax + ny = 1

$a x + n y = 1$ 。因此，

$x$ 就是

$a$ 的逆元。

需要注意的是，并不是所有的整数都存在逆元。只有当

$a$ 和

$n$ 互质时，

$a$ 才有逆元。这是因为如果

$a$ 和

$n$ 有公共因数，那么

$a x$ 将无法等于

$1$ 。

消去律与一次同余方程 🙃

消去律①是指在模运算中，如果

≡

ac \\equiv bc \\mod n

$a c \equiv b c mod n$ 且

gcd

⁡

(

)

\\gcd(c,n) = g

$g cd (c, n) = g$ ，那么可以消去

$c$ ，得到

≡

a \\equiv b \\mod \\frac{n}{g}

$a \equiv b mod \frac{n}{g}$ 。这个性质在解一次同余方程时非常有用。

一次同余方程的形式是

≡

ax \\equiv b \\mod n

$a x \equiv b mod n$ 。如果

gcd

⁡

(

)

\\gcd(a,b) = 1

$g cd (a, b) = 1$ ，那么该方程有唯一解。解法是先求出

$a$ 的逆元

−

a^{-1}

$a^{- 1}$ ，然后将方程两边同时乘以

−

a^{-1}

$a^{- 1}$ ，得到

≡

−

x \\equiv a^{-1}b \\mod n

$x \equiv a^{- 1} b mod n$ 。

如果

gcd

⁡

(

)

\\gcd(a,b) = c > 1

$g cd (a, b) = c > 1$ ,

gcd

⁡

(

)

\\gcd(c,n) = g > 1

$g cd (c, n) = g > 1$ , 我们使用消去律将方程简化为

′

≡

′

a'x \\equiv b' \\mod n'

$a^{'} x \equiv b^{'} mod n^{'}$ ，其中

′

a' = \\frac{a}{c}

$a^{'} = \frac{a}{c}$ ,

′

b' = \\frac{b}{c}

$b^{'} = \frac{b}{c}$ ,

′

n' = \\frac{n}{g}

$n^{'} = \frac{n}{g}$ 。然后求出

′

$a^{'}$ 的逆元

′

−

a'^{-1}

$a^{' - 1}$ ，最后得到

≡

′

−

′

x \\equiv a'^{-1}b' \\mod n'

$x \equiv a^{' - 1} b^{'} mod n^{'}$ 。

总而言之，先用消去律将方程简化为

′

≡

′

a'x \\equiv b' \\mod n'

$a^{'} x \equiv b^{'} mod n^{'}$ ，然后求出

′

$a^{'}$ 的逆元

′

−

a'^{-1}

$a^{' - 1}$ ，最后得到

≡

′

−

′

x \\equiv a'^{-1}b' \\mod n'

$x \equiv a^{' - 1} b^{'} mod n^{'}$ 。

一次同余方程组与中国剩余定理 🥳

如果我们有多个同余方程需要同时满足，那么我们就需要使用中国剩余定理（Chinese Remainder Theorem）②来求解。一次同余方程组的形式是：

{

≡

⋮

≡

\\begin{cases} x \\equiv a_1 \\mod n_1 \\\\ x \\equiv a_2 \\mod n_2 \\\\ \\vdots \\\\ x \\equiv a_m \\mod n_m \\end{cases}

$⎩$

⎨

⎧x≡a1modn1x≡a2modn2⋮x≡ammodnm

中国剩余定理告诉我们，如果

…

n_1, n_2, \\ldots, n_m

$n_{1}, n_{2}, \dots, n_{m}$ 互质，那么这个同余方程组有唯一解，并且可以通过以下步骤来求解：

计算

\\prod_{i=1}^{m} n_i N=∏i=1m​ni​。

对于每个

M_i = \\frac{N}{n_i} Mi​=ni​N​。

对于每个

M^{-1}_i Mi−1​，使得 M i M i − 1 ≡ 1 m o d n i M_i M^{-1}_i \\equiv 1 \\mod n_i Mi​Mi−1​≡1modni​。

最后，解

\\sum_{i=1}^{m} a_i M_i M^{-1}_i \\mod N x=∑i=1m​ai​Mi​Mi−1​modN

实际上，求解一次同余方程也可以用CRT（中国剩余定理）来解决，以达到当模数较大时简化计算的目的。只需要将模数n分解成互质的因数，然后将原方程转化为多个同余方程，最后使用CRT来求解即可。

威尔逊定理 😎

威尔逊定理③是数论中的一个重要定理，它给出了一个关于素数的判定方法。威尔逊定理的内容是：

是一个素数

⟺

(

−

)

≡

−

p 是一个素数 \\Longleftrightarrow (p-1)! \\equiv -1 \\mod p

$p 是一个素数 ⟺ (p - 1)! \equiv - 1 mod p$

这个定理在密码学中算是比较少见的，一般是用来简便运算，就不过多介绍了。

结论①②③证明 😨

本章节的定理和算法虽然比较基础，但我们来简单证明一下吧。（一定不是因为CRT比较重要和常用🤪）

结论①证明 🤐

设

gcd

⁡

(

)

g = \\gcd(c, n)

$g = g cd (c, n)$ ，则

′

c = g c'

$c = g c^{'}$ 和

′

n = g n'

$n = g n^{'}$ ，其中

gcd

⁡

(

′

)

\\gcd(c', n') = 1

$g cd (c^{'}, n^{'}) = 1$ 。

因为

≡

ac \\equiv bc \\mod n

$a c \equiv b c mod n$ ，所以

(

′

−

′

)

≡

′

g(ac' – bc') \\equiv 0 \\mod gn'

$g (a c^{'} - b c^{'}) \equiv 0 mod g n^{'}$ ，即

′

−

′

≡

′

ac' – bc' \\equiv 0 \\mod n'

$a c^{'} - b c^{'} \equiv 0 mod n^{'}$ 。

由于

gcd

⁡

(

′

)

\\gcd(c', n') = 1

$g cd (c^{'}, n^{'}) = 1$ ，所以可以消去

′

$c^{'}$ ，得到

≡

′

a \\equiv b \\mod n'

$a \equiv b mod n^{'}$ 。

结论②证明 💀

设

∏

N = \\prod_{i=1}^{m} n_i

$N = \prod_{i = 1}^{m} n_{i}$ 。

构造

∗

…

∗

n^*_1 = \\frac{N}{n_1}, \\ n^*_2 = \\frac{N}{n_2}, \\ \\ldots, \\ n^*_m = \\frac{N}{n_m}

$n_{1}^{*} = \frac{N}{n _{1}}, n_{2}^{*} = \frac{N}{n _{2}}, \dots, n_{m}^{*} = \frac{N}{n _{m}}$

模数

n_i

$n_{i}$ 与

∗

n^*_i

$n_{i}^{*}$ 互质，因此存在逆元

t_i

$t_{i}$ 使得

∗

≡

∗

≡

…

∗

≡

t_1 n^*_1 \\equiv 1 \\mod n_1, \\ t_2 n^*_2 \\equiv 1 \\mod n_2, \\ \\ldots, \\ t_m n^*_m \\equiv 1 \\mod n_m

$t_{1} n_{1}^{*} \equiv 1 mod n_{1}, t_{2} n_{2}^{*} \equiv 1 mod n_{2}, \dots, t_{m} n_{m}^{*} \equiv 1 mod n_{m}$

我们发现

∗

≡

{

(

)

(

)

≠

e_i = t_i n_i^* \\equiv \\begin{cases} 1 \\pmod{n_i} \\\\ 0 \\pmod{n_j}, & j \\neq i \\end{cases}

$e_{i} = t_{i} n_{i}^{*} \equiv {1 (mod n_{i}) 0 (mod n_{j}), j \neq = i$

用

e_i

$e_{i}$ 乘以

a_i

$a_{i}$ ，然后将它们相加，我们得到方程的一个解

∑

≡

∑

∗

x = \\sum_{i=1}^{m} a_i e_i \\equiv \\sum_{i=1}^{m} a_i t_i n^*_i \\mod N

$x = i = 1 \sum m a_{i} e_{i} \equiv i = 1 \sum m a_{i} t_{i} n_{i}^{*} mod N$

因为

$x$ 里所包含的那些下标不等于

$i$ 的单项式因为

$e$ 的性质而在模

n_i

$n_{i}$ 下为

$0$ ，只留下下标等于

$i$ 的单项式

∗

a_i t_i n^*_i

$a_{i} t_{i} n_{i}^{*}$ ，而

∗

≡

t_i n^*_i \\equiv 1 \\mod n_i

$t_{i} n_{i}^{*} \equiv 1 mod n_{i}$ ，所以

≡

x \\equiv a_i \\mod n_i

$x \equiv a_{i} mod n_{i}$ 。

结论③证明 😵

要证明

$p$ 是素数当且仅当

(

−

)

≡

−

(p-1)! \\equiv -1 \\mod p

$(p - 1)! \equiv - 1 mod p$ ，显然

−

≡

−

p – 1 \\equiv -1 \\mod p

$p - 1 \equiv - 1 mod p$ ，所以即证明

(

−

)

≡

(p-2)! \\equiv 1 \\mod p

$(p - 2)! \equiv 1 mod p$ 。

也就是说，除去

$1$ 后，如果

…

−

2, 3, \\ldots, p-2

$2, 3, \dots, p - 2$ 能够两配对,且每对数乘积模

$p$ 后为

$1$ 的话，威尔逊定理就成立了，然后我们考虑这其实就是去找模

$p$ 意义下的逆元。

考虑一下二次剩余里面的衍生知识，我们可以知道对于

≡

x^2 \\equiv 1 \\mod p

$x^{2} \equiv 1 mod p$ 只有两个解

(

−

)

(1, p-1)

$(1, p - 1)$ ，而这两个数已经被我们安排掉了，也就是说

…

−

2, 3, \\ldots, p-2

$2, 3, \dots, p - 2$ 中不存在某个数的逆元是自己本身。

那么对于集合

…

−

A = {1, 2, \\ldots, p-1}

$A = 1, 2, \dots, p - 1$ 中的元素，我们可以将

…

−

2, 3, \\ldots, p-2

$2, 3, \dots, p - 2$ 中的元素两两配对，使得每对数的乘积模

$p$ 后为

$1$ ，所以

(

−

)

≡

(p-2)! \\equiv 1 \\mod p

$(p - 2)! \equiv 1 mod p$ 。

当然，用群论的知识可以更加快速证明，集合

…

−

A = {1, 2, \\ldots, p-1}

$A = 1, 2, \dots, p - 1$ 是一个乘法群，每个元素都有唯一逆元。我们又将自逆元排除，所以所有元素都可以两两配对为互逆的数对，每对乘积模

$p$ 为

$1$ 。

我的个人blog：Alice and Bobの神秘小屋

密码学数学基础 - 同余关系与模运算

模运算与同余关系 🥰

逆元（模反元素） 😗

消去律与一次同余方程 🙃

一次同余方程组与中国剩余定理 🥳

威尔逊定理 😎

结论①②③证明 😨

结论①证明 🤐

结论②证明 💀

结论③证明 😵

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

模运算与同余关系 🥰

逆元（模反元素） 😗

消去律与一次同余方程 🙃

一次同余方程组与中国剩余定理 🥳

威尔逊定理 😎

结论①②③证明 😨

结论①证明 🤐

结论②证明 💀

结论③证明 😵

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发