密码学简单数论笔记（1）：素数和模运算

  
参考资料：
1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c
2.余红兵：《数学奥林匹克小丛书（第二版）高中卷10————数论》

素数

素数的定义：
除了1和它本身以外不再有其他因数的自然数。亦即，除了1和n以外，并无其他正整数整除n的正整数.
1既不是素数，也不是合数。
n为合数，则有n=ab;n>a>1,n>b>1.

我们可以视正整数为3类数。1为单独一类数，其二素数，其三合数.
素数（prime number）的表示常用字母p。

引理2-1：任何大于1的整数必有素因子。

  
证明使用反证法。插播一句，带有“必有”字样的定理都可尝试反证法，正难则反。

我们设集合S包含所有大于1且没有素因子的整数，只需证明S为空集即可。假设S不为空集，m∈S是S中最小的整数(m>1且没有素因子)。
情况分为2种：
（1）m不可能为素数，因为任何素数都有素因子（它本身）；
（2）m若为合数，则有m=ab（合数定义），则1<a<m,1<b<m;
既然a<m,必有a∉S.a必有素因子，设为p，因为p|a,且a|m，也即m必有素因子p，与m∈S矛盾，得证.

定理2-1 任何合数都至少有一个不超过n*1/2的素因子。（n>1是合数，则存在素数p，使得p<=n*1/2）

  
证明：
设任一合数n，根据定义有n=ab；
假设a>n*1/2，b>n*1/2，易证这种情况不存在，因为ab>n*1/2*n*1/2,矛盾于n=ab。同理，亦不可能有a,b<n*1/2.那么先得出结论，a,b其一必定不超过n*1/2.
假设此其一为a，根据引理2-1得出a必有素因子p，p|a。而a|n，所以p|n,满足p<=n*1/2.

判断n为素数的方法：如果所有素数p<=n*1/2，都不能整除n，则n是素数.

定理2-2（算术基本定理）：任何非零整数n可以表示出如下乘积形式：n=±p1^e1...prer。其中，p1...pr是互不相同的素数，e1...er是正整数.

  
1.该表示形式是唯一的（不计顺序）
2.认为±1可以表示成零个素数相乘的结果作为1.

接下来的文章中会证明该定理，此处暂时超纲.

欧几里得定理：素数有无穷多个.

  
其实它最好叫做欧几里得素数定理.
证明会使用算术基本定理。
假设素数仅有限个，设其为p1，...，pk;设M为这k个数的乘积，表示为M=p1...pk，设N=M+1.
显然，N>=2.
那么N也可以表示为一系列素数乘积的形式，则存在一个素数p，满足p|N.
且有p≠p1...pk（否则p|M，导致p|(N-M),有p|1，不可能）
所以，p不在p1...pk之中，这与假设相矛盾.

模运算

  
a mod b:设a,b∈Z且b>0，如果q,r∈Z满足a=qb+r,且0<=r<b,则定义：a mod b:=r.
在C，C++语言中mod表示为%.

对于负整数的模运算，则与正整数正好相反，
设a<0,b>0.a mod b可理解为a不断地加上b直至得数d>0(d<b)。
但事实上，还存在这种争议结果：求出的d只需满足0<|d|<|b|，也就是说假设-5%3，得数可以是1，也可以是-2.

现如今大多数人认可的是这个模运算定义：

若a,b为整数,c≠0，那么余数d满足a=kb+c(k∈Z).
且，0<=|r|<=|d|.

  
在MSVC2021和Python 3.8中，对于-5%3，前者输出了-2，后者输出了1.这表示不同的语言、编译器都会有不同的理解。
  

(重要)模运算的性质

1. b|a即a mod b=0
2. (a+b) mod n= (a mod n + b mod n)mod n
3. (a-b) mod n= (a mod n - b mod n)mod n
4. (axb) mod n= (a mod n x b mod n)mod n

模运算的性质第一条显而易见，除此之外模运算没有类似的除法性质(本身就包含了一重除法).

为什么说重要呢？因为运用该性质C++不容易发生算术溢出。预先设置一个模数，对每个因数取模再总体取模，这样不容易发生long long悲剧.