發新話題
打印

用Maxima學密碼學-Lattice Reduction應用2-找出同餘方程式較小的解

推到噗浪
推到臉書

用Maxima學密碼學-Lattice Reduction應用2-找出同餘方程式較小的解









公式

範例

問題敘述

設同餘方程式為\(f(x)=a_d x^d+a_{d-1}x^{d-1}+\ldots+a_1 x+a_0\equiv 0 \pmod{N}\)
利用LLL方法可以找出比邊界\(X\)還小的解\(x_0\)(\( |\;x_0|\;<X=N^{\displaystyle \frac{2}{d(d+1)}}\))
使得\(f(x_0)\equiv 0 \pmod{N}\)
設同餘方程式為\(f(x)=1131x^3+14531x^2+116024x+57592\equiv 0 \pmod{123107}\)
\(\displaystyle d=3,X=N^{\frac{2}{3\cdot 4}}=7.0531\)
利用LLL方法可以找出比邊界\(X=7\)還小的解
使得\(f(x_0)\equiv 0 \pmod{123107}\)

步驟1.產生lattice證明向量線性組合方程式的解和原方程式相同。

將\(f(x)\)各項係數取lattice如下
\(B=\matrix{\matrix{常數項&1次方&2次方&\ldots&d-1次方&d次方&} \cr \left[\matrix{a_0&a_1X&a_2X^2&\ldots&a_{d-1}X^{d-1}&a_dX^d&\frac{1}{d+1} \cr N&0&0&0&0&0&0\cr
0&NX&0&0&0&0&0\cr
0&0&NX^2&0&0&0&0\cr
&&&\ddots&&&\cr
0&0&0&0&NX^{d-1}&0&0\cr
0&0&0&0&0&NX^d&0}\right]}\)
該lattice的向量線性組合為
\(\matrix{\matrix{s\cr -s_0 \cr -s_1 \cr -s_2 \cr \vdots \cr -s_{d-1}\cr -s_d}&\left[\matrix{a_0&a_1X&a_2X^2&\ldots&a_{d-1}X^{d-1}&a_dX^d&\frac{1}{d+1} \cr N&0&0&0&0&0&0\cr
0&NX&0&0&0&0&0\cr
0&0&NX^2&0&0&0&0\cr
&&&\ddots&&&\cr
0&0&0&0&NX^{d-1}&0&0\cr
0&0&0&0&0&NX^d&0}\right]}\)
\(=\left[\matrix{sa_0&sa_1X&sa_2X^2&\ldots&sa_{d-1}X^{d-1}&sa_dX^d&\frac{s}{d+1}\cr
-s_0N&0&0&0&0&0&0\cr
0&-s_1NX&0&0&0&0&0\cr
0&0&-s_2NX^2&0&0&0&0\cr
0&0&0&\ddots&0&0&0\cr
0&0&0&0&-s_{d-1}NX^{d-1}&0&0\cr
0&0&0&0&0&-s_dNX^d&0}\right]\)
\(=[(sa_0-s_0N),(sa_1-s_1N)X,\ldots,(sa_{d-1}-s_{d-1}N)X^{d-1},(sa_d-s_dN)X^d,\frac{s}{d+1}]\)

將向量線性組合前\(d+1\)個分量除以\(X^i\)為係數的方程式
\(h(x)=(sa_0-s_0N)+(sa_1-s_1N)x+\ldots+(sa_{d-1}-s_{d-1}N)x^{d-1}+(sa_d-s_dN)x^d\)
 \(=s(a_0+a_1x+\ldots+a_{d-1}x^{d-1}+a_d x^d)-N(s_0+s_1x^1+\ldots+s_{d-1}x^{d-1}+s_dx^d)\)
 \(=sf(x)-N(s_0+s_1x^1+\ldots+s_{d-1}x^{d-1}+s_dx^d)\)
得到\(h(x)\equiv sf(x)\pmod{N}\)
若\(x=x_0\)是\(h(x)\equiv 0 \pmod{N}\)的解,那\(x=x_0\)也會是\(f(x)\equiv 0 \pmod{N}\)的解。
\(B=\left[\matrix{57592&116024\cdot 7^1&14531\cdot 7^2&1131\cdot 7^3& \frac{1}{4}\cr
123107&0&0&0&0\cr
0&123107\cdot 7^1&0&0&0\cr
0&0&123107\cdot 7^2&0&0\cr
0&0&0&123107\cdot 7^3&0}\right]\)

  \(\left[\matrix{57592&812168&712019&387933&\frac{1}{4}\cr
123107&0&0&0&0\cr
0&861749&0&0&0\cr
0&0&6032243&0&0\cr
0&0&0&42225701&0}
\right]\)

步驟2.經LLL化簡得到短向量所形成的方程式不需再同餘\(N\)。

lattice經LLL化簡後第一行為整個lattice中較短向量
取前\(d+1\)個分量\((c_0,c_1X,\ldots,c_{d-1}X^{d-1},c_dX^d)\)將每個分量除以\(X^i\)得到係數\(c_i\)
將係數\(c_i\)組成新方程式\(\displaystyle h(x)=\sum_{i=0}^d c_ix^i\)
若每個係數\(\displaystyle |\;c_i|\;<\frac{N}{(d+1)X^i}\),要求的解\(x\)小於邊界\(X\)(\(|\;x|\;<X\))。
\(\displaystyle |\;h(x)|\;= |\;\sum_{i=0}^d c_i x^i|\;\le \sum_{i=0}^d |\;c_i|\; |\;x|\;^i<\sum_{i=0}^d \frac{N}{(d+1)X^i} X^i\)
\(\displaystyle =\sum_{i=0}^d \frac{N}{d+1}=\frac{N}{d+1}\cdot (d+1)=N\),得到\(|\;h(x)|\;<N\)
原本要解同餘方程式\(h(x)\equiv 0\pmod{N}\),因為\(|\;h(x)|\;<N\),變成解一般方程式\(h(x)=0\)。
\(B=\left[\matrix{-9310&13671&-4704&343&5905\cr
9310&-13671&4704&-343&\frac{99487}{4}\cr
85867&54684&-18816&1372&-\frac{28627}{4}\cr
-28932&-96173&-263424&19208&-\frac{31457}{4}\cr
44745&-4151&-100499&-432523&\frac{3537}{2}}\right]\)
\(\displaystyle h(x)=-9310+\frac{13671}{7^1}x-\frac{4704}{7^2}x^2+\frac{343}{7^3}x^3\)
  \(=-9310+1953x-96x^2+x^3\)
其中各項係數符合
\(\displaystyle |\;-9310|\;<\frac{123107}{4\cdot 7^0}=30776.75\)
\(\displaystyle |\;1953|\;<\frac{123107}{4\cdot 7^1}=4396.68\)
\(\displaystyle |\;-96|\;<\frac{123107}{4\cdot 7^2}=628.10\)
\(\displaystyle |\;1|\;<\frac{123107}{4\cdot 7^3}=89.73\)

步驟3.解一般方程式得到小於\(X\)的解\(x=x_0\)。

\(h(x)=(x-7)(x-19)(x-70)=0\)
\(x=7,19,70\),也是\(f(x)\equiv 0 \pmod{123107}\)的解。
驗算
\(f(7)=1969712\equiv 0\pmod{123107}\)
\(f(19)=15265268\equiv 0\pmod{123107}\)
\(f(70)=467314172\equiv 0\pmod{123107}\)


步驟4.計算邊界\(X\)的範圍
計算行列式值\(\displaystyle det(B)\)
\(=\left|\ \matrix{a_0&a_1X&a_2X^2&\ldots&a_{d-1}X^{d-1}&a_dX^d&\frac{1}{d+1} \cr N&0&0&0&0&0&0\cr
0&NX&0&0&0&0&0\cr
0&0&NX^2&0&0&0&0\cr
&&&\ddots&&&\cr
0&0&0&0&NX^{d-1}&0&0\cr
0&0&0&0&0&NX^d&0}\right|\)
以第\(d+2\)行降階,0降階後仍是0,只剩下\(\displaystyle \frac{1}{d+1}\)再乘上餘因子
\(\displaystyle =\frac{1}{d+1}\left|\matrix{N&0&0&0&0&0\cr
0&NX&0&0&0&0\cr
0&0&NX^2&0&0&0\cr
&&&\ddots&&\cr
0&0&0&0&NX^{d-1}&0\cr
0&0&0&0&0&NX^d} \right|\)
行列式只有對角線有值,其餘為0,行列式值由對角線元素相乘
\(\displaystyle =\frac{N^{d+1}X^{\frac{d(d+1)}{2}}}{d+1}\)

經LLL化簡後的第一列向量\(\vec{b_1}\)是整個lattice中較短的向量,向量長度符合不等式\(\Vert\;\vec{b_1}\Vert\;\le 2^{(n-1)/4}\cdot (det(B))^{1/n}\)
https://en.wikipedia.org/wiki/Le ... reduction_algorithm

其中lattice有\(d+2\)列,\(n=d+2\)。將\(\displaystyle det(B)=\frac{N^{d+1}X^{\frac{d(d+1)}{2}}}{d+1}\)代入得到\(\displaystyle \Vert\;\vec{b_1}\Vert\;\le 2^{\frac{d+1}{4}}\left(\frac{N^{d+1}X^{\frac{d(d+1)}{2}}}{d+1}\right)^{\frac{1}{d+2}}\)

若想找到邊界\(X\)的範圍,需要第一列向量長度再小於\(\displaystyle \frac{N}{d+1}\)和需要\(\displaystyle 2^{\frac{d+1}{4}}\left(\frac{N^{d+1}X^{\frac{d(d+1)}{2}}}{d+1}\right)^{\frac{1}{d+2}}<\frac{N}{d+1}\)
不等式兩邊\(d+2\)次方,\(\displaystyle 2^{\frac{(d+1)(d+2)}{4}}\frac{N^{d+1}X^{\frac{d(d+1)}{2}}}{d+1}<\frac{N^{d+2}}{(d+1)^{d+2}}\)
重新整理不等式,\(\displaystyle 2^{\frac{(d+1)(d+2)}{4}}(d+1)^{d+1}X^{\frac{d(d+1)}{2}}<N\)
令\(\epsilon(d)=2^{\frac{(d+1)(d+2)}{4}}(d+1)^{d+1}\)僅和\(d\)有關的函數,當\(d\)固定時\(\epsilon(d)\)是常數
\(\epsilon(d)X^{\frac{d(d+1)}{2}}<N\),得到邊界\(\displaystyle X<N^{\frac{2}{d(d+1)}}\)

參考資料
Håstad, J.: Solving Simultaneous Modular Equations of Low Degree. SIAM Journalon Computing 17(2), 336–341 (1988)
http://www.csc.kth.se/~johanh/rsalowexponent.pdf
http://citeseerx.ist.psu.edu/vie ... p=rep1&type=pdf
註:
原本論文以\(n\)代表邊界,但之後的資料改以\(X\)表示,本文章也以\(X\)表示能找到小於\(X\)的解\(x_0\)。



請下載LLL.zip,解壓縮後將LLL.mac放到C:\maxima-5.43.2\share\maxima\5.43.2\share目錄下
要先載入LLL.mac才能使用LLL指令

(%i1) load("LLL.mac");
(%o1) C:/maxima-5.43.2/share/maxima/5.43.2/LLL.mac

同餘方程式\(f(x)\)
(%i2) fx:1131*x^3+14531*x^2+116024*x+57592;
(fx) \(1131x^3+14531x^2+116024x+57592\)

\(f(x)\equiv 0\pmod{N}\)
(%i3) N:123107;
(N) \(123107\)

\(f(x)\)的次數d
(%i4) d:hipow(fx,x);
(d) \(3\)

希望能找到\(|\;x|\;<X=N^{2/d(d+1)}\),\(f(x)\equiv 0\pmod{N}\)
(%i5) X:floor(N^(2/(d*(d+1))));
(X) \(7\)

定義lattice產生方式
(%i7)
kill(genlattice)$
genlattice[i,j]:=
if i=1 and j=d+2 then 1/(d+1)/*第1列第d+2行為1/(d+1)*/
else if i=1 then coeff(fx,x,j-1)*X^(j-1)/*第一行為f(x)係數乘上X^(j-1)*/
else if i=j+1 then N*X^(j-1)/*子對角線為NX^(j-1)*/
else 0$/*剩下元素為0*/


根據\(f(x)\)係數,產生lattice
(%i8) latticeB:genmatrix(genlattice,d+2,d+2);
(latticeB) \(\left[\matrix{\displaystyle 57592&812168&712019&387933&\frac{1}{4}\cr
123107&0&0&0&0\cr
0&861749&0&0&0\cr
0&0&6032243&0&0\cr
0&0&0&42225701&0}\right]\)

經LLL化簡後的lattice B
(%i9) latticeB: LLL(latticeB);
(latticeB) \(\left[\matrix{\displaystyle -9310&13671&-4704&343&5905\cr
9310&-13671&4704&-343&\frac{99487}{4}\cr
85867&54684&-18816&1372&-\frac{28627}{4}\cr
-28932&-96173&-263424&19208&-\frac{31457}{4}\cr
44745&-4151&-100499&-432523&\frac{3537}{2}}\right]\)

lattice第一行是整個lattice中較短的向量\(\vec{b_1}\)
(%i10) b1:latticeB[1];
(b1) \([-9310,13671,-4704,343,5905]\)

取\(\vec{b_1}\)前\(d+1\)個分量除以\(X^i\)乘上\(x^i\)形成\(h(x)\)
(%i11) hx:sum(b1[i+1]/X^i*x^i,i,0,d);
(hx) \(x^3-96x^2+1953x-9310\)

將\(h(x)\)因式分解
(%i12) factor(hx);
(%o12) \((x-70)(x-19)(x-7)\)

得到\(h(x)\)的解,因為這個範例比較簡單\(f(x)\equiv 0\pmod{N}\)的三個解都找出來
(%i13) roots:solve(hx,x);
(roots) \([x=7,x=19,x=70]\)

驗證答案
(%i14)
for root in roots do
  (print(將,root,代入f(,rhs(root),)=,ev(fx,root),≡0 (mod ,N,))
  )$

將\(x=7\)代入\(f(7)=1969712\equiv 0 \pmod{123107}\)
將\(x=19\)代入\(f(19)=15265268\equiv 0 \pmod{123107}\)
將\(x=70\)代入\(f(70)=467314172\equiv 0 \pmod{123107}\)

TOP

發新話題