注：需要有密碼學(xué)基礎(chǔ)才能看懂，全文以N=21舉例
基礎(chǔ)推導(dǎo)：
假設(shè)模數(shù)$N=p?q$ 。p和q是兩個不同的奇素數(shù)，N是一個Blum Integer(參考鏈接)。舉例N=21(p=3,q=7).$Z_N^{?}$是他的簡化剩余系。則$Z_N^{?}$含有$(p?1)?(q?1)$個元素(原理：歐拉函數(shù)).
$N=21,?(N)=2?6=12,Z_N^{?}=\{1,2,4,5,8,10,11,13,16,17,19,20\}.$
根據(jù)Chinese remainder theorem(中國剩余定理)，我們可以作如下映射$x\to (xmodp,xmodq)$,且是雙射。
上面$Z_N^{?}$的點則變?yōu)榱?span id="ze8trgl8bvbq" class="katex--inline">$\{(1,1),(2,2),(1,4),(2,5),(2,1),(1,3),(2,4),(1,6),(1,2),(2,3),(1,5),(2,6)\}.$這個點構(gòu)成的$Z_N^{?}$同樣構(gòu)成乘法群。(1)封閉性，$x=(x_p,x_q),y=(y_p,y_q).z=(x_p?y_{p}modp,y_p?y_{q}modq).如果x,y屬于Z_N^{?}那么x_p,x_q,y_p,y_q均為非零元，可知zmodp,zmodq同樣為非零元。$ (2)單位元(1,1).(3)逆元滿足。所以是一個群。

如果$r=x^{2}modN$是二次剩余，且是$Z_N^{?}$中的元素，那么他在$Z_N^{?}$中有四個平方根。
$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^{?}$中有$(p?1)?(q?1)/4$個元素是二次剩余。($Z_N^{?}$有$(p?1)?(q?1)個元素，每一個二次剩余在$Z_N^{*}$中有四個平方根，因此有(p?1)?(q?1)/4個元素是二次剩余$)
在$Z_{21}^{?}$中：
$(1,1{)}^2=(1,1)mod21,(2,2{)}^2=(1,4)mod21,(1,4{)}^2=(1,2)mod21,(2,5{)}^2=(1,4)mod21剩下的自行計算總之最后結(jié)果為\{(1,1),(1,4),(1,2)\}三個平方剩余$

困難性問題：如果存在一個算法A能以多項式時間t，以概率$\ge \xi$尋找以模為N=pq的二次剩余，那么存在算法$A^{?}$以時間$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/

總結(jié)

以上是生活随笔為你收集整理的密码学二次剩余困难性问题The Quadratic Residuosity Problem的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。