Please enable JavaScript.
Coggle requires JavaScript to display documents.
第四章 二次剩余与方根 - Coggle Diagram
第四章 二次剩余与方根
勒让德符号
二次剩余
设m是正整数，若同余式x^2≡a(mod m)，(a,m)=1有解，则a称作模m的二次剩余(或平方剩余)
-
-
-
指标与原根
设<g>是一个n元循环群，a,b∈<g>，则indg(ab)≡indg(a)+indg(b) (mod n)
-
设m是大于1的正整数，g是模m的一个原根，(a,m)=1，d=(n,fai(m))，那么x^n≡a (mod m)有解的充要条件为a^(fai(m)/d)≡1 (mod m)
-
二次剩余的应用
Rabin加密算法
Alice选择两个不同的Blum素数p,q，计算n=pq，将p,q作为私钥，而公开n。
-
-
安全性
除了Alice之外，其他人不知道p,q，所以无法求解同余式c≡x^2(mod n)
Goldwasser –Micali加密算法
Alice选择两个不同的素数p，q，和整数y满足(y/p)=(y/q)=-1，计算n=pq，将p,q作为私钥，而公开n,y
加密
假设Bob想将二进制整数m=(b0b1b2⋯br)2加密后传给Alice，对每一个bi，Bob随机选择0<xi<n，若bi=0，计算ci≡xi^2(mod n)，否则计算ci≡yxi^2(mod n)，最终，密文c=（c0c1c2...cr)2，Bob将c传给Alice即可
-
-
原根存在的条件
当且仅当m=2，4，p^a,2p^a，p为奇素数，模m有原根