信息安全数学基础-第一章-整除

这一章讲了初等数论的整除部分，这篇文章是对这章内容的重点归纳和拓展

这章内容解决了以前在算法编程中遇到的几个问题，当时只是苦思冥想，不知其所以然。通过这次对理论的学习忽然理解了算法背后的设计思想，写下这篇博客，记录一下灵感乍现的惊喜。

判断素数问题，定理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博客

Theory > 信息安全数学基础

#Math

信息安全数学基础-第一章-整除

https://43.242.201.154/2024/09/02/secmath0/

Author

Dong

Posted on

September 2, 2024

Licensed under

SQL注入-有过滤注入 Previous

信息安全数学基础-第二章-同余 Next