数论基础1-1
整数
整数分为：素数，合数，1
素数：大于1，且只能被1和本身整除
| b | a，b是除数，a是被除数，例如3 | 12，如果b是可以整除a的素数，则b是素因子,2/3是素因子，4是因子 |
整数分解的唯一性定理
任何一个正整数a＞1，总可以分解为一系列素数乘积的形式，而且分解形式是唯一的
e.g. 36=2*2*3*3
数论基础1-2
素性检测
生成素数的正确方法——素性检测：随机生成一个大奇数，然后检测它是否为素数
Miller-Rabin算法是容易实现且广泛使用的算法
步骤：
- 通过伪随机序列发生器随机产生一个n比特的随机数p
- 将p的最高位（确保素数达到有效长度防止0）和最低位（确保为奇数）设置为1
- 检查p能否被小于2000的素数整除
- 随机选择a，a<p
- 用a对p进行素性测试（Miller-Rabin算法），若p没通过，抛弃p转第一步，或者p+2进行第三步
- 如果通过测试，转到第四步，如果p通过足够多次数的测试，认为p是素数
基于原理
- 在整数n中，约lnn个整数中就有一个素数
- 素数密度客观，检测方法很实用，约几秒钟就能生成一个素数
说明
素性检测算法是概率算法，会有一定的错误率，但是较低
- 可能会把合数误判成素数输出出来，
- 多次使用素数检测算法会减低错误率
数论基础2-1
公约数
- a1，a2…都可以被d整除，则称a1，a2…是d的公约数，最大的叫做最大公约数，记为gcd（a1，a2…）
- 互素：gcd（a1，a2…）=1，则称1，a2..互素
- 互素正整数不一定有素数：25,36
- 在个数不少于三个的互素正整数中，不一定两两互素：6,10,15
计算最大公约数的算法——欧几里得算法（辗转相除法）
基于的原理
若a=b*d+r，则gcd（a，b）=gcd（b，r）
b除数，d商，r余数
将大数的问题转换为小数的问题，a>b>r
不断地将除数和余数当作新的被除数和除数
a=38，b=26，则gcd（38,26）
-
38=26*1+12
-
26=12*2+2
-
12=2*6
最后一个非零余数就是所求gcd
数论基础2-2
公倍数
lcm（a,b）=a和b的最小公倍数
如何计算最小公倍数
只用加法计算最小公倍数
- 两者取最小
- 反复加自己
- 相等时停止
e.g.
| 30 | |
|---|---|
| 24 | |
| 18 | |
| 12 | 30 |
| 6 | 15 |
数论基础3-1
模运算
即求余数的运算，符号mod，a mod n =r，表示a除以n余数为r，n称为模数
e.g. 11 mod 7 = 4
模n同余
a mod n=b mod n=r，记作a ＝b （mod n)
称a和b在模n下是同余的
模运算的性质
- （a+b） mod n=（a mod n+b mod n） mod n
- （a*b） mod n=（a mod n*b mod n） mod n
- （a-b） mod n=（a mod n-b mod n） mod n
- 交换律 结合律 分配律
可以对模运算进行化简，使得中间结果不会溢出，一直保持在0-n-1之间
乘法链算法
a的m次方 mod n
a的25次方=a的16次方*a的8次方*a的1次方（从二进制表示看出的）