20220616现代密码学读书笔记
4.1.9 离散对数
如果a的阶m等于φ(n),则称a为n的本原根(生成元)
若p是质数,a是p的本原根,则a, a*a, a*a*a,...a^(p-1)
的结果是1~(p-1)之间互不相同的所有值,因此对任意的1<=b<=p-1
都存在唯一的1<=i<=p-1
使得b===a^i mod p
。
称i为模p下以a为底的指标,记为i=ind(a,p,b)
,也就是离散对数
性质 ind(a,p,1)=0, ind(a,p,a)=1
显然易证:a^0 mod p == 1 mod p == 1, a^1 mod p == a
若a^z === a^q mod p 则z===q mod φ(p)
4.1.10 平方剩余
n是正整数,a是整数,满足gcd(a,n)=1,称a是模n的平方剩余,反之若x * x === a mod n
有解则称为非平方剩余
显然若p是质数则模p的平方剩余个数为(p-1)/2, 且与模p的非平凡剩余相等。
若a是模p的平方剩余则a的两个平方根0<=x1<=(p-1)/2, (p-1)/2+1<=x2<=(p-1)
,且x1或x2之一也是模p的平方剩余
legendre函数定义
p是质数,a是整数
若a被p整除,p|a则legendre(a,p)=0
若a是模p的平方剩余则legendre(a,p)=1
若a是模p的非平方剩余则legendre(a,p)=-1
公式 legendre(a,p) === a^((p-1)/2) mod p
性质,当p是奇素数且a,b都不能被p整除时
a === b mod p 则 legendre(a,p) = legendre(b,p)
legendre(a*b,p) = legendre(a,p) * legendre(b,p)
legendre(a*a,p) = 1
legendre(a+p,p) = legendre(a,p)
设n是正整数,当n表示为质因子的幂乘积的形式p1^a1 * p2^a2 * ... pk^ak
时
定义Jacobi(a,n) = legendre(a,p1) ^ a1 * legendre(a,p2) ^ a2 * legendre(a,pk) ^ ak
jacobi性质如下
当n是正合数,a,b与n互质时
a === b mod n 则 jacobi(a,n) = jacobi(b,n)
jacobi(a*b,n) = jacobi(a,n) * jacobi(b,n)
jacobi(a*b*b,n) = jacobi(a,n)
jacobi(a+n,n) = jacobi(a,n)
jacobi(1,n)=1, jacobi(-1,n)=(-1)^((n-1)/2), jacobi(2,n)=(-1)^((n^2-1)/8)
当m,n为大于2的奇数时
jacobi(m,n) = -1 ^ (((m-1)(n-1))/4) * jacobi(n,m)
易得当m===n===3 mod 4时 jacobi(m,n) = -jacobi(n,m)
否则jacobi(m,n)=jacobi(n,m)
综上所述计算jacobi不需要质因式分解,所以当计算legendre时可以先当作jacobi计算,如果有必要,计算jacobi(m,n)时可以通过m mod n 代替m,利用mn交换位置可以减小其中的一个数
jacobi和legendre的本质区别就是jacobi不表示平方剩余方程是否有解
设n为两个大质数p * q的积
由上面的结论可知1 ~ p-1的一半是模p的平方剩余,集合记为P,另一半记为NP
由上面的结论可知1 ~ q-1的一半是模q的平方剩余,集合记为Q,另一半记为NQ
而n的平方剩余a必须同时满足n是模p的平方剩余且a是模q的平方剩余, a属于P∩Q
所以与n互质小于n的a,有一半满足jacobi(a,n)=1记为c,另一半满足jacobi(a,n)=-1记为d
c可能属于P∩Q或NP∩NQ,d可能属于P∩NQ或NP∩Q
同理c中也有一半满足jacobi(a,p)=jacobi(a,q)=1的 a属于P∩Q 这些a就是n的平方剩余
c中剩下一半满足jacobi(a,p)=jacobi(a,q)=-1的 a属于NP∩NQ 这些a不是n的平方剩余
综上当p===q===3 mod 4 时,
由中国剩余定理可快速求出 x === y,-y mod p, x === z, -z mod q
反过来若已知四个中两个不同的根,就可快速的分解大整数n
jacobi(y,n) = -jacobi(z,n) 证明略
4.1.11 计算复杂度
这个数据结构里提过了,这里不赘述
若算法时间复杂度为多项式复杂度,就说这个算法是有效的,反之如果是指数复杂度则称之为无效
若问题存在多项式复杂度的算法可解,则称问题为P问题,也称之为计算可行的
NP问题是指可在多项式复杂度是时间内验证问题的一个解
问题若可在多项式时间内求解则一定可在多项式时间内验证,反之不行,因此P是NP的子集
NP问题中有一部分可以证明比其他问题困难,称之为NPC问题
下周继续第四章公钥密码,数学铺垫终于结束了,后面是公钥密码体制。现在回想起来好像当时听蔡老师没讲多久,自己看居然要这么久Orz
mark当前92页
0 Comments