20220614现代密码学读书笔记
后面即将出现大量数学基础,看不懂的建议直接放弃或者先去复习下离散数学
4.1.3 模运算
若a===0(modn),则n|a,也就是a=mn
若n|(a-b),则a===bmodn
简单理解,被n整除的部分都可以减去,所以如果差值都可以被整除了,所以a和b在模n下相等(同余)
0 1 2 3 4 |
a===bmodn则b===amodn a===bmodn,b===cmodn,则a===cmodn a===bmodn,d|n,则a===bmodd |
证明,a===bmodn-->n|(a-b),d|n-->d|(a-b)-->a===bmodd
解释,d|n说明d是n的因子,a-b可以被n整除的话,也一定可以被n的因子整除,所以a和b在modd下也同余
a===bmodni,d=lcm(n1....nk),a===bmodd
模运算性质
0 1 2 3 4 |
(a % n + b % n) % n == (a + b) % n (a % n - b % n) % n == (a - b) % n (a % n - b % n) % n == (a * b) % n |
4.1.4 模指数运算
给定m,n计算a^m%n
显然a=7,n=19时,a^3+j=a^3,从a^4就重复了,循环周期为3
定义这个最小的循环周期为模n下a的阶,记为ordn(a)
定理: a在模n下的阶是=m则a^k===1modn的充要条件是k为n的倍数
4.1.5 费马定理、欧拉定理、卡米歇尔定理
Fermat定理:若p是素数,a是正整数,gcd(a,p)=1即ap互质,则a^(p-1)===1modp
欧拉函数:小于n且与n互质的正整数的个数
性质:
若n为质数则fn=n-1,显然因为n无法被分解了,除了自己以为就是n-1
若n为两个质数qp乘积,fn=fq * fp = (q-1) * (p-1)
若n有标准分解式,则fn=n(1-1/p1)*...*(1-1/pn)
欧拉定理:若a和n互质,则a^fn===1modn,其中fn为n的欧拉函数
卡米歇尔Carmichael函数: 对满足所有gcd(a,n)==1的a使得a^m===1modn同时成立的最小的正整数m
卡米歇尔定理:若a和n互质,则a^fn===1modn,其中fn为n的卡米歇尔函数
4.1.6 素数校验
定理:若n为正整数,若所有满足p<=sqrt(n)的素数p都无法整除n,n为素数
基于上面的定理有Eratosthenes筛法,列出2-n后删掉小于等于sqrt(n)的素数的倍数剩下的都是素数
当n很大时要排除的数量很大,实际上是不可行的
若p为大于2的素数,则方程x*x === 1 mod p的解只有 x===1和x===-1
Miller-Rabin概率检测基于这个条件做反向判断,可以快速判定不是
反之则有概率是素数,对于足够大的尝试次数若总不返回非素数,则会加大是素数的概率
AKS算法由Agrawal Kayal Saxena三个人提出,完全看不懂。。。。。总之有确定性的公式可以大大降低计算量了
4.1.7 欧几里得算法
对任意非负整数a和正整数b有gcd(a,b) = gcd(b,a%b)
欧几里得算法可使当ab较大时逐渐缩小运算输入的大小
扩展的欧几里得算法可求模乘法逆元,当互输入的两数质时,利用倒数第二轮的变量可快速计算
4.1.8 中国剩余定理
今有物不知其数,三三数之有二,五五数之有七,七七数之有二,问物几何?
也就是求解x的一元一次同余方程组
结论:对两两互质的正整数序列mi,M为mi联乘乘积,一元一次同余方程组对模M有唯一解
公式略
作用,对模M下的大数运算因同余性质可使用小数运算代替
印象中这里有秘密分割的应用,利用的就是中国剩余定理,可使密钥分开存放后必须集齐才可完整解密
原则是互质数字序列分割为多个密钥,加密密钥把M中排除掉对应的质数再做加密运算
明天继续第四章公钥密码,学数学果然是催眠和消磨时间的好方法,就是有点费脑子
回想当年大学开学之前看国防科技大学的老师MOOC讲高数证明,每天都能睡的很香
mark当前87页,下一节离散对数
0 Comments