密码学二次剩余困难性问题The Quadratic Residuosity Problem

注：需要有密码学基础才能看懂，全文以N=21举例
基础推导：
假设模数$N=p\cdot q$ 。p和q是两个不同的奇素数，N是一个Blum Integer(参考链接)。举例N=21(p=3,q=7).$Z_N^{\ast }$是他的简化剩余系。则$Z_N^{\ast }$含有$(p-1)\cdot (q-1)$个元素(原理：欧拉函数).
$N=21,\varphi (N)=2\ast 6=12,Z_N^{\ast }=\{1,2,4,5,8,10,11,13,16,17,19,20\}.$
根据Chinese remainder theorem(中国剩余定理)，我们可以作如下映射$x\to (xmodp,xmodq)$,且是双射。
上面$Z_N^{\ast }$的点则变为了$\{(1,1),(2,2),(1,4),(2,5),(2,1),(1,3),(2,4),(1,6),(1,2),(2,3),(1,5),(2,6)\}.$这个点构成的$Z_N^{\ast }$同样构成乘法群。(1)封闭性，$x=(x_p,x_q),y=(y_p,y_q).z=(x_p\cdot y_{p}modp,y_p\cdot y_{q}modq).如果x,y属于Z_N^{\ast }那么x_p,x_q,y_p,y_q均为非零元，可知zmodp,zmodq同样为非零元。$ (2)单位元(1,1).(3)逆元满足。所以是一个群。

如果$r=x^{2}modN$是二次剩余，且是$Z_N^{\ast }$中的元素，那么他在$Z_N^{\ast }$中有四个平方根。
$x_p=xmodp,x_q=xmodq$$$x_1=(x_p,x_q)$$ $$x_2=(-x_p,x_q)$$ $$x_3=(x_p,-x_q)$$ $$x_4=(-x_p,-x_q)$$
$$x_1^2=x_2^2=x_3^2=x_4^2=rmodN$$
因此这四个均是r不同的平方根。
可知在$Z_N^{\ast }$中有$(p-1)\cdot (q-1)/4$个元素是二次剩余。($Z_N^{\ast }$有$(p-1)\cdot (q-1)个元素，每一个二次剩余在$Z_N^{*}$中有四个平方根，因此有(p-1)\cdot (q-1)/4个元素是二次剩余$)
在$Z_{21}^{\ast }$中：
$(1,1{)}^2=(1,1)mod21,(2,2{)}^2=(1,4)mod21,(1,4{)}^2=(1,2)mod21,(2,5{)}^2=(1,4)mod21剩下的自行计算总之最后结果为\{(1,1),(1,4),(1,2)\}三个平方剩余$

困难性问题：如果存在一个算法A能以多项式时间t，以概率$\ge \xi$寻找以模为N=pq的二次剩余，那么存在算法$A^{\ast }$以时间$t+O(logN{)}^{O(1)}$,以概率$\ge \frac{\xi }{2}$分解N。证明略。

参考资料：
1.The Group of Signed Quadratic Residues and Applications(Dennis Hofheinz and Eike Kiltz)
2.Notes on Zero Knowledge（Professor Luca Trevisan）
3.https://math.stackexchange.com/questions/1090675/blum-blum-shub-pseudorandom-numbers-clarification-on-prerequisites
4.https://crypto.stanford.edu/pbc/notes/numbertheory/crt.html
5.https://brilliant.org/wiki/legendre-symbol/

总结

以上是生活随笔为你收集整理的密码学二次剩余困难性问题The Quadratic Residuosity Problem的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。