信息安全数学基础

第一章整除

在整数集合中，整除是一种重要的二元关系。这些概念与性质又是整数集合中另一种重要的二元关系——同余关系的基础。

Overview
因此，(a,b)也可以视为利用长度为a和b的两把“尺子”可以“丈量”的最小长度。

Abstract：

判断素数问题，定理1.4对应到了O(√n)算法优化方法的证明
素数筛的两种方法：埃氏筛和欧拉筛，刚好对应了两种素数不可穷举的证明思想
辗转相除法及其证明
贝祖定理，扩展欧几里得算法的应用——求逆元
素数的性质，最大公因数和最小公倍数
算术基本定理

重要定理及证明(素数部分)

定理1.3：

设a,b,c!=0是三个正整数。若c|a，c|b，则对任意整数s,t有

c | sa+tb

这条定理通过整除定义证明即可。但是这条定理也值得记下，它提供了后边欧几里得除法的证明方式，而扩展欧几里得除法提供了求逆元的方法，这又是后续RSA加密算法的关键环节，所以说这条定理差不多算是大楼的第一块砖了，基础却重要。

定理1.4

设n是一个正合数，p是n的一个大于1的最小正因数，则p一定是素数，且p小于等于√n。
这条定理应该是整除部分最重要的之一了。

空口无凭，举个实际应用的例子-判断一个数是否是素数：
“非正式地说，这条定理说明了两点：素数可以视为合数的“组成部分”，且这一“组成成分”中必然有一部分小于√n”

def is_prime(n):  
    if n <= 1:  
        return False  
    if n <= 3:  
        return True  
    if n % 2 == 0 or n % 3 == 0:  
        return False  
    i = 5  
    while i * i <= n:  
        if n % i == 0 or n % (i + 2) == 0:  
            return False  
        i += 6  
    return True

为什么只枚举到√n?，这里就用到了定理1.4，大大提高了算法时间复杂度。
值得说明的是，对于判断素数问题，O(√n)即是速度瓶颈，也就是说这基本上是最快的方法了。

定理1.5

素数有无穷多个
课上讲了两种证明方法，思考发现，两种证明思想刚刚好对应了两种编程算法，这里先介绍证明方法：

证明A：

证明B:

算法设计

对于寻找范围内所有素数的问题，网上资料会说：欧拉筛是埃氏筛法的优化、欧拉筛和埃氏筛的本质都一样：“素数的倍数不是素数。”、欧拉筛避免了埃氏筛中重复筛选的问题、等等.

这些说法都不错，但是当我们学过算法的数学理论，不难发现这两种算法其实是两种不同证明思想的体现，而不是简单的算法优化与继承。

埃氏筛法对应证法A，欧拉筛对应证法B

Eraosthenes（埃拉托斯尼筛法）埃氏筛法

时间复杂度O（nloglogn）

const int maxn=2e6+6;
bool isprime[maxn];
void seive(){
    memset(isprime,true,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=2;i<=maxn;i++){
        if (isprime[i]&&i<sqrt(maxn)) {
            for (int j = i * i; j <= maxn; j += i) {//枚举倍数并筛去
                isprime[j] = false;
            }
        }
    }
}
//Attention：
//1.Q:如何理解它与证明A的联系？
//  A:反证存在无限个素数的过程实际上提供了一种寻找素数的方法，进而完成素数的筛选。
//2.Q:如何理解并证明埃氏筛重复筛选的问题？
//  A:例如：对于6就有重复的筛选-2*3和3*2
//3.Q:为什么j要从i平方开始枚举，如何证明这样做的正确性?
//4.Q:i可以枚举到√maxn就停止吗？

埃氏筛法的相关证明

证明从i平方开始枚举可行

证明埃氏筛正确，并证明它无法避免重复筛选

假设存在一个数n，它是i的倍数但大于i^2，且n还没有被任何小于i的质数筛去。那么n可以表示为n = i * k，其中k > i。

如果k是质数:
那么k一定大于i（因为k是n的因子且n > i^2），那么k*i > i^2，那么当前i一定可以筛掉这个n，合理。
如果k是合数:
那么根据定理1.23（算术基本定理），任意整数可以唯一的表示成:
$n=p1^{a_1} p2^ {a_2}p3^ {a_3}\cdots p_k^{a_k},p_i < p_j,$ 且都是素数
那么之前遍历过的素数一定筛掉了当前的n，合理。
综上所述，埃氏筛可以实现不漏的筛选。
无法避免重复?， $n=p1^{a_1} p2^ {a_2}p3^ {a_3}\cdots p_k^{a_k}$ 里边有几个素数，n就被重复筛了多少次。由此，每个数被重复筛掉过次数也可以知道了。

证明是可以缩小i的枚举范围至√maxn，回答优化后的算法时间复杂度。

证明就是定理1.4，无需再枚举大于√maxn的素数，因为正合数n的最小正因数一定小于√n，且为素数。
这也是手算的重要技巧，被老师在课堂重点强调：

▶

编程测试

**调用计时函数，计算1000以内的素数1000次，记录运行时间**

可以看到，优化后的埃氏筛法快了近一倍！

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3;
bool isprime[maxn+10];
typedef long long int ull;
clock_t start,endd;
double duration;
int Test = 1000;
void seive(){
	memset(isprime,true,sizeof(isprime));
	isprime[0]=isprime[1]=false;
	for(ull i=2;i<=maxn;i++){
//		if(i >= sqrt(maxn))break;
		if (isprime[i]) {
			for (ull j = i * i; j <= maxn; j += i) {//枚举倍数并筛去
				isprime[j] = false;
			}
		}
	}
}
int main()
{
//	start = clock();
//	for(int i = 0;i < Test;++ i)
//	{
		seive();
//	}
//	endd = clock();
	for(int i = 0;i < maxn;++i)
	{
		if(isprime[i])
		{
			cout << i << " ";
		}
	}
	cout << endl;
//	printf("ticks%d=%f\n",maxn,(double)(endd-start));
//	duration = ((double)(endd-start))/CLK_TCK;
//	printf("duration%d=%lf\n",maxn,duration);
	return 0;
}

欧拉筛

时间复杂度:O（n）

const int N = 1e8 + 3;
bool isprime[N];
int prime[N],cnt;
void ola(int n) {
	memset(isprime, true, sizeof(isprime));
	isprime[1] = 0;
 
	for (int i = 2; i <= n; i++) {
		if (isprime[i]) prime[++cnt] = i;//如果i没有被前面的数筛掉，则i是素数
 
		for (int j = 1; j<=cnt&&prime[j] <= n/i; j++) {//j枚举已经筛出的素数
			isprime[i * prime[j]] = 0;//把i*prime[j]筛掉
			if (i % prime[j] == 0) break;//保证不会重复筛
		}
	}
}
//1.Q:为什么要再开一个数组记录素数?
// .A:继承证明B的思想，另外，这也是一种空间换时间的算法思路。
//2.Q:if (i % prime[j] == 0) break;如何保证不重复的？
//  A:模拟一下代码运行过程考虑一会即可知。

补充定理：

课堂思考题及证明：

▶

证明

$\mathbf{证明：（反证法）}\newline\mathbf{若n/p为合数，\exists p_1,p_2\in[2,n/p]}\newline\mathbf{使得：p_1 p_2=n/p}\newline\mathbf{则 p p_1 p_2=n}\newline\mathbf{又 p>n^{1/3}}\newline\mathbf{p_1 p_2< n^{2/3}}\newline\mathbf{由已知：p是n的最小因子}\newline\mathbf{则：p< p_1且p< p_2}\newline\mathbf{\implies p^2 < p_1 p_2 < n ^ {2/3}}\newline\mathbf{\implies p< n ^ {1/3}}\newline\mathbf{矛盾，原命题得证。}\newline$

重要定理及证明(gcd部分)

良序原理

自然数集的每个非空子集都有个最小元素。也称最小数原理。

定理1.8(贝祖定理):

这是GCD 的另一个定义，在高等数学中很有帮助，尤其是环论。

推论:

a 和 b 的任何公约数也会被GCD整除。
三个或更多数字的 GCD 等于所有数字的质因数的乘积
计算两个整数的 GCD 的 Euclid 算法足以计算任意多个整数的 GCD。

定理1.9:

后续乘法逆元部分的重要铺垫
只有两个数互素的时候才有乘法逆元

定理1.12：

欧几里得定理：
理解欧几里得除法的关键点

欧几里得除法：

基本定义与证明

于是由欧几里得定理，(a,b) = (r0,r1) = (r1,r2) = …… = (rn,0) = rn
即gcd(a,b)=gcd(b,a%b)

扩展的欧几里得算法

GCD 可以表示为两个原始数字的线性组合，即两个数字之和，每个数字乘以一个整数（例如，21 = 5 × 105 + （−2） × 252）。
GCD 总是可以用这种方式表达的事实被称为 Bézout 贝祖恒等式。

定理1.13:

扩展欧几里得定理(exgcd算法)

证明

核心：核心思想是反复构造并求解一系列适于裴蜀定理（贝祖定理）的恒等式，进而得到s和t

▶

证明

书P12-13：”以q为纽带，尝试计算s和t的数列。通过尝试和整理，得到定理。”
但是书上并没有说明s和t的数列是怎么找到的，这里将整个证明过程补全。
一切都从贝祖恒等式开始：
$已知:r_n=(a,b)=(b,a,mod,b)\newline那么:(a,b)=(b,a-b \lfloor \frac{a}{b} \rfloor)\newline那么由:s_na+t_nb=(a,b)\newline联系递推式:s_{n-1}b+t_{n-1}(a-b \lfloor \frac{a}{b} \rfloor)=(b,a-b \lfloor \frac{a}{b} \rfloor)\newline得到等式:s_na+t_nb=s_{n-1}b+t_{n-1}(a-b \lfloor \frac{a}{b} \rfloor)\newline\implies a(s_n-t_{n-1})+b(t_{n}-(s_{n-1}-t_{n-1}\lfloor \frac{a}{b} \rfloor))\newline\implies s_n=t_{n-1}\newline\implies t_n=s_{n-1}-t_{n-1}\lfloor \frac{a}{b} \rfloor\newline\begin{cases}t_n=t_{n-2}-q_nt_{n-1}\newlines_n=s_{n-2}-q_ns_{n-1}\newline\end{cases},,,,q_n=\lfloor r_{n-2}/r_{n-1} \rfloor$
那么现在只需证明:
$对j=-2,-1,0,1,…,n-1，\newlines_ja+t_jb=r_j,其中r_j=r_{j-2}-q_jr_{j-1}$
数学归纳法:
$假设上式对于,-2\leq j\leq k-1成立,即\newlines_ja+t_jb=r_j\newline对于j=k，有:\newliner_k=r_{k-2}-q_kr_{k-1}\newline利用归纳假设，得到:\newliner_k=(s_{k-2}a+t_{k-2}b)-q_k(s_{k-1}a+t_{k-1}b)\newliner_k=(s_{k-1}-q_ks_{k-1})a+(t_{k-2}-q_kt_{k-1})b\newliner_k=s_ka+t_kb\newline$

算法设计

▶

递归算法

区别与联系

欧几里得算法，即辗转相除法，将求两个较大数的公因数转化为求两个较小数的公因数。
扩展欧几里得算法，引入了关于s和t的递推关系，在计算r的递推关系求出(a,b)的同时，算出s和t
扩展欧几里得算法求逆元，是扩展欧几里得算法的主要应用
由定理1.9可知，当(m,b)=1时,sm+tb=(m,b)=1，因此，tb=1(mod m)
于是找到了t，这是b在乘法群中的乘法逆元（第六章）

欧几里得算法

int gcd(int a,int b)
{
	if(b == 0)
	{
		return a;
	}
	return gcd(b,a%b);
}

扩展欧几里得算法

int exgcd(int a,int b,int &x,int &y)
{
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	int d = exgcd(b,a%b,x,y);
	int z = x;
	x = y;
	y = z - a / b * y;
	return d;
}

扩展欧几里得算法求逆元

int inv(int a,int p)
{
	int x,y;
	int d = exgcd(a,p,x,y);
	return (x % p + p) % p;//保证返回值在[0,p)之间
}

补充定理:

这部能够深化对素数和gcd的认识，提出了一些实用的性质。
同时又像是贝祖定理的拓展（因为所有证明都离不开贝祖定理）
在这对它们进行整理。

互素的充要条件:

最大公因数的充要条件

▶

证明

最大公因数的性质

互素的gcd性质

推论1:

设a,b,c是三个整数，且c!=0，如果c|ab,(a,c)=1,则c|b

推论2:

设p是素数, 若p|ab, 则p|a或p|b.

推论3:

设a,b,c是整数，若(a,c)=1，(b,c)=1，则(ab,c)=1

推论4:

设a1,a2,……,an是整数,p是素数,p|a1a2……an，则p|某个a。

小结

证明方法略，贝祖定理和反证法即可完成所有。
这部分也是这节课主要理解难度所在，看起来杂乱繁琐，但是形散而神不散。
概括：一个数被拆成乘积形式，素数是其基本组成部分。

发现了吗，这个规律就是下一部分的算术基本定理！！！
理解到位，很自然地就过渡到了下一部分，到此为止这章内容的线索也就很明显了。

思考题及其证明

分类讨论:
若c是素数，由推论2，ab必然有一个被c整除。
若c非素数，举个反例,12=3*4，6|12

1.根据gcd性质,公因数一定小于等于最大公因数
2.由题:n|(a+b)(a-b),那么由推论1反证即可。

1.根据有理数的性质：有理数可以被表示成分数，构造即可。
2.由上述互素的gcd性质可以知道: $(m,n)=1 \iff (m^k,n^k)=1$
那么结合最大公因数的性质（图中框出的那条），即可得证。

重要定理及证明(lcm部分)

定理1.19:

设a,b是两个互素的正整数，则：
(1) $a|m,b|m \implies ab|m$
(2) $[a,b]=ab$

▶

证明

定理1.20:

(1) $a|m,b|m \implies [a,b]|m$
(2) $[a,b]=ab/(a,b)$

▶

证明

算术基本定理:

标准分解式:

标准分解式的应用:

判断整除

求因数个数

求gcd和lcm

综合应用与总结:

找了半天一年前的博客笔记，但是再也找不到了，有一些失落。
但还记得，那是梦开始的地方，如今时隔一年了，问题终于有了答案。
翻到了当时讨论出的AC代码：

▶

已知gcd、lcm，求a和b

#include<stdio.h>
#include<math.h>
int max(int x,int y);
int main(){
	int t,i;
	int m,n,a,b;
	scanf("%d",&t);
	for(i=1;i<=t;i++){
		scanf("%d %d",&n,&m);
		int k=m/n;//求出ab
    for(a=1;a<=sqrt(m/n);a++){
		b=k/a;
		if(max(a,b)==1 && a*b==k)
			printf("%d %d\n",a*n,b*n);
	}
	}	
	return 0;}

int max(int x,int y){
	int i;
	while(x!=y){
		if(x>y)
			x=x-y;
		if(x<y)
			y=y-x;
	}
	i=x;
	return i; }

$ab=a,b=m,n\iff \frac{a}{n} \frac{b}{n} = \frac{m}{n}$
什么意思呢？公式两边除以n平方，那么根据这条定理:

只需要枚举找到这两个互素的数就可以找到a,b了，大大减少了循环次数，是不是很神奇。

The End.

参考资料：

王鑫教授的课件
《信息安全数学基础》(任伟)
维基百科-欧几里得算法
 OI选手现充|junyu33博客

第二章同余

“同余”是大自然的循环现象，是一种等价关系，研究同余的优点在于:化无限为有限。

Overview
图中每一列中的元素以相似的方式不重不漏地出现，这种规律就是剩余类。同余这种等价关系——它将整数划分成了n-1在模n意义下的等价类——n的完全剩余系。
全体整数按照模m是否同余划分成若干两两不相交的集合，使得每一个集合中的任意两个整数模m一定同余，而不属于同一集合的任意两个整数模m不同余。

Abstract：

模运算的基本性质
剩余类：将所有整数按照模m划分成了不同的类
完全剩余系：从每个剩余类中拿一个出来组成完全剩余系
简化剩余类：是m的完全剩余系中与m互素的数构成的子集
简化剩余系：从每个简化剩余类中拿一个出来组成简化剩余系
欧拉定理
Wilson定理
费马定理

考点0：模运算的基本性质

考点1：同余等价关系定义、三大性质（自反、对称、传递）

同余的定义：

同余的充要条件：

同余的基本性质：

由此可以说明同余是一种等价关系（离散数学-二元关系）。

考点2：利用乘法（降幂）计算较大数的mod运算

实质是利用同余的乘性。

考点3：验算大整数乘法结果（模9法，弃9法）

定理基础：

推论应用：

推论应用(模7/11/13)：

例题：

考点4：欧拉函数的定义以及利用标准因数分解式计算欧拉函数

定义：

设m是一个正整数，则m个整数0,1,…，m-1中与m互素的整数的个数，记为 $\phi(m)$ ，叫做欧拉函数。

欧拉函数只有在互素的情况下才有乘性！

考点5：费马小定理、威尔逊定理、欧拉定理

第三章同余式

重点是中国剩余定理及RSA

Abstract:

一次同余式的求解
中国剩余定理
RSA公钥密码系统(非考点)
模重复平方算法

一次同余式的求解

考点1：判断同余式是否有解

考点2：求解一次同余式组

中国剩余定理

考点3：用中国剩余定理求解同余式组

模重复平方算法

考点4：用模重复平方法求解大数的模

第四章二次同余式和平方剩余

二次同余，这种关系将模m剩余类划分成了两个部分，其中，平方剩余是封闭的代数系统——平方剩余的乘积还是平方剩余

Overview

Abstract：

二次剩余/二次非剩余
勒让德符号
二次同余式

重点归纳：

二次剩余

欧拉判别法

勒让德符号

考点梳理：

考点1：寻找、判定二次剩余

考点2：计算勒让德符号

考点3：判断二次同余式有无解

计算勒让德符号是否为1

考点4：求解二次同余式

1.拆模，拆成不可分解的素数
2.配方
3.二次同余计算
eg:

ps：参考了复习课同学的pdf

第五章阶与原根

研究了二次剩余之后，研究n次剩余。研究阶和原根实际上是在研究这个剩余类加群元素的阶和生成元。

Overview

Abstract：

二次剩余/二次非剩余
勒让德符号
二次同余式
原根和二次剩余的关系：
1>原根一定是一个二次非剩余——因此，可以从二次非剩余中寻找最小原根。
2>素数p的原根g的奇数次幂分别与p的平方非剩余同余。
3>素数p的原根g的偶数次幂分别与p的平方剩余同余。

对上述结论的解释：
由上一章可以知道，二次同余这种关系将模m剩余类划分成了两个部分，其中，平方剩余的乘积还是平方剩余。而根据原根的定义，原根的幂次要生成模m剩余类中所有的元素，如果原根是一个二次剩余，那么原根的幂次就全是二次剩余，无法生成二次非剩余。因此，原根一定是一个二次剩余。
原根作为一个生成元，它的循环群中元素模m与模m剩余类中的元素一一对应，又知道，素数p的平方剩余和非平方剩余个数相同，可得上述结论。

重点梳理：

阶和原根的定义

阶的性质：

原根的性质：

用生成元的角度更好理解这种关系，即让11再走几步等于3 =>8步
这种把乘法变成加法的规律实际上是因为原根g形成的循环群与整数模m同余类加法群同构。
这与群论中的性质相契合：任一循环群都能找到一个群与之同构。

原根的应用-密钥交换算法

指数定理：

指数的应用-循环小数

考点归纳：

考点1：阶的判定，求阶

注意先化简，并在phi(m)中寻找阶。

考点2：阶的证明

考点3：判断原根存在性

考点4：判断是否是原根

注：此处也可以联想二次剩余来解题，以判断2/3是否是47的原根为例：

小结论：

考点5：求最小原根

可对2-m-1逐个判断，也可在二次非剩余中逐个判断(更快)
实际上是判断是否是原根的问题，使用原根的充要条件如上。

考点6：求所有原根

由阶的基本性质可以推出：

考点7：原根的证明

考点8：求离散对数

考点9：求解高次同余式

补充：

2的k次无原根
 OI中计算原根
 模板-原根
 费马数的原根

ps：参考了复习课同学的pdf

第六章群

第七章环与域

阶的性质-指数定理

应用广泛的重要定理和性质。

引入（可用于求余的技巧）：

\mathbf{证明：a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \mathbf{若b<\phi(m)：显然成立}\newline \mathbf{若b>=\phi(m)：}\newline \mathbf{b=n\phi(m)+k}\newline \mathbf{k=b(mod(\phi(m)))}\newline \mathbf{a^b\equiv a^{n\phi(m)+k}\equiv a^{n\phi(m)}\times a^{k}\space (mod\space m)}\newline \mathbf{a^{\phi(m)}\equiv1 \space (mod\space m) \space\space[欧拉定理]}\newline \mathbf{a^{n\phi(m)}\equiv1 \space (mod\space m)}\newline \mathbf{\implies a^{b}\equiv a^k\space (mod\space m)}\newline \mathbf{\implies a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \space \newline

这种方法可以简化计算类似 $7^{7^{7}}\equiv ? \space (mod \space m)$ 这样的问题。

阶的基本性质

指数定理

证明

\mathbf{充分性：}\newline \mathbf{假设x\equiv y\space(mod \space \phi(m)),则x=y+k\phi(m),k\in \Zeta\space所以，}\newline \mathbf{g^x\equiv g^{y+k\phi(m)}\space mod(\space m)}\newline \mathbf{\equiv g^y(g^{\phi(m)})^k}\newline \mathbf{k=b(mod(\phi(m)))}\newline \mathbf{g^y\space mod(\space m)}\newline \mathbf{必要性可由上述引例完成证明。}\newline

单素数RSA

数论基础在密码学的应用举例

拿2024BaseCTF 的babyrsa举例：

题目

python
from Crypto.Util.number import *
flag=b'BaseCTF{}'
m=bytes_to_long(flag)

n=getPrime(1024)
e=65537
c=pow(m,e,n)

print("n =",n)
print("e =",e)
print("c =",c)
"""
n = 104183228088542215832586853960545770129432455017084922666863784677429101830081296092160577385504119992684465370064078111180392569428724567004127219404823572026223436862745730173139986492602477713885542326870467400963852118869315846751389455454901156056052615838896369328997848311481063843872424140860836988323
e = 65537
c = 82196463059676486575535008370915456813185183463924294571176174789532397479953946434034716719910791511862636560490018194366403813871056990901867869218620209108897605739690399997114809024111921392073218916312505618204406951839504667533298180440796183056408632017397568390899568498216649685642586091862054119832
"""

单素数RSA是基于RSA算法的一个简化版本，其中使用的密钥只涉及一个素数。
单素数RSA的一个主要特点是它简化了密钥的生成过程，因为只需要找到一个大素数，而不是两个。然而，这也意味着它可能比双素数RSA（传统的RSA算法）更不安全，因为攻击者只需要找到一个素数就可以破解密钥。因此，单素数RSA在实际应用中并不常见，它更多的是作为一个理论概念或者在某些特定的、对安全性要求不高的场景中使用。

在这题中，被加密的信息是字节数据m，为了对其进行加密，将m转换为大整数。
随机生成1024位大质数n作为密钥，选择与n互质的素数e作为公钥进行加密。
题目给出了大质数n，公钥，被加密数据。要求计算出私钥并对其进行解密。

题解：

python
from Crypto.Util.number import *
import gmpy2
n = 104183228088542215832586853960545770129432455017084922666863784677429101830081296092160577385504119992684465370064078111180392569428724567004127219404823572026223436862745730173139986492602477713885542326870467400963852118869315846751389455454901156056052615838896369328997848311481063843872424140860836988323
e = 65537
c = 82196463059676486575535008370915456813185183463924294571176174789532397479953946434034716719910791511862636560490018194366403813871056990901867869218620209108897605739690399997114809024111921392073218916312505618204406951839504667533298180440796183056408632017397568390899568498216649685642586091862054119832

phin = n-1
d = gmpy2.invert(e, phin)
m = pow(c, d, n)
print(long_to_bytes(m))
#b'BaseCTF{7d7c90ae-1127-4170-9e0d-d796efcd305b}'

理解这个题解有两个个关键点：

\mathbf{欧拉函数的性质：若p为素数，则\phi(p)=p-1}\newline \mathbf{e\times d=1\space mod(\space \phi(n))}\newline

\mathbf{已知c=m^e\space(mod\space n)如何反解m？}\newline \mathbf{已知：a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \mathbf{\implies c\equiv m^{e\space (mod \space \phi(n))}\space (mod \space n)} \mathbf{设整数d，m\equiv c^x\space (mod \space n)}\newline \mathbf{\implies m^{e\space (mod \space \phi(n))} \equiv c^{x\times e \space (mod\space \phi(m))} \equiv c}\newline \mathbf{要使上式成立，d必须满足是e在模\phi(n)意义下的逆元，即e\times d=1\space mod(\space \phi(n))}

\mathbf{证明：a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \mathbf{若b<\phi(m)：显然成立}\newline \mathbf{若b>=\phi(m)：}\newline \mathbf{b=n\phi(m)+k}\newline \mathbf{k=b(mod(\phi(m)))}\newline \mathbf{a^b\equiv a^{n\phi(m)+k}\equiv a^{n\phi(m)}\times a^{k}\space (mod\space m)}\newline \mathbf{a^{\phi(m)}\equiv1 \space (mod\space m) \space\space[欧拉定理]}\newline \mathbf{a^{n\phi(m)}\equiv1 \space (mod\space m)}\newline \mathbf{\implies a^{b}\equiv a^k\space (mod\space m)}\newline \mathbf{\implies a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \space \newline

原根与生成元

可以发现很多定理在它的下一章以另一种方式出现

Theory > 数学基础课

#Math

信息安全数学基础

https://47.108.189.123/2025/01/02/课程心得/信息安全数学基础/

Author

Dong

Posted on

January 2, 2025

Licensed under

离散数学 Previous

2023学年年度书单 Next

信息安全数学基础

第一章 整除

Abstract：

重要定理及证明(素数部分)

定理1.3：

定理1.4

定理1.5

证明A：

证明B:

算法设计

Eraosthenes（埃拉托斯尼筛法）埃氏筛法

埃氏筛法的相关证明

证明从i平方开始枚举可行

证明埃氏筛正确，并证明它无法避免重复筛选

证明是可以缩小i的枚举范围至√maxn，回答优化后的算法时间复杂度。

欧拉筛

补充定理：

课堂思考题及证明：

重要定理及证明(gcd部分)

良序原理

定理1.8(贝祖定理):

推论:

定理1.9:

定理1.12：

欧几里得除法：

基本定义与证明

扩展的欧几里得算法

定理1.13:

证明

算法设计

区别与联系

欧几里得算法

扩展欧几里得算法

扩展欧几里得算法求逆元

补充定理:

互素的充要条件:

最大公因数的充要条件

最大公因数的性质

互素的gcd性质

推论1:

推论2:

推论3:

推论4:

小结

思考题及其证明

重要定理及证明(lcm部分)

定理1.19:

定理1.20:

算术基本定理:

标准分解式:

标准分解式的应用:

判断整除

求因数个数

求gcd和lcm

综合应用与总结:

参考资料：

第二章 同余

Abstract：

考点0：模运算的基本性质

考点1：同余等价关系定义、三大性质（自反、对称、传递）

同余的定义：

同余的充要条件：

同余的基本性质：

考点2：利用乘法（降幂）计算较大数的mod运算

考点3：验算大整数乘法结果（模9法，弃9法）

定理基础：

推论应用：

推论应用(模7/11/13)：

例题：

考点4：欧拉函数的定义以及利用标准因数分解式计算欧拉函数

定义：

考点5：费马小定理、威尔逊定理、欧拉定理

第三章 同余式

Abstract:

一次同余式的求解

考点1：判断同余式是否有解

考点2：求解一次同余式组

中国剩余定理

考点3：用中国剩余定理求解同余式组

模重复平方算法

第一章整除

第二章同余

第三章同余式

第四章二次同余式和平方剩余

第五章阶与原根

第六章群

第七章环与域