方法 | 範例 |
問題敘述 | |
| 設同餘方程式為\(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}\) | |
| 公式 | 範例 |
| 產生金鑰 1.選擇兩個不相同的大質數\(p\)和\(q\)，其中\(p\equiv 3\pmod{4}\)和\(q\equiv 3\pmod{4}\) 2.計算\(n=pq\) \(n\)是公鑰和\((p,q)\)是私鑰 | 私鑰\(p=7\)和\(q=11\) 公鑰\(n=77\) |
| 加密 訊息\(M\)轉換成數字\(m\)(\(m<n\)) 計算密文\(c=m^2\pmod{n}\) | 明文\(m=20\) 密文\(c=20^2=400=15\pmod{77}\) |
| 解密 計算密文\(c\)在同餘\(n\)的平方根得到\(m\) 1.計算\(c\)在同餘\(p\)和\(q\)的平方根 \(m_p=c^{\frac{1}{4}(p+1)}\pmod{p}\) \(m_q=c^{\frac{1}{4}(q+1)}\pmod{q}\) 2.使用擴展歐幾里得演算法計算\(y_p\)和\(y_q\)使得\(y_p\cdot p+y_q\cdot q=1\)。 3.使用中國餘數定理\(c\)在同餘\(n\)的平方根 \(r_1=(y_p\cdot p\cdot m_q+y_q\cdot q\cdot m_p)\pmod{n}\) \(r_2=n-r_1\) \(r_3=(y_p\cdot p\cdot m_q-y_q\cdot q\cdot m_p)\pmod{n}\) \(r_4=n-r_3\) 4個\(r_i\)值其中一個會是明文\(m\) | 1.計算\(m_p=15^{\frac{1}{4}(7+1)}=15^2=1\pmod{7}\) \(m_q=15^{\frac{1}{4}(11+1)}=15^3=9\pmod{11}\) 2.使用擴展歐幾里得演算法計算\(y_p\)和\(y_q\) \(p=7\)，\(q=11\) \(q-p=11-7=4\) \(p-(q-p)=7-4\)，\(2p-q=3\) \((q-p)-(2p-q)=4-3\)，\(-3p+2q=1\) \(y_p=-3\)和\(y_q=2\) 3.計算4個\(r_i\)值 \(r_1=(-3\cdot 7\cdot 9+2\cdot 11\cdot 1)\pmod{77}=64\) \(r_2=77-64=13\) \(r_3=(-3\cdot 7\cdot 9-2\cdot 11\cdot 1)\pmod{77}=20\) \(r_4=77-20=57\) 其中\(r_3=20\)是當初的明文 |
Håstad方法 | Coppersmith方法 |
| 可以找出比邊界\(X\)還小的解\(x_0\)(\(\displaystyle |\;x_0|\;<X=N^{\displaystyle \frac{2}{d(d+1)}}\)) | 可以找出比邊界\(X\)還小的解\(x_0\)(\(\displaystyle |\;x_0|\;<X=\frac{1}{2}N^{\displaystyle \frac{1}{d}}\)) |
| 將\(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}\)的解。 | 將\(f(x)\)各項係數取lattice如下 \(B=\left[\matrix{1&0&0&\ldots&0&0&a_0 \cr 0&X^{-1}&0&0&0&0&a_1\cr 0&0&X^{-2}&0&0&0&a_2\cr 0&0&0&X^{-3}&0&0&a_3\cr &&&\ddots&&&\cr 0&0&0&0&X^{-(d-1)}&0&a_{d-1}\cr 0&0&0&0&0&X^{-d}&a_d\cr 0&0&0&0&0&0&N}\right] \matrix{常數項\cr 1次方\cr 2次方\cr 3次方\cr \vdots \cr d-1次方\cr d次方}\) 該lattice的向量線性組合為 \(\matrix{\matrix{1\cr x_0 \cr x_0^2 \cr x_0^3 \cr \vdots \cr x_0^{d-1}\cr x_0^d\cr -y_0}&\left[\matrix{1&0&0&\ldots&0&0&a_0 \cr 0&X^{-1}&0&0&0&0&a_1\cr 0&0&X^{-2}&0&0&0&a_2\cr 0&0&0&X^{-3}&0&0&a_3\cr &&&\ddots&&&\cr 0&0&0&0&X^{-(d-1)}&0&a_{d-1}\cr 0&0&0&0&0&X^{-d}&a_d\cr 0&0&0&0&0&0&N}\right]}\) \(=\left[\matrix{1&0&0&\ldots&0&0&a_0 \cr 0&x_0^1X^{-1}&0&0&0&0&a_1x_0^1\cr 0&0&x_0^2X^{-2}&0&0&0&a_2x_0^2\cr 0&0&0&x_0^3X^{-3}&0&0&a_3x_0^3\cr &&&\ddots&&&\cr 0&0&0&0&x_0^{(d-1)}X^{-(d-1)}&0&a_{d-1}x_0^{(d-1)}\cr 0&0&0&0&0&x_0^{d}X^{-d}&a_dx_0^d\cr 0&0&0&0&0&0&-y_0N}\right]\) \(\displaystyle =\left[1,\left(\frac{x_0}{X}\right),\left(\frac{x_0}{X}\right)^2,,\left(\frac{x_0}{X}\right)^3,\ldots,,\left(\frac{x_0}{X}\right)^{d-1},\left(\frac{x_0}{X}\right)^d,f(x_0)-y_0N\right]\) 若能找到\(x_0,y_0\)使得\(|\;x_0|\;<X\)、\(f(x_0)-y_0N\equiv 0\pmod{N}\) 此時向量長度\(\sqrt{1^2+\left(\frac{x_0}{X}\right)^2+\left(\frac{x_0}{X}\right)^4+\ldots+\left(\frac{x_0}{X}\right)^{2d}+0^2}<\sqrt{d+1}\)是短向量。 |
方法 | 範例 |
問題敘述 | |
| 設同餘方程式為\(p(x)=x^k+a_{k-1}x^{k-1}+\ldots+a_1 x+a_0\equiv 0 \pmod{N}\) 且\(p(x)\)為monic(最高次方項係數為1)且不可分解。 利用LLL方法可以找出比邊界\(X\)還小的解\(x_0\)(\(\displaystyle |\;x_0|\;<X=\frac{1}{2}N^{\displaystyle \frac{1}{k}}\)) 使得\(p(x_0)\equiv 0 \pmod{N}\) | 設同餘方程式為\(p(x)=x^2+14x+19\equiv 0\pmod{35}\) 且\(p(x)\)為monic(最高次方項係數為1)且不可分解。 利用LLL方法可以找出比邊界\(X\)還小的解 使得\(p(x_0)\equiv 0 \pmod{35}\) |
步驟1：計算參數\(h\)和\(X\) | |
| 步驟3需要\(hk\ge7\)、\(\displaystyle h-1\ge (hk-1)(\frac{1}{k}-\epsilon)\)和\(\displaystyle X=\frac{1}{2}N^{\frac{1}{k}}\) \(hk\ge7\)化簡為\(\displaystyle h\ge \frac{7}{k}\) \(\displaystyle h-1\ge (hk-1)(\frac{1}{k}-\epsilon)\)化簡為 \(\displaystyle h-1\ge h-\epsilon hk-\frac{1}{k}+\epsilon\) \(\displaystyle \epsilon hk\ge \frac{k+\epsilon k-1}{k}\) \(\displaystyle h\ge \frac{k+\epsilon k-1}{\epsilon k^2}\) 兩個條件合併一起 \(\displaystyle h\ge max\left(\frac{7}{k},\frac{k+\epsilon k-1}{\epsilon k^2}\right)\) | \(p(x)\)最高次方為2次方\((k=2)\) 設\(\epsilon=0.1\) \(\displaystyle h\ge max\left(\frac{7}{2},\frac{2+0.1\cdot 2-1}{0.1\cdot 2^2}\right)=max(3.5,3)\) \(h\ge 4\)但本範例取\(h=3\)就能得到答案 \(\displaystyle X=\frac{1}{2}35^{1/2}=2.958\)，取\(X=2\) |
步驟2：產生矩陣\(M\) | |
| 矩陣\(M\)是大小\((2hk-k)\times(2hk-k)\)的上三角矩陣 \(M=\left[\matrix{D&A\cr0_{hk}&D'}\right]\) 左上角矩陣\(D=(d(i,j))\)是大小\(hk\times hk\)的對角矩陣， 對角線元素為\(d_{i,i}=\delta X^{1-i}\)，\(\displaystyle \delta=\frac{1}{\sqrt{hk}}\) 右上角矩陣\(A=(a_{i,j})\)是大小\((hk\times (h-1)k)\)矩陣， 矩陣元素\(a_{i,j}\)是\(x^u(p(x))^v\)的\(x^i\)項係數 其中\(\displaystyle v=\lfloor\;\frac{k+j-1}{k}\rfloor\;\)和\(u=(j-1)-k(v-1)\) 左下角\(0_{hk}\)為零矩陣 右下角矩陣\(D'=(d_{i,j}')\)是大小\(((h-1)k\times (h-1)k)\)的對角矩陣， 對角線元素為\(d_{i,i}'=N^v\) \(M\)為上三角矩陣，行列式值為對角線元素相乘 \(\displaystyle det(M)=\prod_{g=0}^{hk-1}\delta X^{-g}\prod_{\gamma(i,j)=hk}^{2hk-k}N^j\) \(\displaystyle =\delta^{hk} X^{-{\frac{hk(hk-1)}{2}}}N^{\frac{hk(h-1)}{2}}\) \(\displaystyle =(N^{h-1}X^{-(hk-1)}(hk)^{-1})^{\frac{hk}{2}}\) －－－－－－－－－－－－－－－－－－－ \(p(x)=x^2+ax+b\equiv 0\pmod{N}\) \(xp(x)=x^3+ax^2+bx\equiv 0\pmod{N}\) \((p(x))^2=x^4+cx^3+dx^2+ex+f\equiv 0\pmod{N^2}\) \(x(p(x))^2=x^5+cx^4+dx^3+ex^2+fx\equiv 0\pmod{N^2}\) \(M=\left[\matrix{\matrix{\delta&&&&&\cr&\delta X^{-1}&&&&\cr&&\delta X^{-2}&&&\cr&&&\delta X^{-3}&&\cr&&&&\delta X^{-4}&\cr&&&&&\delta X^{-5}}&\matrix{│\cr │\cr │\cr │}& \matrix{ b&0&f&0\cr a&b&e&f\cr 1&a&d&e\cr &1&c&d\cr &&1&c\cr &&&1}\cr ―――――――――&┼&――――――― \cr \matrix{0}&\matrix{│\cr │\cr │}&\matrix{N&&&\cr &N&&\cr &&N^2&\cr &&&N^2}}\right]\) 設\(r\)向量左手邊為\(r_g=x_0^g\)，右手邊為\(x_0\)和\(y_0\)的非負次方\(r_{\gamma(i,j)}=-x_0^iy_0^j\) \(r=[1,x_0,x_0^2,x_0^3,x_0^4,x_0^5,-y_0,-x_0y_0,-y_0^2,-x_0y_0^2]\) 計算向量線性組合\(s=rM\) \(\displaystyle s=[1,\delta\frac{x_0}{X},\delta\left(\frac{x_0}{X}\right)^2,\delta\left(\frac{x_0}{X}\right)^3,\delta\left(\frac{x_0}{X}\right)^4,\delta\left(\frac{x_0}{X}\right)^5,\) \(-p(x_0)-y_0N,x_0p(x_0)-x_0y_0N,(p(x_0))^2-y_0^2N^2,x_0(p(x_0))^2-x_0y_0^2N^2]\) 存在\(|\;x_0|\;<X\)和\(y_0\)使得\(p(x_0)-y_0N=0\) \(\displaystyle s=\left[1,\delta\frac{x_0}{X},\delta\left(\frac{x_0}{X}\right)^2,\delta\left(\frac{x_0}{X}\right)^3,\delta\left(\frac{x_0}{X}\right)^4,\delta\left(\frac{x_0}{X}\right)^5,0,0,0,0\right]\) 計算向量\(s\)長度比1短 \(\displaystyle \Vert\;s\Vert\;=\sqrt{\sum_{k=0}^{hk-1}\left(\delta \left( \frac{x_0}{X}\right)^{k}\right)^2}<\sqrt{\sum_{k=0}^{hk-1}(\delta \cdot 1)^2}=\sqrt{\delta^2\cdot hk}=1\) | \(p(x)=x^2+14x+19\equiv 0\pmod{35}\) \(xp(x)=x^3+14x^2+19x\equiv 0\pmod{35}\) \(p(x)^2=x^4+28x^3+234x^2+532x+361\equiv 0\pmod{35^2}\) \(xp(x)^2=x^5+28x^4+234x^3+532x^2+361x\equiv 0\pmod{35^2}\) 原本\(\displaystyle \delta=\frac{1}{\sqrt{hk}}=\frac{1}{\sqrt{6}}\)，但本範例忽略\(\delta\)也能算出答案 \(M=\left[\matrix{\matrix{1&&&&&\cr&2^{-1}&&&&\cr&&2^{-2}&&&\cr&&&2^{-3}&&\cr&&&&2^{-4}&\cr&&&&&2^{-5}}&\matrix{│\cr │\cr │\cr │}& \matrix{ 19&0&361&0\cr 14&19&532&361\cr 1&14&234&532\cr &1&28&234\cr &&1&28\cr &&&1}\cr ―――――――――&┼&――――――― \cr \matrix{0}&\matrix{│\cr │\cr │}&\matrix{35&&&\cr &35&&\cr &&1225&\cr &&&1225}}\right]\) \(det(M)=1\cdot 2^{-1}\ldots 2^{-5}\cdot 35 \cdot 35 \cdot 1225 \cdot 1225\) \(=2^{-15}35^6\) |
步驟3：矩陣\(M\)基本列運算得到\(\widehat{M}\) | |
| 因為\(p(x)\)為monic(最高次方項係數為1)，在矩陣\(A\)的對角線元素為1，進行基本列運算將右上角化簡為零，右下角化簡為零，再將對角線元素為1的一整列移到整個矩陣下方。 \(\widetilde{M}=\left[\matrix{\widehat{M}&│&0_{(hk\times (h-1)k)}\cr ―&┼&――――――\cr A'&│&I_{(h-1)k}}\right]\) 得到左上角矩陣\(\widehat{M}\) －－－－－－－－－－－－－－－－－－－ \(|\;det(M)|\;=|\;det(\widetilde{M})|\;=|\;det(\widehat{M})det(I)|\;=|\;det(\widehat{M})|\;\) 得到\(\displaystyle det(M)=(N^{h-1}X^{-(hk-1)}(hk)^{-1})^{\frac{hk}{2}}=det(\widehat{M})\) 設\(hk\ge 7\)，可推得\(\displaystyle hk<2^{\frac{hk-1}{2}}\)，\((hk)^{-1}>2^{-\frac{(hk-1)}{2}}\) \(\displaystyle det(\widehat{M})>(N^{h-1}X^{-(hk-1)}2^{-\frac{(hk-1)}{2}})^{\frac{hk}{2}}\) 設\(\displaystyle X=\frac{1}{2}N^{\frac{1}{k}-\epsilon}\)，可推得\(\displaystyle X^{-1}=2N^{-(\frac{1}{k}-\epsilon)}\)，\(\displaystyle X^{-(hk-1)}=2^{hk-1}N^{-(hk-1)(\frac{1}{k}-\epsilon)}\) \(\displaystyle det(\widehat{M})>(N^{n-1-(hk-1)(\frac{1}{k}-\epsilon)}\cdot 2^{+\frac{(hk-1)}{2}})^{\frac{hk}{2}}\) 設\(\displaystyle n-1\ge (hk-1)(\frac{1}{k}-\epsilon)\) \(\displaystyle det(\widehat{M})>(N^0\cdot 2^{+\frac{(hk-1)}{2}})2^{\frac{hk}{2}}=2^{\frac{(hk)(hk-1)}{4}}\) 設\(n=hk=dim(\widehat{M})\) \(\displaystyle det(\widehat{M})>2^{\frac{n(n-1)}{4}}\) \(\displaystyle det(\widehat{M})^{\frac{1}{n}}>2^{\frac{n-1}{4}}\) \(\displaystyle det(\widehat{M})^{\frac{1}{n}}\cdot 2^{-\frac{n-1}{4}}>1\) 由步驟2結論可知向量\(s\)長度小於1(\(1>\Vert\;s\Vert\;\)) 得到\(\displaystyle det(\widehat(M))^{\frac{1}{n}}\cdot 2^{-\frac{n-1}{4}}>\Vert\;s\Vert\;\) | 將右上角化簡為零 \(\widetilde{M}=\left[\matrix{\matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}\cr &\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}\cr &&\frac{1}{4}&-\frac{7}{4}&\frac{79}{8}&-\frac{105}{2}\cr &&&\frac{1}{8}&-\frac{7}{4}&\frac{275}{16}\cr &&&&\frac{1}{16}&-\frac{7}{8}\cr &&&&&\frac{1}{32}}&\matrix{│\cr│\cr│\cr│\cr│\cr│}&\matrix{\displaystyle 0&0&0&0\cr 0&0&0&0\cr 1&0&0&0\cr &1&0&0\cr &&1&0\cr &&&1}\cr ――――――――――――――&┼&―――――――――\cr \matrix{0}&\matrix{│\cr│\cr│\cr│}&\matrix{35&&&\cr&35&&\cr&&1225&\cr&&&1225}}\right]\) 將右下角化簡為零 \(\widetilde{M}=\left[\matrix{\matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}\cr &\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}\cr &&\frac{1}{4}&-\frac{7}{4}&\frac{79}{8}&-\frac{105}{2}\cr &&&\frac{1}{8}&-\frac{7}{4}&\frac{275}{16}\cr &&&&\frac{1}{16}&-\frac{7}{8}\cr &&&&&\frac{1}{32}}&\matrix{│\cr│\cr│\cr│\cr│\cr│}&\matrix{\displaystyle 0&0&0&0\cr 0&0&0&0\cr 1&0&0&0\cr &1&0&0\cr &&1&0\cr &&&1}\cr ――――――――――――――&┼&―――\cr \matrix{\displaystyle &&-\frac{35}{4}&\frac{245}{4}&-\frac{2765}{8}&-\frac{3675}{2}\cr &&&-\frac{35}{8}&\frac{245}{4}&-\frac{9625}{16}\cr &&&&-\frac{1225}{16}&-\frac{8575}{8}\cr &&&&&-\frac{1225}{32}}&\matrix{│\cr│\cr│\cr│}&\matrix{0&&&\cr&0&&\cr&&0&\cr&&&0}}\right]\) 將對角線元素為1的一整列移到整個矩陣下方 \(\widetilde{M}=\left[\matrix{\matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}\cr &\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}\cr &&-\frac{35}{4}&\frac{245}{4}&-\frac{2765}{8}&-\frac{3675}{2}\cr &&&-\frac{35}{8}&\frac{245}{4}&-\frac{9625}{16}\cr &&&&-\frac{1225}{16}&-\frac{8575}{8}\cr &&&&&-\frac{1225}{32}}&\matrix{│\cr│\cr│\cr│\cr│\cr│}&\matrix{\displaystyle 0&0&0&0\cr 0&0&0&0\cr 0&0&0&0\cr &0&0&0\cr &&0&0\cr &&&0}\cr ――――――――――――――&┼&―――\cr \matrix{\displaystyle & &\frac{1}{4}&-\frac{7}{4}&\frac{79}{8}&-\frac{105}{2}\cr &&&\frac{1}{8}&-\frac{7}{4}&\frac{275}{16}\cr &&&&\frac{1}{16}&-\frac{7}{8}\cr &&&&&\frac{1}{32}\cr}&\matrix{│\cr│\cr│\cr│}&\matrix{1&&&\cr&1&&\cr&&1&\cr&&&1}}\right]\) 得到左上角矩陣\(\widehat{M}\) \(\widehat{M}=\left[\matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}\cr &\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}\cr &&-\frac{35}{4}&\frac{245}{4}&-\frac{2765}{8}&-\frac{3675}{2}\cr &&&-\frac{35}{8}&\frac{245}{4}&-\frac{9625}{16}\cr &&&&-\frac{1225}{16}&-\frac{8575}{8}\cr &&&&&-\frac{1225}{32}}\right]\) \(\displaystyle det(\widehat{M})=1\cdot \frac{1}{2}\cdot \frac{-35}{4}\cdot \frac{-35}{8}\cdot \frac{-1225}{16}\cdot \frac{-1225}{35}\) \(\displaystyle =2^{-15}35^6\) \(\widehat{M}\)乘32倍變成整數 \(\widehat{M}=\left[\matrix{ 32&0&-152&1064&-6726&42028\cr &16&-112&708&-4424&27605\cr &&-280&1960&-11060&58800\cr &&&-140&1960&-19250\cr &0&&&-2450&34300\cr &&&&&-1225}\right]\) |
步驟4：經LLL化簡和Gram-Schmidt正交化後得到不需要同餘\(N\)的方程式 | |
| 矩陣\(\widehat{M}\)經LLL化簡為\(B\) \(B=LLL(\widehat{M})\) 矩陣\(B\)經Gram-Schmidt正交化得到\(B^{*}\) \(B^{*}=\)Gram-Schmidt\((B)\) －－－－－－－－－－－－－－－－－－－ 引理1： 假設lattice \(L\)經LLL化簡後向量為\(b_1,b_2,\ldots,b_n\)，經Gram-Schmidt化簡後向量為\(b_1^{*},b_2^{*},\ldots,b_n^{*}\)，則\(\displaystyle \Vert\;b_n^{*}\Vert\;\ge det(L)^{\frac{1}{n}}2^{-\frac{n-1}{4}}\)。 [證明] \(\displaystyle det(L)^2=\prod_{i=1}^n \Vert\;b_i^{*}\Vert\;^2=\Vert\;b_1^{*}\Vert\;^2 \Vert\;b_2^{*}\Vert\;^2\cdot \Vert\;b_n^{*}\Vert\;^2\) 經LLL化簡後向量長度滿足\(\Vert\;b_i^{*}\Vert\;^2\le 2\Vert\;b_{i+1}^{*}\Vert\;^2\) \((i=1,2,\ldots,n-1)\) \(\displaystyle det(L)^2 \le \left(2^{n-1}\Vert\;b_n^{*}\Vert\;^2\right)\left(2^{n-2}\Vert\;b_n^{*}\Vert\;^2\right)\ldots \left(\Vert\;b_n^{*}\Vert\;^2\right)\left(\Vert\;b_n^{*}\Vert\;^2\right)\) \(\displaystyle det(L)^2 \le 2^{\frac{n(n-1)}{2}}\Vert\;b_n^{*}\Vert\;^{2n}\) \(\displaystyle \Vert\;b_n^{*}\Vert\;^{2n}\ge det(L)^2 2^{-\frac{n(n-1)}{2}}\) 兩邊各加上\(\displaystyle \frac{1}{2n}\)次方\(\Vert\;b_n^{*}\Vert\;\ge det(L)^{\frac{1}{n}}2^{-\frac{n-1}{4}}\) 引理2： 假設lattice \(L\)其中一個元素\(s\)滿足\(\displaystyle det(L)^{\frac{1}{n}}2^{-\frac{n-1}{4}}>\Vert\;s\Vert\;\)，則\(s\)會落在由\(b_1,b_2,\ldots,b_{n-1}\)所展開的超平面上。 [證明] 將lattice 元素\(s\)表示成\(b_1,b_2,\ldots,b_n\)的線性組合\(\displaystyle s=\sum_{i=1}^n a_ib_i\)，其中\(a_i\)是整數 向量長度\(\Vert\;s\Vert\;=\Vert\;a_1b_1+a_2b_2+\ldots+a_nb_n\Vert\;\ge \Vert\;a_nb_n\Vert\;=|\;a_n|\;\Vert\;b_n\Vert\;\ge |\;a_n|\;\Vert\;b_n^{*}\Vert\;\) 由引理1可知\(\Vert\;b_n^{*}\Vert\;\ge det(L)^{\frac{1}{n}}2^{-\frac{n-1}{4}}\)、\(\displaystyle det(L)^{\frac{1}{n}}2^{-\frac{n-1}{4}}>\Vert\;s\Vert\;\)和 \(\Vert\;s\Vert\;\ge |\;a_n|\;\Vert\;b_n^{*}\Vert\;\)，得到\(\Vert\;b_n^{*}\Vert\;>|\;a_n|\;\Vert\;b_n^{*}\Vert\;\)，\(a_n=0\) \(s\)可表示成\(b_1,b_2,\ldots,b_{n-1}\)的線性組合，\(s\)落在由\(b_1,b_2,\ldots,b_{n-1}\)所展開的超平面上。 －－－－－－－－－－－－－－－－－－－ \(\displaystyle s=\left[1,\delta \frac{x_0}{X},\ldots,\delta\left(\frac{x_0}{X}\right)^{hk-1}\right]\)是lattice\(\widehat{M}\)的向量元素， 由步驟3結論可知\(\displaystyle det(\widehat{M})^{\frac{1}{n}}2^{-\frac{n-1}{4}}>\Vert\;s\Vert\;\) 由上面引理2可知\(s\)落在由\(b_1,b_2,\ldots,b_{n-1}\)所展開的超平面上。 而這個超平面會和Gram-Schmidt的向量\(b_n^{*}\)正交，得到\(s\cdot b_n^{*}=0\)，可得到一個不需要同餘\(N\)的方程式。 | LLL化簡 \(B=\left[\matrix{0&160&0&-60&0&-100\cr -64&-64&-88&80&-72&-51\cr 64&-48&32&4&-180&16\cr 128&-80&-48&16&116&-13\cr -32&-96&-16&-132&90&-108\cr -64&-32&248&96&-30&-141}\right]\) Gram-Schmidt正交化 \(B^{*}=\left[\matrix{\displaystyle 0&160&0&-60&0&-100\cr -64&-\frac{164}{7}&-88&\frac{907}{14}&-72&-\frac{1069}{14}\cr \frac{4327744}{55201}&-\frac{213712}{55201}&\frac{2859392}{55201}&-\frac{1388192}{55201}&-\frac{9041940}{55201}&\frac{490976}{55201}\cr \frac{2396089600}{17933807}&-\frac{673016640}{17933807}&-\frac{1044380280}{17933807}&\frac{154688960}{17933807}&\frac{745216000}{17933807}&-\frac{1169640000}{17933807}\cr -\frac{2184694400}{45963969}&-\frac{1521655800}{15321323}&\frac{344724800}{15321323}&-\frac{6338718400}{45963969}&\frac{172362400}{45963969}&-\frac{1166905600}{15321323}\cr -\frac{117600}{17929}&-\frac{627200}{17929}&\frac{3763200}{17929}&\frac{2508800}{17929}&\frac{627200}{17929}&-\frac{2508800}{17929}}\right]\) 取最後一列向量乘上\(\displaystyle \frac{17929}{39200}\)變成整數 \([−3, −16, 96, 64, 16, −64]\) 形成不需要再同餘\(N\)的方程式 \(\displaystyle h(x)=-3-16\left(\frac{x}{2}\right)+96\left(\frac{x}{2}\right)^2+64\left(\frac{x}{2}\right)^3+16\left(\frac{x}{2}\right)^4-64\left(\frac{x}{2}\right)^5\) \(=-3-8x+24x^2+8x^3+x^4-2x^5\) \(=-(x-3)(2x-1)(x^3+3x^2+5x+1)\) 解方程式得到答案 \(x=3\) |
方法 | 範例 |
步驟1：計算參數\(h\)和\(X\)(和Coppersmith相同) | |
步驟2：產生矩陣\(M\)(和Coppersmith相同) | |
步驟3：矩陣\(M\)基本列運算得到\(\widehat{M}\)，計算\([r(x)H_1^{-1}]_{sh}\) | |
| 因為\(p(x)\)為monic(最高次方項係數為1)，在矩陣\(A\)的對角線元素為1，進行基本列運算將右上角化簡為零，右下角化簡為零，再將對角線元素為1的一整列移到整個矩陣下方。 \(\widetilde{M}=H_1M=\left[\matrix{\widehat{M}&│&0_{(hk\times (h-1)k)}\cr ―&┼&――――――\cr A'&│&I_{(h-1)k}}\right]\) 得到左上角矩陣\(\widehat{M}\) 計算矩陣\(H_1^{-1}=M\widetilde{M}^{-1}\) \(r(x)=[1,x_0,x_0^2,x_0^3,x_0^4,x_0^5,-y_0,-x_0y_0,-y_0^2,-x_0y_0^2]\) 又\(p(x_0)\equiv 0\pmod{N}\)，\(p(x_0)=y_0N\)，\(\displaystyle y_0=\frac{p(x_0)}{N}\) \(\displaystyle r(x)=[1,x_0,x_0^2,x_0^3,x_0^4,x_0^5,-\frac{p(x_0)}{N},-\frac{x_0p(x_0)}{N},-\frac{p^2(x_0)}{N},-\frac{x_0p^2(x_0)}{N}]\) 計算\(\displaystyle p(x_0)H_1^{-1}\) 將後面的0刪除\(\displaystyle [p(x_0)H_1^{-1}]_{sh}\) | \(H_1^{-1}=M\widetilde{M}^{-1}=\left[\matrix{ 1&&&&&&19&0&361&0\cr &1&&&&&14&19&532&361\cr &&&&&&1&14&234&532\cr &&&&&&&1&28&234\cr &&&&&&&&1&28\cr &&&&&&&&&1\cr &&1&&&&35&&&\cr &&&1&&&&35&&\cr &&&&1&&&&1225&\cr &&&&&1&&&&1225} \right]\) \(\displaystyle r(x)=(1,x,x^2,x^3,x^4,x^5,-\frac{p(x)}{35},-\frac{xp(x)}{35},-\frac{p^2(x)}{35^2},-\frac{xp^2(x)}{35^2})\) \(r(x)H_1^{-1}=(1,x,-\frac{p(x)}{35},-\frac{xp(x)}{35},-\frac{p^2(x)}{35^2},-\frac{xp^2(x)}{35^2},\) \(19+14x+x^2-p(x),\) \(19x+14x^2+x^3-xp(x),\) \(361+532x+234x^2+28x^3+x^4-p^2(x),\) \(361x+532x^2+234x^3+28x^4+x^5-xp^2(x))\) \(r(x)H_1^{-1}=(1,x,-\frac{p(x)}{35},-\frac{xp(x)}{35},-\frac{p^2(x)}{35^2},-\frac{xp^2(x)}{35^2},0,0,0,0)\) \(\left[r(x)H_1^{-1}\right]_{sh}=(1,x,-\frac{p(x)}{35},-\frac{xp(x)}{35},-\frac{p^2(x)}{35^2},-\frac{xp^2(x)}{35^2})\) |
步驟4：經LLL化簡和計算矩陣\(H_2^{-1}\)得到不需要同餘\(N\)的方程式 | |
| \(B_2=LLL(\widehat{M})\) 計算\(B_2=H_2\widehat{M}\)，\(H_2^{-1}=\widehat{M}B_2^{-1}\) \(r'_{hk}(x)=[r(x)H_1^{-1}]_{sh}\cdot ((H_2^{-1})_{hk})^T\) 解出\(x\) | \(\widehat{M}=\left[\matrix{ 32&0&-152&1064&-6726&42028\cr &16&-112&708&-4424&27605\cr &&-280&1960&-11060&58800\cr &&&-140&1960&-19250\cr &0&&&-2450&34300\cr &&&&&-1225}\right]\) \(B=LLL(\widehat{M})=\left[\matrix{0&160&0&-60&0&-100\cr -64&-64&-88&80&-72&-51\cr 64&-48&32&4&-180&16\cr 128&-80&-48&16&116&-13\cr -32&-96&-16&-132&90&-108\cr -64&-32&248&96&-30&-141}\right]\) \(H_2^{-1}=\widehat{M}B_2^{-1}=\left[\matrix{-166&-125&-9&-111&-73&-70\cr -109&-82&-6&-73&-48&-46\cr -231&-171&-7&-157&-104&-98\cr 77&60&8&50&32&32\cr -138&-109&-18&-88&-56&-57\cr 5&4&1&3&2&2}\right]\) \(((H_2^{-1})_{6})^T=\left[-70,-46,-98,32,-57,2\right]\) \(\displaystyle [r(x)H_1^{-1}]_{sh}\cdot ((H_2^{-1})_6)^T=-70\cdot 1-46x+98\frac{p(x)}{35}-32\frac{xp(x)}{35}+57\frac{p^2(x)}{35^2}-2\frac{xp^2(x)}{35^2}\) \(\displaystyle h(x)=\frac{-1}{1225}(2x^5-x^4-8x^3-24x^2+8x+3)\) \(\displaystyle =\frac{-1}{1225}(x-3)(2x-1)(x^3+3x^2+5x+1)\) 解方程式得到答案 \(x=3\) |
方法 | 範例 |
問題敘述 | |
| 設同餘方程式為\(p(x)=x^k+a_{k-1}x^{k-1}+\ldots+a_1 x+a_0\equiv 0 \pmod{N}\) 且\(p(x)\)為monic(最高次方項係數為1)且不可分解。 利用LLL方法可以找出比邊界\(X\)還小的解\(x_0\)(\(\displaystyle |\;x_0|\;<X\)) 使得\(p(x_0)\equiv 0 \pmod{N}\) | 設同餘方程式為\(p(x)=x^2+14x+19\equiv 0\pmod{35}\) 且\(p(x)\)為monic(最高次方項係數為1)且不可分解。 利用LLL方法可以找出比邊界\(X\)還小的解 使得\(p(x_0)\equiv 0 \pmod{35}\) |
步驟1：計算參數\(h\)和\(X\) | |
| \(h\ge 2\) \(\displaystyle X=\lceil\;2^{-\frac{1}{2}}(hk)^{-\frac{1}{hk-1}}N^{\frac{h-1}{hk-1}}\rceil\;-1\) | \(h=3\) \(k=2\) \(X=\lceil\;2^{-\frac{1}{2}}\cdot 6^{-\frac{1}{5}}\cdot 35^{\frac{2}{5}}\rceil\;-1=\lceil\;2.0487\rceil\;-1=3-1=2\) |
步驟2：產生矩陣\(M\) | |
| 定義三角\((hk)\times(hk)\)矩陣\(M=(m_{i,j})\)，\(m_{i,j}=e_{i,j}X^{j-1}\) \(e_{i,j}\)是\(q_{u,v}(x)=N^{(h-1-v)}x^u(p(x))^v\)的\(\displaystyle x^{j-1}\)項係數 其中\(\displaystyle v=\lfloor\;\frac{i-1}{k}\rfloor\;\)和\(u=(i-1)-kv\) 注意到對所有\(u,v\ge 0\)，\(q_{u,v}(x_0)\equiv 0\pmod{N^{h-1}}\) －－－－－－－－－－－－－－－－－－－－－－－ 以\(h=3,k=2\)為例計算\(det(M)\) \(M=\left[\matrix{N^2&&&&&\cr 0&N^2X^1&&&&\cr *&*&NX^2&&&\cr 0&*&*&NX^3&&\cr *&*&*&*&X^4&\cr 0&*&*&*&*&X^5}\right]\) *代表非零數字 因為\(M\)為下三角矩陣，行列式值為對角線元素相乘 \(det(M)=(N^2\cdot N^2X^1)\cdot (NX^2\cdot NX^3)\cdot(X^4\cdot X^5)\) \(=X^{0+1+2+3+4+5}N^{2(2+1+0)}\) \(=X^{15}N^6\) －－－－－－－－－－－－－－－－－－－－－－－ 有上面的經驗改計算\(det(M)\)的一般式 維度\((hk)\times(hk)\)矩陣\(M\)的對角線元素為 \(\displaystyle [(N^{h-1},N^{h-1}X^1,\ldots,N^{h-1}X^{k-1}),\)有\(k\)個 \(\displaystyle (N^{h-2}X^k,N^{h-2},X^{k+1},\ldots,N^{h-2}X^{2k-1}),\)有\(k\)個 ⋯ \(\displaystyle (X^{hk-k},\ldots,X^{hk-1})]\)有\(k\)個 因為\(M\)為下三角矩陣，行列式值為對角線元素相乘 \(det(M)=X^{0+1+\ldots+(hk-1)}N^{k[(h-1)+(h-2)+\ldots+0]}\) \(=X^{\frac{hk(hk-1)}{2}}N^{\frac{hk(h-1)}{2}}\) | \(i=1\)，\(\displaystyle v=\lfloor\;\frac{1-1}{2}\rfloor\;=0\)，\(u=(1-1)-2\cdot 0=0\) \(q_{0,0}(x)=N^{3-1-0}x^0(x^2+14x+19)^0=1225\) \(i=2\)，\(\displaystyle v=\lfloor\;\frac{2-1}{2}\rfloor\;=0\)，\(u=(2-1)-2\cdot 0=1\) \(q_{1,0}(x)=N^{3-1-0}x^1(x^2+14x+19)^0=1225x\) \(i=3\)，\(\displaystyle v=\lfloor\;\frac{3-1}{2}\rfloor\;=1\)，\(u=(3-1)-2\cdot 1=0\) \(q_{0,1}(x)=N^{3-1-1}x^0(x^2+14x+19)^1=665+490x+35x^2\) \(i=4\)，\(\displaystyle v=\lfloor\;\frac{4-1}{2}\rfloor\;=1\)，\(u=(4-1)-2\cdot 1=1\) \(q_{1,1}(x)=N^{3-1-1}x^1(x^2+14x+19)^1=665x+490x^2+35x^3\) \(i=5\)，\(\displaystyle v=\lfloor\;\frac{5-1}{2}\rfloor\;=2\)，\(u=(5-1)-2\cdot 2=0\) \(q_{0,2}(x)=N^{3-1-2}x^0(x^2+14x+19)^2=361+532x+234x^2+28x^3+x^4\) \(i=6\)，\(\displaystyle v=\lfloor\;\frac{6-1}{2}\rfloor\;=2\)，\(u=(6-1)-2\cdot 2=1\) \(q_{1,2}(x)=N^{3-1-2}x^1(x^2+14x+19)^2=361x+532x^2+234x^3+28x^4+x^5\) \(m_{i,j}=e_{i,j}X^{j-1}\)，\(x^{j-1}\)次方係數乘上\(2^{j-1}\) 常數項 1次方 2次方 3次方 4次方 5次方 \(M=\matrix{q_{0,0}(x)\cr q_{1,0}(x)\cr q_{0,1}(x)\cr q_{1,1}(x)\cr q_{0,2}(x)\cr q_{1,2}(x)}\left[\matrix{1225&&&&0&\cr 0&1225\times 2&&&&\cr 665&490\times 2&35\times 2^2&&&\cr 0&665\times 2&490\times 2^2&35\times 2^3&&\cr 361&532\times 2&234 \times 2^2&28\times 2^3&2^4&\cr 0&361\times 2&532\times 2^2&234\times 2^3&28\times 2^4&2^5} \right]\) \(det(M)=2^{15}35^6\) |
步驟3：經LLL化簡後的短向量產生不需要同餘\(N^{h-1}\)的方程式 | |
| 矩陣\(M\)經LLL化簡為\(B\) \(B=LLL(M)\) lattice經LLL化簡後第一行\(b_1\)為整個lattice中較短向量 所形成的方程式不需要再同餘\(N\) －－－－－－－－－－－－－－－－－－－ 設\(B\)是矩陣\(M\)經LLL化簡後的矩陣，矩陣\(B\)的第一列短向量\(b_1\) 從\(\displaystyle det(M)=X^{\frac{hk(hk-1)}{2}}N^{\frac{hk(h-1)}{2}}\)和引理\(\Vert\;b_1\Vert\;\le 2^{(n-1)/4}\cdot (det(L))^{1/n}\) 得知\(\Vert\;b_1\Vert\;\le 2^{\frac{hk-1}{4}}X^{\frac{hk-1}{2}}N^{\frac{h-1}{2}}\) 設整數向量\(c\)，長度為\(n\)，\((c\in Z^n)\) \(b_1=cM\)，其中\(\displaystyle b_{1,j}=\sum_{i=1}^{hk}c_im_{i,j}=\sum_{i=1}^{hk}c_ie_{i,j}X^{j-1}\) \([b_{1,1},b_{1,2},\ldots,b_{1,hk}]=[c_1,c_2,\ldots,c_{hk}]\left[\matrix{m_{1,1}&m_{1,2}&\ldots&m_{1,hk}\cr m_{2,1}&m_{2,2}&\ldots&m_{2,hk}\cr \vdots&\vdots&&\vdots\cr m_{hk,1}&m_{hk,2}&\ldots&m_{hk,hk}}\right]\) \([b_{1,1},b_{1,2},\ldots,b_{1,hk}]=[c_1,c_2,\ldots,c_{hk}]\left[\matrix{e_{1,1}&e_{1,2}X&\ldots&e_{1,hk}X^{hk-1}\cr e_{2,1}&e_{2,2}X&\ldots&e_{2,hk}X^{hk-1}\cr \vdots&\vdots&&\vdots\cr e_{hk,1}&e_{hk,2}X&\ldots&e_{hk,hk}X^{hk-1}}\right]\) 設向量長度\(\displaystyle \Vert\;b_1\Vert\;_2=\sqrt{\sum_{j=1}^{hk} b_{1j}^2}\)，\(\displaystyle \Vert\;b_1\Vert\;_1=\sum_{j=1}^{hk} |\;b_{1j}|\;\) https://en.wikipedia.org/wiki/Norm_(mathematics) \(\displaystyle \Vert\;b_1\Vert\;_2\ge \frac{1}{\sqrt{hk}}\Vert\;b_1\Vert\;_1\) \(\displaystyle =\frac{1}{\sqrt{hk}}\left(\Bigg|\sum_{i=1}^{hk}c_i m_{i,1}\Bigg|+\Bigg|\sum_{i=1}^{hk}c_i m_{i,2}\Bigg|+\ldots+\Bigg|\sum_{i=1}^{hk}c_i m_{i,hk}\Bigg|\right)\) \(\displaystyle =\frac{1}{\sqrt{hk}}\left(\Bigg|\sum_{i=1}^{hk}c_i e_{i,1}\Bigg|+\Bigg|\left(\sum_{i=1}^{hk}c_i e_{i,2}\right)X\Bigg|+\ldots+\Bigg|\left(\sum_{i=1}^{hk}c_i e_{i,hk}\right)X^{hk-1}\Bigg|\right)\) \(\displaystyle \ge \frac{1}{\sqrt{hk}}|\;r(x)|\;\)對所有\(|\;x|\;\le X\) 其中\(\displaystyle r(x)=\sum_{i}^{hk}c_ie_{i,1}+\left(\sum_{i=1}^{hk}c_i e_{i,2}\right)x+\ldots+\left(\sum_{i=1}^{hk}c_i e_{i,hk}\right)x^{hk-1}\) 從\(\displaystyle \frac{1}{\sqrt{hk}}|\;r(x)|\;\le \Vert\;b_1\Vert\;\)，\(\Vert\;b_1\Vert\;\le 2^{\frac{hk-1}{4}}X^{\frac{hk-1}{2}}N^{\frac{h-1}{2}}\) 得到\(\displaystyle |\;r(x)|\;\le \left(2^{\frac{hk-1}{4}}\sqrt{hk}\right)X^{\frac{hk-1}{2}}X^{\frac{h-1}{2}}\) 選擇\(\displaystyle X=\lceil\;\left(2^{-\frac{1}{2}}(hk)^{-\frac{1}{hk-1}}\right)N^{\frac{h-1}{hk-1}}\rceil\;-1\)，\(\displaystyle X^{\frac{hk-1}{2}}<2^{-\frac{hk-1}{4}}(hk)^{-\frac{1}{2}}N^{\frac{h-1}{2}}\) \(\displaystyle |\;r(x)|\;\le\left(2^{\frac{hk-1}{4}}\sqrt{hk}\right)\left(2^{-\frac{hk-1}{4}}(hk)^{-\frac{1}{2}}N^{\frac{h-1}{2}}\right)N^{\frac{h-1}{2}}=N^{h-1}\) 原本要解同餘方程式\(r(x)\equiv 0\pmod{N^{h-1}}\)，對所有\(|\;x|\;<X\)，\(|\;r(x)|\;<N^{h-1}\) 變成解一般方程式\(r(x)=0\) | LLL化簡 \(B=LLL(M)=\left[\matrix{3&8\times 2&-24\times 2^2&-8 \times 2^3&-1\times 2^4&2\times 2^5\cr 49&50\times 2&0&20\times 2^3&0&2\times 2^5\cr 115&-83\times 2&4\times 2^2&13\times 2^3&6\times 2^4&2\times 2^5\cr 61&16\times 2&37\times 2^2&-16\times 2^3&3\times 2^4&4\times 2^5\cr 21&-37\times 2&-14\times 2^2&2\times 2^3&14\times 2^4&-4\times 2^5\cr -201&4\times 2&33\times 2^2&-4\times 2^3&-3\times 2^4&1\times 2^5} \right]\) 取第一列向量形成不需要再同餘\(N^{h-1}\)的方程式 \(\displaystyle r(x)=3+8\times 2\left(\frac{x}{2}\right)-24\times 2^2\left(\frac{x}{2}\right)^2-8\times 2^3\left(\frac{x}{2}\right)^3-1\times 2^4\left(\frac{x}{2}\right)^4+2\times 2^5\left(\frac{x}{2}\right)^5\) \(=3+8x-24x^2-8x^3-x^4+2x^5\) \(=(x-3)(2x-1)(x^3+3x^2+5x+1)\) 解方程式得到答案 \(x=3\) －－－－－－－－－－－－－－－－－－－ \(b_1=[\matrix{3&16&-96&-64&-16&64}]\) \(c=[\matrix{70&46&-98&32&-57&2}]\) \((m_{i,j})=\left[\matrix{1225&&&&&\cr 0&2450&&&&\cr 665&980&140&&&\cr 0&1330&1960&280&&\cr 361&1064&936&224&16&\cr 0&722&2128&1872&448&32}\right]\) \((e_{i,j}X^{j-1})=\left[\matrix{1225&&&&&\cr 0&1225\times 2&&&&\cr 665&490\times 2&35\times 2^2&&&\cr 0&665\times 2&490\times 2^2&35\times 2^3&&\cr 361&532\times 2&234\times 2^2&28\times 2^3&2^4&\cr 0&361\times 2&532\times 2^2&234\times 2^3&28\times 2^4& 2^5}\right]\) |
| 修正前 | 修正後 |
| h:3$ k:3$ N:10^150$ X:ceiling(2^(-1/2)*(h*k)^(-1/(h*k-1))*N^((h-1)/(h*k-1)))-1; 16990442448471225139289591175253590015錯誤 | h:3$ k:3$ N:10^150$ fpprec:100$/*設定小數點以下100為有效位數*/ X:ceiling(bfloat(2^(-1/2)*(h*k)^(-1/(h*k-1))*N^((h-1)/(h*k-1))))-1; 16990442448471225207917914988908164235正確 |
公式 | 範例 |
| 設\(f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0\)和 \(g(x)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_0\) 是次數為\(n\)和\(m\)的多項式 設\(f(x)\)和\(g(x)\)的Sylvester矩陣為 \(Syl(f,g)=\left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr 0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&a_n&a_{n-1}&\ldots&a_0\cr b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr 0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&b_m&b_{m-1}&\ldots&b_0}\right] \matrix{ \cr \cr f(x)取m列\cr \cr \cr \cr g(x)取n列\cr }\) 則\(f(x)\)和\(g(x)\)的Resultant為Sylvester矩陣的行列式值 \(Res(f,g)=det(Syl(f,g))\) \(Res(f,g)=\left|\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr 0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&a_n&a_{n-1}&\ldots&a_0\cr b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr 0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&b_m&b_{m-1}&\ldots&b_0}\right|\) | \(f(x)=1x^3+2x^2+3x+4\) \(g(x)=5x^2+6x+7\) \(f(x)\)和\(g(x)\)的Sylvester矩陣為 \(Syl(f,g)=\left[\ \matrix{1&2 &3 &4 &0\cr 0 &1&2 &3 &4 \cr 5&6&7&0&0 \cr 0&5&6&7&0 \cr 0&0&5&6&7} \right] \matrix{f(x)取2列\cr \cr \cr g(x)取3列 \cr }\) \(f(x)\)和\(g(x)\)的Resultant為 \(Res(f,g)= \left|\ \matrix{1&2 &3 &4 &0\cr 0 &1&2 &3 &4 \cr 5&6&7&0&0 \cr 0&5&6&7&0 \cr 0&0&5&6&7} \right|=832 \) 超過3階行列式不能用交叉相乘方式計算，而降階方式計算量又太大，實務上可採用PA=LU分解，再個別計算矩陣\(P,L,U\)的行列式值，\(det(P)\cdot det(A)=det(L)\cdot det(U)\)，進而得到矩陣\(A\)的行列式值。 參考資料：https://ccjou.wordpress.com/2012/04/13/palu-%E5%88%86%E8%A7%A3/ \(P=\left[ \matrix{1&0&0&0&0\cr 0&1&0&0&0\cr 0&0&0&1&0\cr 0&0&1&0&0\cr 0&0&0&0&1}\right]\)，\(det(P)=-1\) \(L=\left[ \matrix{\displaystyle 1&0&0&0&0\cr 0&1&0&0&0\cr 0&5&1&0&0\cr 5&-4&0&1&0\cr 0&0&-\frac{5}{4}&\frac{1}{2}&1}\right]\)，\(det(L)=1\cdot 1\cdot 1\cdot 1\cdot 1=1\) \(U=\left[ \matrix{1&2&3&4&0\cr 0&1&2&3&4\cr 0&0&-4&-8&-20\cr 0&0&0&-8&16\cr 0&0&0&0&-26}\right]\)，\(det(U)=1\cdot 1\cdot (-4)\cdot(-8)\cdot(-26)=-832\) \(\displaystyle Res(f,g)=\frac{det(L)\cdot det(U)}{det(P)}=\frac{1\cdot (-832)}{-1}=832\) |
| 判斷是否有共同根 若\(Res(f,g)=0\)，則\(f,g\)有共同根 [證明] 設\(x=x_0\)是\(f(x)=0,g(x)=0\)的共同根，則\(f(x_0)=g(x_0)=0\) \(\left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr 0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&a_n&a_{n-1}&\ldots&a_0\cr b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr 0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&b_m&b_{m-1}&\ldots&b_0}\right] \left[\matrix{x_0^{n+m-1}\cr x_0^{n+m-2}\cr \vdots \cr x_0^n \cr x_0^{n-1}\cr \vdots \cr x_0 \cr 1}\right]=\left[\matrix{f(x_0)x_0^{m-1}\cr f(x_0)x_0^{m-2}\cr \vdots \cr f(x_0)x_0 \cr f(x_0)\cr g(x_0)x_0^{n-1} \cr g(x_0)x_0^{n-2}\cr \vdots \cr g(x_0)x_0 \cr g(x_0)} \right]=0\) \(Syl(f,g)x=0\)是齊次方程組 若\(x\)有非0解，則\(Syl(f,g)\)的行列式值要為0，得到 \(Res(f,g)=\left|\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr 0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&a_n&a_{n-1}&\ldots&a_0\cr b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr 0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&b_m&b_{m-1}&\ldots&b_0}\right|=0\) | \(f(x)=(x^2-1)(x^2+x+2)=x^4+x^3+x^2-x-2\) \(g(x)=(x^2-1)(x^3+x^2+x-1)=x^5+x^4-2x^2-x+1\)有共同根 設\(x=x_0\)是\(f(x)=0,g(x)=0\)的共同根，則\(f(x_0)=g(x_0)=0\) \(\left[\matrix{1&1&1&-1&-2&0&0&0&0\cr 0&1&1&1&-1&-2&0&0&0\cr 0&0&1&1&1&-1&-2&0&0\cr 0&0&0&1&1&1&-1&-2&0\cr 0&0&0&0&1&1&1&-1&-2\cr 1&1&0&-2&-1&1&0&0&0\cr 0&1&1&0&-2&-1&1&0&0\cr 0&0&1&1&0&-2&-1&1&0\cr 0&0&0&1&1&0&-2&-1&1}\right] \left[\matrix{x_0^8\cr x_0^7\cr x_0^6\cr x_0^5\cr x_0^4\cr x_0^3\cr x_0^2\cr x_0^1\cr 1} \right]= \left[\matrix{f(x_0)\cdot x_0^4\cr f(x_0)\cdot x_0^3\cr f(x_0)\cdot x_0^2\cr f(x_0)\cdot x_0\cr f(x_0)\cr g(x_0)\cdot x_0^3\cr g(x_0)\cdot x_0^2\cr g(x_0)\cdot x_0\cr g(x_0)} \right]=0\) \(Syl(f,g)x=0\)是齊次方程組 若\(x\)有非0解，則\(Syl(f,g)\)的行列式值要為0，得到 \(Res(f,g)=\left|\ \matrix{1&1&1&-1&-2&0&0&0&0\cr 0&1&1&1&-1&-2&0&0&0\cr 0&0&1&1&1&-1&-2&0&0\cr 0&0&0&1&1&1&-1&-2&0\cr 0&0&0&0&1&1&1&-1&-2\cr 1&1&0&-2&-1&1&0&0&0\cr 0&1&1&0&-2&-1&1&0&0\cr 0&0&1&1&0&-2&-1&1&0\cr 0&0&0&1&1&0&-2&-1&1}\right|=0\) |
| 兩變數方項式消除共同變數 \(f(x,y)=0,g(x,y)=0\)為兩變數方程式，已知\(f(x)\)和\(g(x)\)有共同根，可利用Resultant消除共同變數 | 設\(f(x,y)=x^2y^2-25x^2+9=0\) \(g(x,y)=4x+y=0\) 若要消去\(x\)變數，先以\(x\)為變數降冪排列 \(f(x,y)=(y^2-25)x^2+0x+9\)，\(g(x,y)=4x+y\) 計算\(f(x,y)\)和\(g(x,y)\)的Resultant \(Res_x(f,g)=\left|\ \matrix{y^2-25&0&9 \cr 4&y&0 \cr 0&4&y} \right|\ =y^4-25y^2+144=0\) 解得\(y=\pm 3,\pm 4\)，代回\(g(x,y)=0\) 得\(\displaystyle (x,y)=(1,-4),(-1,4),(\frac{3}{4},-3),(-\frac{3}{4},3)\) 若要消去\(y\)變數，先以\(y\)為變數降冪排列 \(f(x,y)=x^2y^2+0y+(-25x^2+9),g(x,y)=y+4x\) 計算\(f(x,y)\)和\(g(x,y)\)的Resultant \(Res_y(f,g)=\left|\ \matrix{x^2&0&-25x^2+9 \cr 1&4x&0 \cr 0&1&4x} \right|\ =16x^4-25x^2+9=0 \) 解得\(\displaystyle x=\pm \frac{3}{4},\pm 1\)，代回\(g(x,y)=0\) 得\(\displaystyle (x,y)=(1,-4),(-1,4),(\frac{3}{4},-3),(-\frac{3}{4},3)\) 範例出處 http://buzzard.ups.edu/courses/2 ... ts-ups-434-2016.pdf |
方法 | 範例 |
問題敘述 | |
| 相同的明文\(m\)，為明文加上隨機補綴值後加密成\(k\)個密文\(c_i\)。 其中\(\displaystyle \alpha<\frac{k-2}{6k-3}<\frac{1}{6}\)，\(\displaystyle |\; t_i|\;\le \frac{1}{2}N^{\alpha}\) \(A_0\equiv m^3\pmod N\)，第0個直接三次方不加補綴 \(A_i\equiv (m+t_i)^3 \pmod N\)，第\(i\)個加上補綴後三次方 \(c_i\equiv A_i-A_0\equiv 3m^2t_i+3mt_i^2+t_i^3 \pmod N\)，第\(i\)個減第0個得到密文\(c_i\) 已知\(c_i,N\)，則透過Coppersmith方法可以回復補綴值\(t_i\)和明文\(m\)。 | 明文\(m=25152118001609140014150009191379\) 公鑰\(N=54957464841358314276864542898551\) 出自Cryptanalytic Attacks on RSA \(k=4\)，\(\displaystyle \alpha=\frac{1}{11}\)，\(\displaystyle \alpha<\frac{4-2}{6\cdot 4-3}<\frac{1}{6}\) \(t_1=761,t_2=683,t_3=714,t_4=756\) 其中\(t_1,t_2\)為質數，可以解出明文\(m\) 但\(t_3=2\cdot 3 \cdot 7\cdot 17,t_4=2^2\cdot 3^3 \cdot 7\)可以分解成小質數乘積，反而無法解出明文\(m\) \(A_0\equiv m^3 \equiv 37393323096087665763922106857101\pmod{N}\) \(A_1\equiv (m+761)^3\equiv 21904263018805857488488858542023\pmod{N}\) \(A_2\equiv (m+683)^3\equiv 37153632560891277497054197384710\pmod{N}\) \(A_3\equiv (m+714)^3\equiv 18092792378564256587234068711460\pmod{N}\) \(A_4\equiv (m+756)^3\equiv 39662861356261303674301781451309\pmod{N}\) 密文 \(c_1\equiv A_1-A_0\equiv 39468404764076506001431294583473\pmod{N}\) \(c_2\equiv A_2-A_0\equiv 54717774306161926009996633426160\pmod{N}\) \(c_3\equiv A_3-A_0\equiv 35656934123834905100176504752910\pmod{N}\) \(c_4\equiv A_4-A_0\equiv 2269538260173637910379674594208\pmod{N}\) |
步驟1：利用恆等式建立矩陣\(M\)的右上角區塊 | |
| 設下標\(i<j<l\)，定義\(d_{ij}=t_i t_j(t_i-t_j)\)，\(e_{ijl}=-t_it_jt_l(t_i-t_j)(t_j-t_l)(t_l-t_i)\) \(\displaystyle C_2^k\)個線性獨立數量\(d_{ij}\)滿足\(|\;d_{ij}|\;<N^{3\alpha}\) \(\displaystyle C_3^k\)個線性獨立數量\(e_{ijl}\)滿足\(|\;e_{ijl}|\;<N^{6\alpha}\) 滿足恆等式\(d_{ij}c_l+d_{jl}c_i-d_{il}c_j\equiv e_{ijl}\pmod{N}\) 右上角\(C_2^k\times C_3^k\)區塊為 以數對\((i,j),i<j\)決定哪一列，以數對\((i,j,l),i<j<l\)決定哪一行 第\((i,j,l)\)行，第\(\displaystyle(i,j)=\frac{1}{2}(2k-i)(i-1)+j-i\)列放\(c_l\) 第\((i,j,l)\)行，第\(\displaystyle(j,l)=\frac{1}{2}(2k-j)(j-1)+l-j\)列放\(c_i\) 第\((i,j,l)\)行，第\(\displaystyle(i,l)=\frac{1}{2}(2k-i)(i-1)+l-i\)列放\(-c_j\) －－－－－－－－－－－－－－－－－－－－－－ 數對\((i,j)\)在第\(\displaystyle \frac{1}{2}(2k-i)(i-1)+j-i\)列 [證明] \(\matrix{d_{12}&d_{13}&d_{14}&&\ldots&&d_{1k}&k-1個\cr &d_{23}&d_{24}&&&&d_{2k}&k-2個\cr &&&\ldots&&&&\cr &&&d_{i-1,i}&\ldots&&d_{i-1,k}&k-i+1個\cr &&&&d_{i,i+1}&\ldots&d_{i,j}&j-i個}\) \((i,j)=(k-1)+(k-2)+\ldots+(k-i+1)+(j-1)\) \(\displaystyle =\frac{1}{2}(k-1+k-i+1)(i-1)+(j-i)\) \(\displaystyle =\frac{1}{2}(2k-i)(i-1)+j-i\) | \((1,2,3)\)，\(d_{12}c_3+d_{23}c_1-d_{13}c_2\equiv e_{123}\pmod{N}\) \((1,2,4)\)，\(d_{12}c_4+d_{24}c_1-d_{14}c_2\equiv e_{124}\pmod{N}\) \((1,3,4)\)，\(d_{13}c_4+d_{34}c_1-d_{14}c_3\equiv e_{134}\pmod{N}\) \((2,3,4)\)，\(d_{23}c_4+d_{34}c_2-d_{24}c_3\equiv e_{234}\pmod{N}\) 寫成矩陣形式 \(\left[\matrix{d_{12}& d_{13}& d_{14}& d_{23}& d_{24}& d_{34}}\right] \left[\matrix{c_3&c_4&&\cr -c_2&&c_4&\cr &-c_2&-c_3&\cr c_1&&&c_4\cr &c_1&&-c_3\cr &&c_1&c_2}\right]\equiv \left[\matrix{e_{123}\cr e_{124}\cr e_{134}\cr e_{234}}\right]\pmod{N}\) 第1行 第\(\displaystyle(1,2)=\frac{1}{2}(2\times4-1)(1-1)+2-1=1\)列放\(c_3\) 第\(\displaystyle(2,3)=\frac{1}{2}(2\times4-2)(2-1)+3-2=4\)列放\(c_1\) 第\(\displaystyle(1,3)=\frac{1}{2}(2\times4-1)(1-1)+3-1=2\)列放\(-c_2\) 第2行 第\(\displaystyle(1,2)=\frac{1}{2}(2\times4-1)(1-1)+2-1=1\)列放\(c_4\) 第\(\displaystyle(2,4)=\frac{1}{2}(2\times4-2)(2-1)+4-2=5\)列放\(c_1\) 第\(\displaystyle(1,4)=\frac{1}{2}(2\times4-1)(1-1)+4-1=3\)列放\(-c_2\) 第3行 第\(\displaystyle(1,3)=\frac{1}{2}(2\times4-1)(1-1)+3-1=2\)列放\(c_4\) 第\(\displaystyle(3,4)=\frac{1}{2}(2\times4-3)(3-1)+4-3=6\)列放\(c_1\) 第\(\displaystyle(1,4)=\frac{1}{2}(2\times4-1)(1-1)+4-1=3\)列放\(-c_3\) 第4行 第\(\displaystyle(2,3)=\frac{1}{2}(2\times4-2)(2-1)+3-2=4\)列放\(c_4\) 第\(\displaystyle(3,4)=\frac{1}{2}(2\times4-3)(3-1)+4-3=6\)列放\(c_2\) 第\(\displaystyle(2,4)=\frac{1}{2}(2\times4-2)(2-1)+4-2=5\)列放\(-c_3\) |
步驟2：建立矩陣\(M\)，利用LLL找到較短的\(s\)向量 | |
| 矩陣\(M\)為\(C_2^k+C_2^k\)大小的方陣， 左上角\(C_2^k\times C_2^k\)區塊為單位矩陣乘上近似\(N^{3\alpha}\)的整數值。 左下角\(C_3^k\times C_2^k\)區塊為\(0\)矩陣。 右下角\(C_3^k\times C_3^k\)區塊為單位矩陣乘上\(N\)。 右上角\(C_2^k\times C_3^k\)區塊為步驟1的係數矩陣 －－－－－－－－－－－－－－－－－－－－－－ 設列向量\(r\)前\(C_2^k\)個元是\(d_{ij}\)，後\(C_3^k\)個元是\(\displaystyle \frac{e_{ijl}-(d_{ij}c_l+d_{jl}c_i-d_{il}c_j)}{N}\) 計算\(rM=s\) 列向量\(s\)前\(C_2^k\)個元是\(d_{ij}N^{3\alpha}\)，後\(C_3^k\)個元是\(e_{ijl}\)，每個元都小於\(N^{6\alpha}\) 希望透過lattice化簡演算法找到這一列向量。 因為矩陣\(M\)為上三角矩陣，行列式值為對角線\(C_2^k\)個\(N^{3\alpha}\)和\(C_3^k\)個\(N\)相乘 \(\displaystyle det(M)=N^{3\alpha C_2^k+C_3^k}\)，因為\(\displaystyle \alpha<\frac{k-2}{6k-2}\)，所以還會大於\(\displaystyle (N^{6\alpha})^{C_2^k+C_3^k}\) 所以\(s\)是由矩陣\(M\)個列向量所產生的較短向量，找到\(s\)的難度取決於它在短元素中的rank，若\(|\;t_i|\;\)足夠小於\(N^{\alpha}\)，然後我們希望\(s\)是整個lattice中最短元素，透過lattice化簡演算法能有效地回復\(s\)。我們在這裡不提供效率估計或成功機率，將這個方法視為啟發式攻擊(不一定100%成功)。 －－－－－－－－－－－－－－－－－－－－－－ 當\(\displaystyle \alpha<\frac{k-2}{6k-2}\)時，\(3\alpha C_2^k+C_3^k>6\alpha(C_2^k+C_3^k)\) [證明] \((3\alpha C_2^k+C_3^k)-6\alpha(C_2^k+C_3^k)\) \(=(1-6\alpha)C_3^k-3\alpha C_2^k\) \(\displaystyle =(1-6\alpha)\left[\frac{k(k-1)(k-2)}{6}-\frac{k(k-1)}{2}\right]\) \(\displaystyle =\frac{k(k-1)}{2}\left[(1-6\alpha)\frac{k-2}{3}-3\alpha \right]\) \(\displaystyle \frac{k(k-1)}{2}>0\)為正，還需要\(\displaystyle (1-6\alpha)\frac{k-2}{3}-3\alpha>0\)亦為正 \(\displaystyle \frac{1-6\alpha}{\alpha}>\frac{9}{k-2}\) \(\displaystyle \frac{1}{\alpha}-6>\frac{9}{k-2}\) \(\displaystyle \frac{1}{\alpha}>\frac{9}{k-2}+\frac{6k-12}{k-2}=\frac{6k-3}{k-2}\) \(\displaystyle \alpha<\frac{k-2}{6k-3}\)就是當初的條件 步驟可以逆推回去 | \(M=\left[\matrix{N^{3\alpha}&&&&&&c_3&c_4&&\cr &N^{3\alpha}&&&&&-c_2&&c_4&\cr &&N^{3\alpha}&&&&&-c_2&-c_3&\cr &&&N^{3\alpha}&&&c_1&&&c_4\cr &&&&N^{3\alpha}&&&c_1&&-c_3\cr &&&&&N^{3\alpha}&&&c_1&c_2\cr &&&&&&N&&&\cr &&0&&&&&N&&\cr &&&&&&&&N&\cr &&&&&&&&&N}\right]\) \(r=[\displaystyle d_{12},d_{13},d_{14},d_{23},d_{24},d_{34},\) \(\displaystyle \frac{e_{123}-(d_{12}c_3+d_{23}c_1-d_{13}c_2)}{N},\) \(\displaystyle \frac{e_{124}-(d_{12}c_4+d_{24}c_1-d_{14}c_2)}{N},\) \(\displaystyle \frac{e_{134}-(d_{13}c_4+d_{34}c_1-d_{14}c_3)}{N},\) \(\displaystyle \frac{e_{234}-(d_{23}c_4+d_{34}c_2-d_{24}c_3)}{N}]\) 計算\(rM=s\) \(s=[d_{12}N^{3\alpha},d_{13}N^{3\alpha},d_{14}N^{3\alpha},d_{23}N^{3\alpha},d_{24}N^{3\alpha},d_{34}N^{3\alpha},\) \(e_{123},e_{124},e_{134},e_{234}]\) 利用lattice化簡演算法找到短向量\(s\)，若真的找到\(s\)，從\(r=sM^{-1}\)得到\(r\)向量。 |
步驟3：再用Franklin和Reiter的技巧回復明文\(m\) | |
| 利用\(r\)向量計算最大公因數來回復\(t_i\) \(gcd(d_{1,2},d_{1,3},\ldots,d_{1,k})=gcd\{\;t_1t_2(t_1-t_2),t_1t_3(t_1-t_3),\ldots,t_1t_k(t_1-t_k) \}\;\) \(=t_1\times gcd\{\; t_2(t_1-t_2),t_3(t_1-t_3),\ldots,t_k(t_1-t_k) \}\;\) 希望後面的gcd足夠小而可以暴力搜尋找到\(t_i\)，再用Franklin和Reiter的技巧回復明文\(m\)。 \(c_1\equiv 3m^2t_1+3mt_1^2+t_1^3\pmod{N}\) \(c_2\equiv 3m^2t_2+3mt_2^2+t_2^3\pmod{N}\) \(\displaystyle m \equiv -\frac{t_1t_2^3+(c_1-t_1^3)t_2-c_2t_1}{3t_1t_2^2-3t_1^2t_2}\pmod{N}\) | 計算\(gcd(r_1,r_2,r_3)\)得到\(t_1\) 計算\(gcd(r_1,r_4,r_5)\)得到\(t_2\) 計算\(gcd(r_2,r_4,r_6)\)得到\(t_3\) 計算\(gcd(r_3,r_5,r_6)\)得到\(t_4\) 再用Franklin和Reiter的技巧回復明文\(m\) |
RSA \(n=pq\) | RSA \(n=p^rq\) |
產生公鑰和私鑰 | |
| 產生兩個隨機質數\(p,q\)，\(n=pq\) 計算\(\phi(n)=(p-1)(q-1)\) 找\(e,d\)符合\(ed\equiv 1 \pmod{\phi(n)}\)和\(GCD(e,p)=1\) \(e,n\)是公鑰，\(d,p,q\)是私鑰 | 產生兩個隨機質數\(p,q\)，\(n=p^r q\) 計算\(L=LCM(p-1.q-1)\) 找\(e,d\)符合\(ed \equiv 1\pmod{L}\)和\(GCD(e,p)=1\) \(e,n\)是公鑰，\(d,p,q\)是私鑰 |
加密 | |
| \(c\equiv m^e \pmod{n}\) \(m\)為明文，\(c\)為密文 | 相同 |
解密 | |
| \(m\equiv c^d \pmod{n}\) | 無法使用\(m\equiv c^d \pmod{n}\)來回復明文 |
利用中國餘數定理快速解密 | |
| \(m\equiv c^d \pmod{pq}\) 分解成\(m_p\equiv c^d \pmod{p}\)，\(m_q\equiv c^d\pmod{q}\) 設\(d_p\equiv d\pmod{p-1}\)，\(m_p\equiv c^{d_p}\pmod{p}\) 設\(d_q\equiv d\pmod{q-1}\)，\(m_q\equiv c^{d_q}\pmod{q}\) 利用中國餘數定理 \(m\equiv \left(m_p\cdot q(q^{-1}\pmod{p})+m_q\cdot p(p^{-1}\pmod{q})\right)\pmod{n}\) | \(m_q\equiv c^d\pmod{q}\) 設\(d_q\equiv d\pmod{q-1}\)，\(m_q\equiv c^{d_q}\pmod{q}\) 利用中國餘數定理 \(m\equiv (m_p\cdot q(q^{-1}\pmod{p^r})+m_q\cdot p^r(p^{-r}\pmod{q}))\pmod{n}\) \(m_p\equiv m\pmod{p^r}\)的\(m_p\)無法用\(m_p\equiv c^d\pmod{p^r}\)直接計算，改用以下的方法計算\(m_p\) |
| \(L=LCM(p-1,q-1)\) \(d\equiv e^{-1}\pmod{L}\) | \(\phi(n)=p^{r-1}(p-1)(q-1)\) \(d\equiv e^{-1}\pmod{\phi(n)}\) | \(\lambda(n)=LCM(p^{r-1}(p-1),(q-1))\) \(d\equiv e^{-1}\pmod{\lambda(n)}\) |
| \(L=LCM(60,52)=780\) \(d\equiv 17^{-1}\equiv 413\pmod{L}\) 私鑰\(d\)較小，但不能直接計算\(m\equiv c^d \pmod{n}\)來回復明文，改用以下的中國餘數定理來加速解密。 | \(\phi(n)=61^2\cdot 60\cdot 52=11609520\) \(d\equiv 17^{-1}\equiv 682913\pmod{\phi(n)}\) 雖然可以直接計算\(m\equiv c^d \pmod{n}\)來回復明文， 但解密速度會比\(n=pq\)且使用中國餘數定理的RSA還慢，變成使用\(n=p^rq\)的RSA沒有顯著的優點。 | \(\lambda(n)=LCM(61^2\cdot 60,52)=2902380\) \(d\equiv 17^{-1}\equiv 682913\pmod{\lambda(n)}\) 雖然可以直接計算\(m\equiv c^d \pmod{n}\)來回復明文， 但解密速度會比\(n=pq\)且使用中國餘數定理的RSA還慢，變成使用\(n=p^rq\)的RSA沒有顯著的優點。 |
虛擬碼 | 範例 |
\(A_i=K_0+pK_1+p^2K_2+\ldots+p^{i-1}K_{i-1}\)改成遞迴關係式\(A_{i+1}=A_i+p^iK_i\) \(F_i=(A_i)^e\pmod{p^{i+1}}\) 計算\(\displaystyle K_{i}\equiv \frac{(c_p-F_i)(eF_i)^{-1}A_i}{p^i}\pmod{p^{i+1}}\)，\(i=1,2,\ldots,r-1\) 分解成 \(E_i=c-F_i\pmod{p^{i+1}}\) \(\displaystyle B_i=\frac{E_i}{p^i}\) \(K_i=[(eF_i)^{-1}A_iB_i]\pmod{p}\) －－－－－－－－－－－－－－－－ 解密 輸入：\(d,p,q,e,r,c\) 輸出：\(m\) (1) \(d_p=d\pmod{p-1}\) \(d_q=d\pmod{q-1}\) (2) \(K_0=c^{d_p}\pmod{p}\) \(m_q=c^{d_q}\pmod{q}\) (3) \(A_1=K_0\) for \(i=1\) to \((r-1)\) do \(F_i=A_i^e \pmod{p^{i+1}}\) \(E_i=(c-F_i)\pmod{p^{i+1}}\) \(\displaystyle B_i=\frac{E_i}{p^i}\)為整數 \(K_i=[(eF_i)^{-1}A_iB_i]\pmod{p}\) \(A_{i+1}=A_i+p^iK_i\)為整數 (4) \(m_p=A_r\) (5) \(p_1=[(p^r)^{-1}]\pmod{q}\) \(q_1=[q^{-1}]\pmod{p^r}\) (6) \(m=[q_1qm_p+p_1p^rm_q]\pmod{p^rq}\) | 輸入：\(d=413\)，\(p=61\)，\(q=53\)，\(e=17\)，\(r=3\)，\(c=10259995\) 輸出：\(m=1234567\) (1)\(d_p\equiv 413\pmod{60}\equiv 53\) \(d_q\equiv 413\pmod{52}\equiv 49\) (2)\(K_0\equiv 10259995^{53}\equiv 49\pmod{61}\) \(m_q\equiv 10259995^{49}\equiv 38\pmod{53}\) (3)\(A_1=49\) 當\(i=1\)時 \(F_1=A_1^e= 49^{17} = 527 \pmod{61 ^2}\) \(E_1=(c-F_1)=(10259995-527)=671 \pmod{61 ^2}\) \(\displaystyle B_1=\frac{E_1}{p}=\frac{671}{61}=11\) \(K_1=(eF_1)^{-1} A_1B_1=( 17 \cdot 527 )^{-1} 49 \cdot 11 = 47 \pmod{61}\) \(A_2=A_1+p \cdot K_1= 49 + 61 \cdot 47 = 2916\) 當\(i=2\)時 \(F_2=A_2^e= 2916^{17}= 57013 \pmod{61^3}\) \(E_2=(c-F_2)=(10259995-57013)= 215818 \pmod{61 ^3}\) \(\displaystyle B_2=\frac{E_2}{p^2}=\frac{215818}{3721}= 58\) \(K_2=(eF_2)^{-1} A_2B_2=( 17 \cdot 57013 )^{-1} 2916 \cdot 58 = 26 \pmod{61}\) \(A_3=A_2+p^2 \cdot K_2= 2916 + 61 ^2 \cdot 26 = 99662\) (4)\(m_p=A_r=99662\) (5)\(p_1\equiv 61^{-3}\equiv 50\pmod{53}\) \(q_1\equiv 53^{-1}\equiv 12848 \pmod{61^3}\) (6)\(m\equiv [12848\cdot 53\cdot 99662+50\cdot 61^3 \cdot 38]\pmod{61^3\cdot 53}\) \(\equiv 1234567 \pmod{61^3\cdot 53}\) |
方法 | 範例 |
問題敘述 | |
| 定理 令\(N=p^rq\)，對某些的\(c\)，\(q<p^c\)。 若已知\(N,r,c\)由執行時間為\(\displaystyle exp\left(\frac{c+1}{r+c}\cdot logp\right)\cdot O(\gamma)\)的演算法能分解出因數\(p\)。 其中\(\gamma\)是矩陣維度\(O(r^2)\)，矩陣元素大小為\(O(\gamma logN)\)執行LLL所需的時間。 這個演算法是決定性的和需要多項式的空間。 [證明] \(N=p^rq\)，對某些的\(c\)，\(q<p^c\) 令\(d=2r(r+c)\)，由引理1可知整數\(P\)滿足\(|\; P-p|\;<p^{1-\frac{c+1}{r+c}}\) 就能在\(O((logN)^2d^4)\)的時間內找到\(N\)的分解。 | \(197213=61^2 \cdot 53\)要找出\(197213\)的因數\(61\) \(N=197213\)，\(r=2\)，\(p=61\)，\(q=53\) 假設\(c=1\)，\(53<61^c\) 矩陣維度\(d=2r(r+c)=2\cdot 2(2+1)=12\) 論文範例取較小的\(d\)值，\(d=9\) |
步驟1：列舉因數\(p\)的近似值\(P\) | |
| 令\(\displaystyle ε=\frac{c+1}{r+c}\) For \(k=1,2,\ldots,\frac{log_2N}{r}\) do For \(j=0,1,\ldots,2^{ε}\) do (設\(P=2^k+j\cdot 2^{(1-ε)k}\) 使用近似的\(P\)，執行引理1的演算法 ) | \( \displaystyle ε=\frac{c+1}{r+c}=\frac{1+1}{2+1}=\frac{2}{3}\) \(\displaystyle k=5,j=9,P=2^5+9*2^{(1-2/3)5}=59\) 取\(P=59\)當作因數\(p\)的近似值 |
| 引理1： 給定\(N=p^r q\)和假設\(q<p^c\)對某些\(c\)，更進一步假設\(P\)是符合\(\displaystyle |\; P-p|\;<p^{1-\frac{c}{r+c}-2\frac{r}{d}}\)的整數 從\(N,r,c\)和\(P\)使用維度\(d\)的lattice執行LLL方法，能計算出因數\(p\)。 | |
步驟2.設同餘方程式，計算參數\(X\) | |
| 設同餘方程式為\(f(x)=(P+x)^r\equiv 0 \pmod{p^r}\) 且\(p(x)\)為monic(最高次方項係數為1)。 利用LLL方法可以找出比邊界\(X\)還小的解\(x_0=p-P\)(\(\displaystyle |\;x_0|\;<X\)) 使得\(f(x_0)\equiv 0 \pmod{p^r}\)，進而得到公鑰\(N\)的一個因數\(p=P+x_0\)。 | \(f(x)=(35+x)^2 \equiv 0\pmod{p^2}\) \(\displaystyle X=p^{1-\frac{c+1}{r+c}}=p^{1-ε}\) 因為\(p\)未知，假設\(p,q\)相近，\(\displaystyle N=p^rq\approx p^{r+1}\)，\(\displaystyle p\approx N^{\frac{1}{r+1}}\) \(\displaystyle X\approx N^{\frac{1-ε}{r+1}}= N^{\frac{1-2/3}{2+1}}=197213^{\frac{1}{9}}\approx 3.875\) 取\(X=3\) |
步驟3.產生矩陣\(M\) | |
| \(g_{i,k}(xX)=N^{m-k}(xX)^i f(xX)^k\) \(g_{i,k}(xX)\)，\(i=0,1,\ldots,r-1\)和\(k=0,1,\ldots,m-1\) \(g_{j,m}(xX)\)，\(j=0,1,\ldots,d-mr-1\) 注意到對所有\(i,k\)，\(g_{i,k}(x_0)\equiv 0\pmod{p^{rm}}\) [證明] \(g_{i,k}(x_0)=N^{m-k}(x_0X)^i(P+x_0)^{rk}\) \(=(p^rq)^{m-k}(x_0X)^i(p)^{rk}\) \(=p^{rm}(q^{m-k}(x_0X)^i)\) \(\equiv 0\pmod{p^{rm}}\) 注意到對所有\(j,m\)，\(g_{j,m}(x_0)\equiv 0\pmod{p^{rm}}\) [證明] \(g_{j,m}(x_0)=N^{m-m}(x_0X)^j(P+x_0)^{rm}\) \(=(x_0X)^jp^{rm}\) \(\equiv 0\pmod{p^{rm}}\) 將\(g_{i,k}(xX),g_{j,m}(xX)\)多項式依\(x\)次方形成係數矩陣\(M\)。 令\(M\)是\(L\)的基底向量所形成的矩陣，注意到\(M\)為下三角矩陣，所以\(L\)的行列式值為\(M\)的對角線元素相乘，得到 \(\displaystyle det(M)=\left(\prod_{k=0}^{m-1}\prod_{i=0}^{r-1}N^{m-k}\right)\left(\prod_{j=0}^{d-1}X^j\right)\) \(\displaystyle =\left(\prod_{i=0}^{r-1}N^m\cdot N^{m-1}\ldots N^1\right) \cdot (X^0 \cdot X^1 \ldots X^{d-1})\) \(\displaystyle =\left(\prod_{i=0}^{r-1}N^{m(m+1)/2}\right)X^{d(d-1)/2}\) \(\displaystyle =N^{rm(m+1)/2}X^{d(d-1)/2}\) \(\displaystyle <N^{rm(m+1)/2}X^{d^2/2}\) | \(r=2\) \(\displaystyle m=\lfloor\; \frac{d}{r+c}-\frac{1}{2} \rfloor\;=\lfloor\; \frac{12}{2+1}-\frac{1}{2} \rfloor\;=3\) \(d=9\) 產生\(g_{i,k}(xX)\)多項式 \(i=0,k=0,g_{0,0}(xX)=N^3(xX)^0f(xX)^0=\)\(\bbox[border:1px solid black]{N^3}\) \(i=1,k=0,g_{1,0}(xX)=N^3(xX)^1f(xX)^0=\)\(\bbox[border:1px solid black]{N^3X}x\) \(i=0,k=1,g_{0,1}(xX)=N^2(xX)^0f(xX)^1=N^2(P+Xx)^2\) \(=N^2P^2+2N^2PXx+\)\(\bbox[border:1px solid black]{N^2X^2}x^2\) \(i=1,k=1,g_{1,1}(xX)=N^2(xX)^1f(xX)^1=N^2Xx(P+Xx)^2\) \(=N^2P^2Xx+2N^2PX^2x^2+\bbox[border:1px solid black]{N^2X^3}x^3\) \(i=0,k=2,g_{0,2}(xX)=N(xX)^0f(xX)^2=N(P+Xx)^4\) \(=NP^4+4NP^3Xx+6NP^2X^2x^2+4NPX^3x^3+\bbox[border:1px solid black]{NX^4}x^4\) \(i=1,k=2,g_{1,2}(xX)=N(xX)^1f(xX)^2=NXx(P+Xx)^4\) \(=NP^4Xx+4NP^3X^2x^2+6NP^2X^3x^3+4NPX^4x^4+\bbox[border:1px solid black]{NX^5}x^5\) 產生\(g_{j,m}(xX)\)多項式 \(j=0,g_{0,3}(xX)=(xX)^0f(xX)^3=(P+Xx)^6\) \(=P^6+6P^5Xx+15P^4X^2x^2+20P^3X^3x^3+15P^2X^4x^4+6PX^5x^5+\bbox[border:1px solid black]{X^6}x^6\) \(j=1,g_{1,3}(xX)=(xX)f(xX)^3=Xx(P+Xx)^6\) \(=P^6Xx+6P^5X^2x^2+15P^4X^3x^3+20P^3X^4x^4+15P^2X^5x^5+6PX^6x^6+\bbox[border:1px solid black]{X^7}x^7\) \(j=2,g_{2,3}(xX)=(xX)^2f(xX)^3=X^2x^2(P+Xx)^6\) \(=P^6X^2x^2+6P^5X^3x^3+15P^4X^4x^4+20P^3X^5x^5+15P^2X^6x^6+6PX^7x^7+\bbox[border:1px solid black]{X^8}x^8\) |
| \(M=\matrix{&\matrix{1 &x &x^2 &x^3& x^4 & x^5& x^6& x^7& x^8}\cr \matrix{g_{0,0}(xX)\cr g_{1,0}(xX)\cr g_{0,1}(xX)\cr g_{1,1}(xX)\cr g_{0,2}(xX)\cr g_{1,2}(xX)\cr g_{0,3}(xX)\cr g_{1,3}(xX)\cr g_{2,3}(xX)}&\left[\matrix{N^3&&&&&&&&\cr 0&XN^3&&&&&&&\cr *&*&X^2N^2&&&&&&\cr 0&*&*&X^3N^2&&&&&\cr *&*&*&*&X^4N&&&&\cr 0&*&*&*&*&X^5N&&&\cr *&*&*&*&*&*&X^6&&\cr 0&*&*&*&*&*&*&X^7&\cr 0&0&*&*&*&*&*&*&X^8}\right]}\) *代表非零數字 \(det(M)=N^3 \cdot XN^3 \cdot X^2N^2\cdot X^3N^2\cdot X^4N\cdot X^5N\cdot X^6\cdot X^7\cdot X^8\) \(=N^{2\cdot(3+2+1)}X^{0+1+2+\ldots+7+8}\) \(=N^{12}X^{36}\) | |
步驟4.經LLL化簡後的短向量產生不需要同餘\(p^{rm}\)的方程式，得到公鑰\(N\)的因數\(p\) | |
| 矩陣\(M\)經LLL化簡為\(B\) \(B=LLL(M)\) lattice經LLL化簡後第一行\(b_1\)為整個lattice中較短向量 所形成的方程式不需要再同餘\(p^{rm}\) －－－－－－－－－－－－－－－－－－－ 令\(h(x)\in Z[x]\)是次方為\(n\)的多項式，假設 (1)\(h(x_0)\equiv 0\pmod{p^{rm}}\)，\(r,m\)為正整數，\(|\;x_0|\;<X\) (2)\(\displaystyle \Vert\;h(xX)\Vert\;<\frac{p^{rm}}{\sqrt{d}}\) 則在整數下\(h(x_0)=0\)。 [證明] \(\displaystyle |\;h(x_0)|\;=|\;\sum a_ix_0^i|\;=|\;\sum a_i X^i \left(\frac{x_0}{X}\right)^i|\;\) \(\displaystyle \le \sum |\;a_iX^i \left(\frac{x_0}{X}\right)^i|\;\le \sum |\;a_i X^i|\;\) \(\le \sqrt{d} \Vert\;h(xX)\Vert\;<p^{rm}\) 因為\(h(x_0)\equiv 0\pmod{p^{rm}}\)，所以\(h(x_0)=0\) －－－－－－－－－－－－－－－－－－－ 向量\(b_1\)是由多項式\(g_{i,k}(xX)\)係數的線性組合而成\(h(xX)\)，\(\Vert\;b_1 \Vert\;=\Vert\;h(xX) \Vert\;\) \(h(x)\)也會是多項式\(g_{i,k}(x)\)的線性組合，因為\(g_{i,k}(x_0)\equiv 0\pmod{p^{rm}}\)，所以\(h(x_0)\equiv 0\pmod{p^{rm}}\) 假設lattice \(L\)經LLL化簡後向量\(b_1,b_2,\ldots,b_n\)，則\(\Vert\;b_1 \Vert\;\le 2^{(n-1)/4}\cdot(det(L))^{1/n}\)。 證明在https://math.pro/db/viewthread.php?tid=3498&page=1#pid23067 論文將\(2^{(n-1)/4}\)改成\(2^{d/2}\)，\(d\)為lattice矩陣維度 \(\Vert\;b_1 \Vert\;\le 2^{d/2}\cdot(det(L))^{1/d}\) \(\Vert\;b_1 \Vert\;^d\le 2^{d^2/2}\cdot det(L)\) 將行列式值\( det(L)<N^{rm(m+1)/2}X^{d^2/2}\)代入得到 \(\Vert\;b_1 \Vert\;^d\le 2^{d^2/2}N^{rm(m+1)/2}X^{d^2/2}\) 向量\(b_1\)是某個\(h(xX)\)多項式的係數向量，滿足\(\Vert\;b_1 \Vert\;=\Vert\;h(xX) \Vert\;\) 更進一步，因為\(h(xX)\)是\(g_{i,k}(xX)\)多項式的線性組合， 所以\(h(x)\)也是\(g_{i,k}(x)\)多項式的線性組合 將\(\Vert\;b_1 \Vert\;=\Vert\;h(xX) \Vert\;\)代入 \(\Vert\;h(xX) \Vert\;^d\le 2^{d^2/2}\cdot N^{rm(m+1)/2}X^{d^2/2}\) 若\(\displaystyle \Vert\;h(xX)\Vert\;<\frac{p^{rm}}{\sqrt{d}}\)，分母的\(\sqrt{d}\)在接下來計算中影響較小，為了簡化就忽略了。 \(\displaystyle \Vert\;h(xX)\Vert\;^d\le 2^{d^2/2}\cdot N^{rm(m+1)/2}X^{d^2/2}<p^{rmd}\) \((2X)^{d^2/2}<p^{rmd}N^{-rm(m+1)/2}\) 假設對某個\(c\)，\(q<p^c\)，\(N=p^rq<p^{r+c}\) \((2X)^{d^2/2}<p^{rmd}p^{-r(r+c)m(m+1)/2}\) \((2X)^{d^2/2}<p^{rmd-r(r+c)m(m+1)/2}\) 為了讓\(X\)值越大越好，可以取較弱的近似\(P\)值 利用配方法求\(p\)的最大次方\(rmd-r(r+c)m(m+1)/2\) \(\displaystyle =rmd-\frac{r}{2}(r+c)m(m+1)\) \(\displaystyle =-\frac{r}{2}\left[(r+c)m^2+(r+c-2d)m\right]\) \(\displaystyle =-\frac{r}{2}(r+c)\left(m^2+\frac{r+c-2d}{r+c}m\right)\) \(\displaystyle =-\frac{r}{2}(r+c)\left(m+\frac{r+c-2d}{2(r+c)}\right)^2+\frac{r}{2}(r+c)\left(\frac{r+c-2d}{2(r+c)}\right)^2\) \(\displaystyle =\frac{r}{2}(r+c)\left(m+\frac{1}{2}-\frac{d}{r+c}\right)^2+\frac{r}{2}(r+c)\left(\frac{r+c-2d}{2(r+c)}\right)^2\) \(m\)的最佳值在\(\displaystyle m_0=\lfloor\; \frac{d}{r+c}-\frac{1}{2} \rfloor\;\) 我們也許能選\(d_0\)使得\(\displaystyle \frac{d_0}{r+c}-\frac{1}{2}\)在\(\displaystyle \frac{1}{2r+c}\)的整數範圍內。 將\(m=m_0\)和\(d=d_0\)代入和繁瑣的計算後得到 \(\displaystyle X<\frac{1}{2}p^{1-\frac{c}{r+c}-\frac{r}{d}(1+\delta)}\)，其中\(\displaystyle \delta=\frac{1}{r+c}-\frac{r+c}{4d}\) 因為\(\delta<1\)我們得到稍微弱但更吸引人的界限 \(\displaystyle X<p^{1-\frac{c}{r+c}-2\frac{r}{d}}\) 令\(d=2r(r+c)\) \(\displaystyle X<p^{1-\frac{c}{r+c}-2\frac{r}{2r(r+c)}}\) \(\displaystyle X<p^{1-\frac{c+1}{r+c}}\) | lattice經LLL化簡後第一行\(b_1\)為整個lattice中較短向量 \(b_1=[83412628,-91271724,-27587799,-100623168,\) \([-100709649,89252928,78155361,202680225,228782070]\) 產生不需要同餘\(p^{rm}\)的方程式 \(\displaystyle h(x)=83412628-91271724 \left(\frac{x}{3}\right)-27587799 \left(\frac{x}{3}\right)^2\) \(\displaystyle-100623168 \left(\frac{x}{3}\right)^3-100709649 \left(\frac{x}{3}\right)^4+89252928 \left(\frac{x}{3}\right)^5\) \(\displaystyle+78155361\left(\frac{x}{3}\right)^6+202680225\left(\frac{x}{3}\right)^7+228782070 \left(\frac{x}{3}\right)^8\) \(=83412628-30423908x-3065311x^2-3726784x^3\) \(-1243329x^4+367296x^5+107209x^6+92675x^7+34870x^8\) \(=(-2+x)^2(20853157+13247180x+7267563x^2+\) \(3024072x^3+896349x^4+232155x^5+34870x^6)\) 得到整數解\(x=2\) 得到因數\(p=P+x=59+2=61\) \(N\)可分解成\(197213=61^2 \cdot 53\) |
| 歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) | 論壇程式使用 Discuz! 6.1.0 |