17 12

# 用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|\; 步驟4.計算邊界\(X$$的範圍

$$=\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|$$

$$\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|$$

$$\displaystyle =\frac{N^{d+1}X^{\frac{d(d+1)}{2}}}{d+1}$$

https://en.wikipedia.org/wiki/Le ... reduction_algorithm

$$\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

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

(%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$$

(%i5)　X:floor(N^(2/(d*(d+1))));
(X)　$$7$$

(%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*/

(%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]$$

(%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]$$

(%i11)　hx:sum(b1[i+1]/X^i*x^i,i,0,d);
(hx)　$$x^3-96x^2+1953x-9310$$

(%i12)　factor(hx);
(%o12)　$$(x-70)(x-19)(x-7)$$

(%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  bugmens 發私訊 加為好友 目前離線 2# 大 中 小 發表於 2021-5-10 16:40 只看該作者 使用低次方公鑰$$e$$的RSA傳送線性相關訊息是不安全的，傳送超過$$\displaystyle \frac{e(e+1)}{2}$$個加密訊息能讓破解者回復原本的訊息。 設使用低次方公鑰$$e=3$$，原本訊息$$m$$，在訊息後面串接加密時間$$TimeStamp_i$$當作補綴，計算3次方後同餘$$n_i$$得到密文$$Cipertext_i$$。 $$Cipertext_i=(10000m+TimeStamp_i)^3\pmod{n_i}$$ 當破解者收集超過$$\displaystyle \frac{3\cdot 4}{2}=6$$個密文$$Cipertext_i$$、加密時間$$TimeStamp_i$$和公鑰$$n_i$$，利用前一篇文章的方法可以在多項式時間內回復原本的訊息$$m$$。 此時$$\displaystyle n_1>2^{\frac{(e+1)(e+2)}{4}}(e+1)^{(e+1)}$$，$$n=min(n_i)$$，$$n_i\ge n$$ $$\displaystyle N=\prod_{i=1}^k n_i\ge n_1\prod_{i=2}^{\frac{d(d+1)}{2}+1}n_i>2^{\frac{(e+1)(e+2)}{2}}(e+1)^{(e+1)}n^{\frac{d(d+1)}{2}}$$ 破解者收集到7組密文、加密時間和公鑰 $$TimeStamp_1=$$13點40分產生密文$$Cipertext_1=10117$$，公鑰$$n_1=14857$$ $$TimeStamp_2=$$13點47分產生密文$$Cipertext_2=13166$$，公鑰$$n_2=15397$$ $$TimeStamp_3=$$13點56分產生密文$$Cipertext_3=11707$$，公鑰$$n_3=16199$$ $$TimeStamp_4=$$14點09分產生密文$$Cipertext_4=1590$$，公鑰$$n_4=16463$$ $$TimeStamp_5=$$14點18分產生密文$$Cipertext_5=15758$$，公鑰$$n_5=16171$$ $$TimeStamp_6=$$14點20分產生密文$$Cipertext_6=7371$$，公鑰$$n_6=16157$$ $$TimeStamp_7=$$14點24分產生密文$$Cipertext_7=6303$$，公鑰$$n_7=16241$$ 根據密文和加密時間產生多項式 $$f_i(x)=(10000x+TimeStamp_i)^3-Cipertext_i\pmod{n_i}$$ $$f_1(x)=(10000x+1340)^3-10117\equiv-7380x^3+7136x^2-5462x+2733\pmod{14857}$$ $$f_2(x)=(10000x+1347)^3-13166\equiv1351x^3+7316x^2-5044x-847\pmod{15397}$$ $$f_3(x)=(10000x+1356)^3-11707\equiv-4994x^3+4461x^2-2123x-3373\pmod{16199}$$ $$f_4(x)=(10000x+1409)^3-1590\equiv-7473x^3-3954x^2+4418x-1917\pmod{16463}$$ $$f_5(x)=(10000x+1418)^3-15758\equiv-5245x^3-2021x^2-7211x+1009\pmod{16171}$$ $$f_6(x)=(10000x+1420)^3-7371\equiv1554x^3-2117x^2-1884x+1717\pmod{16157}$$ $$f_7(x)=(10000x+1424)^3-6303\equiv4317x^3+441x^2-301x-5633\pmod{16241}$$ $$\displaystyle N=\prod_{i=1}^7 n_i=258865864180238903908838873371$$ $$X=\lfloor\;N^{2/(d(d+1))}\rfloor\;=79832$$ 利用中國餘數定理計算新的方程式係數 將$$f_i(x)$$的常數項係數以中國餘數定理計算新的常數項$$c_0$$ $$c_0\equiv\cases{2733\pmod{14857}\cr -847\pmod{15397}\cr -3373\pmod{16199}\cr -1917\pmod{16463}\cr 1009\pmod{16171}\cr 1717\pmod{16157}\cr -5633\pmod{16241}}$$，$$c_0\equiv 204373190208566474382317165684\pmod{N}$$ 將$$f_i(x)$$的1次方係數以中國餘數定理計算新的1次方係數$$c_1$$ $$c_1\equiv\cases{-5462\pmod{14857}\cr -5044\pmod{15397}\cr -2123\pmod{16199}\cr 4418\pmod{16463}\cr -7211\pmod{16171}\cr -1884\pmod{16157}\cr -301\pmod{16241}}$$，$$c_1\equiv 249751034306884980399002316934\pmod{N}$$ 將$$f_i(x)$$的2次方係數以中國餘數定理計算新的2次方係數$$c_2$$ $$c_2\equiv\cases{7136\pmod{14857}\cr 7316\pmod{15397}\cr 4461\pmod{16199}\cr -3954\pmod{16463}\cr -2021\pmod{16171}\cr -2117\pmod{16157}\cr 441\pmod{16241}}$$，$$c_2\equiv 189008702173331023044971363347\pmod{N}$$ 將$$f_i(x)$$的3次方係數以中國餘數定理計算新的3次方係數$$c_3$$ $$c_3\equiv\cases{-7380\pmod{14857}\cr 1351\pmod{15397}\cr -4994\pmod{16199}\cr -7473\pmod{16463}\cr -5245\pmod{16171}\cr 1554\pmod{16157}\cr 4317\pmod{16241}}$$，$$c_3\equiv 1000000000000\pmod{N}$$ 產生新的同餘方程式$$g(x)\pmod{N}$$，若$$x=x_0$$是$$g(x)\equiv 0\pmod{N}$$解，那$$x=x_0$$也會是$$f_i(x)\equiv 0\pmod{n_i}$$的解 $$g(x)=c_0+c_1x+c_2x^2+c_3x^3\pmod{N}$$ $$=204373190208566474382317165684+249751034306884980399002316934x+189008702173331023044971363347x^2+1000000000000x^3\pmod{N}$$ 產生lattice，希望能找到較小的解$$x=x_0$$$$(x_0 Rabin加密法請參閱wiki。https://en.wikipedia.org/wiki/Rabin_cryptosystem  公式 範例 產生金鑰 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 使用Rabin加密函數傳送線性相關訊息是不安全的，傳送3個加密訊息能讓破解者在多項式時間內回復原本的訊息。 設原本訊息\(m$$，在訊息後面串接加密時間$$TimeStamp_i$$當作補綴，計算2次方後同餘$$n_i$$得到密文$$Cipertext_i$$。 $$Cipertext_i=(10000m+TimeStamp_i)^2\pmod{n_i}$$ 破解者收集到3組密文、加密時間和公鑰 $$TimeStamp_1=$$13點40分產生密文$$Cipertext_1=5926$$，公鑰$$n_1=14857$$ $$TimeStamp_2=$$13點47分產生密文$$Cipertext_2=3031$$，公鑰$$n_2=15397$$ $$TimeStamp_3=$$13點56分產生密文$$Cipertext_3=5421$$，公鑰$$n_3=16199$$ 根據密文和加密時間產生多項式 $$f_i(x)=(10000x+TimeStamp_i)^2-Cipertext_i\pmod{n_i}$$ $$f_1(x)=-2467x^2-2028x+6834\pmod{14857}$$ $$f_2(x)=-3515x^2-4750x-5468\pmod{15397}$$ $$f_3(x)=3573x^2+2874x+2828\pmod{16199}$$ $$\displaystyle N=\prod_{i=1}^3 n_i=3705573556571$$ $$X=\lfloor\;N^{2/(d(d+1))}\rfloor\;=15474$$ 利用中國餘數定理計算新的方程式係數 將$$f_i(x)$$的常數項係數以中國餘數定理計算新的常數項$$c_0$$ $$c_0\equiv\cases{6834\pmod{14857}\cr -5468\pmod{15397}\cr 2828\pmod{16199}}$$，$$c_0\equiv 489114568907 \pmod{N}$$ 將$$f_i(x)$$的1次方係數以中國餘數定理計算新的1次方係數$$c_1$$ $$c_1\equiv\cases{-2028 \pmod{14857}\cr -4750\pmod{15397}\cr 2874\pmod{16199}}$$，$$c_1\equiv 3243065948060 \pmod{N}$$ 將$$f_i(x)$$的2次方係數以中國餘數定理計算新的2次方係數$$c_1$$ $$c_2\equiv\cases{-2467 \pmod{14857}\cr -3515\pmod{15397}\cr 3573\pmod{16199}}$$，$$c_2\equiv 100000000 \pmod{N}$$ 產生新的同餘方程式$$g(x)\pmod{N}$$，若$$x=x_0$$是$$g(x)\equiv 0\pmod{N}$$解，那$$x=x_0$$也會是$$f_i(x)\equiv 0\pmod{n_i}$$的解 $$g(x)=c_0+c_1x+c_2x^2\pmod{N}$$ $$=489114568907+3243065948060x+100000000x^2\pmod{N}$$ 產生lattice，希望能找到較小的解$$x=x_0$$$$(x_0<X=15474)$$ $$B=\left[\matrix{c_0&c_1X&c_2X^2&\frac{1}{d+1}\cr N&0&0&0\cr 0&NX&0&0\cr 0&0&NX^2&0}\right]$$ $$\left[\matrix{489114568907&50183202480280440&23944467600000000&\frac{1}{3}\cr 3705573556571&0&0&0\cr 0&57340045214379654&0&0\cr 0&0&887279859647310765996&0}\right]$$ 經LLL化簡lattice $$B=\left[\matrix{0&0&0&\frac{3705573556571}{3}\cr 3705573556571&0&0&0\cr -705084292305&-1585793949534&3095540771328&\frac{167522755129}{3}\cr 233266894054&-3534864776520&-1757763366516&240304851747}\right]$$ 第1,2列向量都有0，改取第3列向量 $$\displaystyle \vec{b_3}=[-705084292305,-1585793949534,3095540771328,\frac{167522755129}{3}]$$ 化簡後方程式$$h(x)$$不需要同餘$$N$$ $$\displaystyle h(x)=-\frac{705084292305}{X^0}-\frac{1585793949534}{X^1}x+\frac{3095540771328}{X^2}x^2$$ $$\displaystyle =-\frac{705084292305}{15474^0}-\frac{1585793949534}{15474^1}x+\frac{3095540771328}{15474^2}x^2$$ $$=-705084292305-102481191x+12928x^2$$ $$=(x-12345)(12928x+57114969)$$ 得$$x=12345$$ 參考資料 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的解x0。 請下載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 有3個密文 (%i2) Cipertext:[5926,3031,5421]; (Cipertext) $$[5926,3031,5421]$$ 有3個公鑰$$n_i$$ (%i3) n:[14857,15397,16199]; (n) $$[14857,15397,16199]$$ 有3個時戳 (%i4) Timestamp:[1340,1347,1356]; (Timestamp) $$[1340,1347,1356]$$ 同餘方程式最高次方$$d$$ (%i5) d:2; (d) 2 根據密文和時戳產生同餘方程式$$f_i(x)$$ (%i6) fx:create_list(polymod((10000*x+Timestamp[ i ])^3-Cipertext[ i ],n[ i ]),i,1,length(n)); (fx) $$\matrix{[-2467x^2-2028x+6834,\cr -3515x^2-4750x-5468,\cr 3573x^2+2874x+2828]}$$ $$f_i(x)$$的常數項係數 (%i7) a0:create_list(coeff(fx[ i ],x,0),i,1,length(n)); (a0) $$[6834,-5468,2828]$$ $$f_i(x)$$的1次方係數 (%i8) a1:create_list(coeff(fx[ i ],x,1),i,1,length(n)); (a1) $$[-2028,-4750,2874]$$ $$f_i(x)$$的2次方係數 (%i9) a2:create_list(coeff(fx[ i ],x,2),i,1,length(n)); (a2) $$[-2467,-3515,3573]$$ 利用中國餘數定理計算新的常數項$$c_0$$ (%i10) c0:chinese(a0,n); (c0) $$489114568907$$ 利用中國餘數定理計算新的1次方係數$$c_1$$ (%i11) c1:chinese(a1,n); (c1) $$3243065948060$$ 利用中國餘數定理計算新的2次方係數$$c_2$$ (%i12) c2:chinese(a2,n); (c2) $$100000000$$ 產生新的同餘方程式$$g(x)\pmod{N}$$，若$$x=x_0$$是$$g(x)\equiv 0\pmod{N}$$的解，那$$x=x_0$$也會是$$f_i(x)\equiv 0\pmod{n_i}$$的解 (%i13) gx:c0+c1*x+c2*x^2+c3*x^3; (gx) $$100000000x^2+3243065948060x+489114568907$$ $$\displaystyle N=\prod_{i=1}^3 n_i$$ (%i14) N:product(n[ i ],i,1,length(n)); (N) $$3705573556571$$ 希望能找到$$|\;x_0|\;<X=\lfloor\;N^{2/(d(d+1))} \rfloor\;，g(x_0)\equiv 0\pmod{N}$$ (%i15) X:floor(N^(2/(d*(d+1)))); (X) $$15474$$ 定義lattice產生方式 (%i17) 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(gx,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*/ 根據$$g(x)$$係數，產生lattice (%i18) latticeB:genmatrix(genlattice,d+2,d+2); (latticeB) $$\left[\matrix{ 489114568907&50183202480280440&23944467600000000&\frac{1}{3}\cr 3705573556571&0&0&0\cr 0&57340045214379654&0&0\cr 0&0&887279859647310765996&0}\right]$$ 經LLL化簡後的lattice B (%i19) latticeB: LLL(latticeB); (latticeB) $$\left[\matrix{\displaystyle 0&0&0&\frac{3705573556571}{3}\cr 3705573556571&0&0&0\cr -705084292305&-1585793949534&3095540771328&\frac{167522755129}{3}\cr 233266894054&-3534864776520&-1757763366516&240304851747}\right]$$ 第1,2列向量都有0，改取第3列向量 (%i20) b3:latticeB[3]; (b3) $$\displaystyle [-705084292305,-1585793949534,3095540771328,\frac{167522755129}{3}]$$ 化簡後方程式$$h(x)$$不需要同餘$$N$$ (%i21) hx:sum(b2[i+1]/X^i*x^i,i,0,d); (hx) $$12928x^2-102481191x-705084292305$$ 將$$h(x)$$因式分解 (%i22) factor(hx); (%o22) $$(x-12345)(12928x+57114969)$$ 得到較小的解$$x$$ (%i23) x:12345; (x) $$12345$$ 驗證答案$$f_i(12345)\equiv 0 \pmod{n_i}$$ (%i24) create_list(mod(ev(fx[ i ],x=x),n[ i ]),i,1,length(n)); (%o24) $$[0,0,0]$$ TOP  Håstad方法 Coppersmith方法 可以找出比邊界$$X$$還小的解$$x_0$$($$\displaystyle |\;x_0|\; 上面是Håstad和Coppersmith所用的lattice比較表，Håstad僅針對一個方程式\(h(x_0)=sf(x_0)\pmod{N}$$來產生lattice，而Coppersmith增加方程式個數，產生更大的lattice雖然增加LLL執行時間，但能提高解的上界。 $$f(x_0)-y_0N=0$$ $$x_0f(x_0)-x_0y_0N=0$$ $$(f(x_0))^2-y_0^2N^2=0$$ $$x_0(f(x_0))^2-x_0y_0^2N^2=0$$ Coppersmith方法如下：  方法 範例 問題敘述 設同餘方程式為$$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|\;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$$ 參考資料： D. Coppersmith. Finding a small root of a univariate modular equation. In Proceedings of Eurocrypt 1996, volume 1070 of Lecture Notes in Computer Science, pages 155–165. Springer, 1996. https://link.springer.com/chapter/10.1007/3-540-68339-9_14 N. Howgrave-Graham. Finding small roots of univariate modular equations revisited. In Cryptography and Coding– Proc. IMA ’97, volume 1355 of Lecture Notes in Computer Science, pages 131–142. Springer, 1997. https://link.springer.com/chapter/10.1007/BFb0024458 有二次同餘方程式範例 Finding Small Roots of Polynomial Equations Using Lattice Basis Reduction https://ntnuopen.ntnu.no/ntnu-xm ... e=1&isAllowed=y 有三次同餘方程式範例 Lattice Basis Reduction：An Introduction to the LLL Algorithm and Its Applications https://www.routledge.com/Lattic ... /book/9781439807026 有一整章關於Coppersmith方法的介紹 請下載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/share/LLL.mac 要先載入eigen.mac才能使用gramschmidt指令 (%i2) load("eigen.mac"); (%o2) C:/maxima-5.43.2/share/maxima/5.43.2/share/matrix/eigen.mac 要先載入diag.mac才能使用diag指令 (%i3) load("diag.mac"); (%o3) C:/maxima-5.43.2/share/maxima/5.43.2/share/contrib/diag.mac 同餘方程式$$p(x)$$ (%i4) px:x^2+14*x+19; (px) $$x^2+14x+19$$ $$p(x)\equiv 0\pmod{N}$$ (%i5) N:35; (N) $$35$$ $$p(x)$$的次數$$k$$ (%i6) k:hipow(px,x); (k) $$2$$ 設誤差值$$\epsilon=0.1$$ (%i7) epsilon:0.1; (epsilon) $$0.1$$ 參數$$h$$，按照公式應該是$$h=4$$，但$$h=3$$也能算出來 (%i9) h:ceiling(max(7/k,(k+epsilon*k-1)/(epsilon*k^2))); h:3; (h) 4 (h) 3 $$\widehat{M}$$的維度$$n=hk$$ (%i10) n:h*k; (n) 6 參數$$\delta$$，按照公式應該是$$\displaystyle \delta=\frac{1}{\sqrt{6}}$$，改成$$\delta=1$$方便計算 (%i12) delta:1/sqrt(h*k); delta:1; (delta) $$\displaystyle \frac{1}{\sqrt{6}}$$ (delta) 1 希望能找到$$|\;x|\;<X=\frac{1}{2}N^{1/k}$$，$$p(x)\equiv 0\pmod{N}$$ (%i13) X:floor(1/2*N^(1/k)); (X) 2 左上角矩陣對角線元素$$\delta X^{-i}$$ (%i14) Xpower:create_list(delta*X^-(i-1),i,1,h*k); (Xpower) $$\displaystyle \left[1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32}\right]$$ 左上角矩陣 (%i15) D1:diag(Xpower); (D1) $$\left[\matrix{\displaystyle 1&0&0&0&0&0\cr 0&\frac{1}{2}&0&0&0&0\cr 0&0&\frac{1}{4}&0&0&0\cr 0&0&0&\frac{1}{8}&0&0\cr 0&0&0&0&\frac{1}{16}&0\cr 0&0&0&0&0&\frac{1}{32}}\right]$$ 多項式$$x^u\cdot p(x)^v$$ (%i16) xpxpower:create_list(x^u*px^v,v,1,h-1,u,0,k-1); (xpxpower) $$[x^2+14x+19,x(x^2+14x+19),(x^2+14x+19)^2,x(x^2+14x+19)^2]$$ $$x^1,x^2,\ldots,x^{n-1}$$ (%i17) xpower:create_list(x^i,i,1,n-1); (xpower) $$[x,x^2,x^3,x^4,x^5]$$ 取多項式$$x^u\cdot p(x)^v$$係數，形成右上角矩陣(常數項在最後一行) (%i18) A:augcoefmatrix(xpxpower,xpower); (A) $$\left[\matrix{14&1&0&0&0&19\cr 19&14&1&0&0&0\cr 532&234&28&1&0&361\cr 361&532&234&28&1&0}\right]$$ 將常數項移到第一行 (%i19) A:addcol(col(A,h*k),submatrix(A,h*k)); (A) $$\left[ \matrix{ 19&14&1&0&0&0\cr 0&19&14&1&0&0\cr 361&532&234&28&1&0\cr 0&361&532&234&28&1}\right]$$ 矩陣$$A$$轉置 (%i20) A:transpose(A); (A) $$\left[ \matrix{ 19&0&361&0\cr 14&19&532&361\cr 1&14&234&532\cr 0&1&28&234\cr 0&0&1&28\cr 0&0&0&1}\right]$$ 左下角0矩陣 (%i21) Zero:zeromatrix((h-1)*k,h*k); (Zero) $$\left[ \matrix{ 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&0&0&0&0}\right]$$ 右下角矩陣元素$$N^v$$ (%i22) Npower:create_list(N^v,v,1,h-1,u,0,k-1); (Npower) $$[35,35,1225,1225]$$ 右下角矩陣 (%i23) D2:diag(Npower); (D2) $$\left[ \matrix{ 35&0&0&0\cr 0&35&0&0\cr 0&0&1225&0\cr 0&0&0&1225}\right]$$ 4個子矩陣合併成矩陣$$M$$ (%i24) M:addrow(addcol(D1,A),addcol(Zero,D2)); (M) $$\left[ \matrix{\displaystyle 1&0&0&0&0&0&19&0&361&0\cr 0&\frac{1}{2}&0&0&0&0&14&19&532&361\cr 0&0&\frac{1}{4}&0&0&0&1&14&234&532\cr 0&0&0&\frac{1}{8}&0&0&0&1&28&234\cr 0&0&0&0&\frac{1}{16}&0&0&0&1&28\cr 0&0&0&0&0&\frac{1}{32}&0&0&0&1\cr 0&0&0&0&0&0&35&0&0&0\cr 0&0&0&0&0&0&0&35&0&0\cr 0&0&0&0&0&0&0&0&1225&0\cr 0&0&0&0&0&0&0&0&0&1225}\right]$$ 將矩陣$$M$$複製成另一個矩陣$$\widetilde{M}$$，進行矩陣列運算 (%i25) M_tilde:copymatrix(M)$

(%i27)
for i:k+1 thru n do
(for j:1 thru i-1 do
(print("第",j,"列=第",j,"列-",M_tilde[j,i+n-k],"*第",i,"列=",
M_tilde[j]:M_tilde[j]-M_tilde[j,i+n-k]*M_tilde[ i ])
)
)$M_tilde; 第1列=第1列-19*第3列$$\displaystyle =[1,0,-\frac{19}{4},0,0,0,0,-266,-4085,-10108]$$ 第2列=第2列-14*第3列$$\displaystyle =[0,\frac{1}{2},-\frac{7}{2},0,0,0,0,-177,-2744,-7087]$$ 第1列=第1列--266*第4列$$\displaystyle =[1,0,-\frac{19}{4},\frac{133}{4},0,0,0,0,3363,52136]$$ 第2列=第2列--177*第4列$$\displaystyle =[0,\frac{1}{2},-\frac{7}{2},\frac{177}{8},0,0,0,0,2212,34331]$$ 第3列=第3列-14*第4列$$\displaystyle =[0,0,\frac{1}{4},-\frac{7}{4},0,0,1,0,-158,-2744]$$ 第1列=第1列-3363*第5列$$\displaystyle =[1,0,-\frac{19}{4},\frac{133}{4},-\frac{3363}{16},0,0,0,0,-42028]$$ 第2列=第2列-2212*第5列$$\displaystyle =[0,\frac{1}{2},-\frac{7}{2},\frac{177}{8},-\frac{553}{4},0,0,0,0,-27605]$$ 第3列=第3列--158*第5列$$\displaystyle =[0,0,\frac{1}{4},-\frac{7}{4},\frac{79}{8},0,1,0,0,1680]$$ 第4列=第4列-28*第5列$$\displaystyle =[0,0,0,\frac{1}{8},-\frac{7}{4},0,0,1,0,-550]$$ 第1列=第1列--42028*第6列$$\displaystyle =[1,0,-\frac{19}{4},\frac{133}{4},-\frac{3363}{16},\frac{10507}{8},0,0,0,0]$$ 第2列=第2列--27605*第6列$$\displaystyle =[0,\frac{1}{2},-\frac{7}{2},\frac{177}{8},-\frac{553}{4},\frac{27605}{32},0,0,0,0]$$ 第3列=第3列-1680*第6列$$\displaystyle =[0,0,\frac{1}{4},-\frac{7}{4},\frac{79}{8},-\frac{105}{2},1,0,0,0]$$ 第4列=第4列--550*第6列$$\displaystyle =[0,0,0,\frac{1}{8},-\frac{7}{4},\frac{275}{16},0,1,0,0]$$ 第5列=第5列-28*第6列$$\displaystyle =[0,0,0,0,\frac{1}{16},-\frac{7}{8},0,0,1,0]$$ (%o27) $$\left[ \matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}&0&0&0&0\cr 0&\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}&0&0&0&0\cr 0&0&\frac{1}{4}&-\frac{7}{4}&\frac{79}{8}&-\frac{105}{2}&1&0&0&0\cr 0&0&0&\frac{1}{8}&-\frac{7}{4}&\frac{275}{16}&0&1&0&0\cr 0&0&0&0&\frac{1}{16}&-\frac{7}{8}&0&0&1&0\cr 0&0&0&0&0&\frac{1}{32}&0&0&0&1\cr 0&0&0&0&0&0&35&0&0&0\cr 0&0&0&0&0&0&0&35&0&0\cr 0&0&0&0&0&0&0&0&1225&0\cr 0&0&0&0&0&0&0&0&0&1225}\right]$$ 將右下角化簡為零 (%i29) for i:k+1 thru n do (j:i+n-k, print("第",j,"列=第",j,"列-",M_tilde[j,j],"*第",i,"列=", M_tilde[j]:M_tilde[j]-M_tilde[j,j]*M_tilde[ i ]) )$
M_tilde;

(%o29)　$$\left[ \matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}&0&0&0&0\cr 0&\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}&0&0&0&0\cr 0&0&\frac{1}{4}&-\frac{7}{4}&\frac{79}{8}&-\frac{105}{2}&1&0&0&0\cr 0&0&0&\frac{1}{8}&-\frac{7}{4}&\frac{275}{16}&0&1&0&0\cr 0&0&0&0&\frac{1}{16}&-\frac{7}{8}&0&0&1&0\cr 0&0&0&0&0&\frac{1}{32}&0&0&0&1\cr 0&0&-\frac{35}{4}&\frac{245}{4}&-\frac{2765}{8}&\frac{3675}{2}&0&0&0&0\cr 0&0&0&-\frac{35}{8}&\frac{245}{4}&-\frac{9625}{16}&0&0&0&0\cr 0&0&0&0&-\frac{1225}{16}&\frac{8575}{8}&0&0&0&0\cr 0&0&0&0&0&-\frac{1225}{32}&0&0&0&0}\right]$$

(%i31)
for i:k+1 thru n do
(j:i+n-k,
print("第",i,"列和第",j,"列交換"),
[M_tilde[j],M_tilde[ i ]]:[M_tilde[ i ],M_tilde[j]]
)$M_tilde; 第3列和第7列交換 第4列和第8列交換 第5列和第9列交換 第6列和第10列交換 (%o31) $$\left[ \matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}&0&0&0&0\cr 0&\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}&0&0&0&0\cr 0&0&-\frac{35}{4}&\frac{245}{4}&-\frac{2765}{8}&\frac{3675}{2}&0&0&0&0\cr 0&0&0&-\frac{35}{8}&\frac{245}{4}&-\frac{9625}{16}&0&0&0&0\cr 0&0&0&0&-\frac{1225}{16}&\frac{8575}{8}&0&0&0&0\cr 0&0&0&0&0&-\frac{1225}{32}&0&0&0&0\cr 0&0&\frac{1}{4}&-\frac{7}{4}&\frac{79}{8}&-\frac{105}{2}&1&0&0&0\cr 0&0&0&\frac{1}{8}&-\frac{7}{4}&\frac{275}{16}&0&1&0&0\cr 0&0&0&0&\frac{1}{16}&-\frac{7}{8}&0&0&1&0\cr 0&0&0&0&0&\frac{1}{32}&0&0&0&1}\right]$$ 得到左上角矩陣$$\widehat{M}$$ (%i32) M_hat:genmatrix(lambda([i,j],M_tilde[i,j]),n,n); (M_hat) $$\left[ \matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}\cr 0&\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}\cr 0&0&-\frac{35}{4}&\frac{245}{4}&-\frac{2765}{8}&\frac{3675}{2}\cr 0&0&0&-\frac{35}{8}&\frac{245}{4}&-\frac{9625}{16}\cr 0&0&0&0&-\frac{1225}{16}&\frac{8575}{8}\cr 0&0&0&0&0&-\frac{1225}{32}}\right]$$ $$\widehat{M}$$乘32倍變成整數 (%i33) M_hat:M_hat*1/delta*X^(n-1); (M_hat) $$\left[ \matrix{ 32&0&-152&1064&-6726&42028\cr 0&16&-112&708&-4424&27605\cr 0&0&-280&1960&-11060&58800\cr 0&0&0&-140&1960&-19250\cr 0&0&0&0&-2450&34300\cr 0&0&0&0&0&-1225}\right]$$ LLL化簡 (%i34) B: LLL(M_hat); (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正交化 (%i35) Bstar:apply(matrix,expand(gramschmidt(B))); (Bstar) $$\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]$$ 取最後一個正交向量 (%i36) Bstar_n:Bstar[n]; (Bstar_n) $$\displaystyle \left[-\frac{117600}{17929},-\frac{627200}{17929},\frac{3763200}{17929},\frac{2508800}{17929},\frac{627200}{17929},-\frac{2508800}{17929}\right]$$ 取各分數的分母 (%i37) Denom:map('denom,Bstar_n); (Denom) $$[17929,17929,17929,17929,17929,17929]$$ 求最大的分母 (%i38) MaxDenom:lmax(%); (MaxDenom) 17929 正交向量化為整數 (%i39) Bstar_n:Bstar_n*MaxDenom; (Bstar_n) $$[-117600,-627200,3763200,2508800,627200,-2508800]$$ 計算最大公因數 (%i40) GCD:lreduce('gcd,Bstar_n); (GCD) 39200 同除最大公因數，得到化簡的正交向量 (%i41) Bstar_n:Bstar_n/GCD; (Bstar_n) $$[-3,-16,96,64,16,-64]$$ 正交向量和$$\displaystyle \left(\frac{x}{X}\right)^i$$相乘 (%i42) hx:sum(Bstar_n[i+1]*(x/X)^i,i,0,n-1); (hx) $$-2x^5+x^4+8x^3+24x^2-8x-3$$ 將$$h(x)$$因式分解 (%i43) factor(hx); (%o43) $$-(x-3)(2x-1)(x^3+3x^2+5x+1)$$ 得到$$h(x)$$的解 (%i44) x:3; (x) 3 驗證答案 (%i45) ev(mod(px,N),x=3); (%o45) 0 TOP  bugmens 發私訊 加為好友 目前離線 5# 大 中 小 發表於 2021-6-7 19:44 只看該作者 解三次同餘方程式$$p(x)=x^3-4x^2-3x-10\pmod{1131}$$。 參考資料 Finding Small Roots of Polynomial Equations Using Lattice Basis Reduction https://ntnuopen.ntnu.no/ntnu-xm ... e=1&isAllowed=y 請下載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/share/LLL.mac 要先載入eigen.mac才能使用gramschmidt指令 (%i2) load("eigen.mac"); (%o2) C:/maxima-5.43.2/share/maxima/5.43.2/share/matrix/eigen.mac 要先載入diag.mac才能使用diag指令 (%i3) load("diag.mac"); (%o3) C:/maxima-5.43.2/share/maxima/5.43.2/share/contrib/diag.mac 同餘方程式$$p(x)$$ (%i4) px:x^3-4*x^2-3*x-10; (px) $$x^3-4x^2-3x-10$$ $$p(x)\equiv 0\pmod{N}$$ (%i5) N:1131; (N) 1131 $$p(x)$$的次數$$k$$ (%i6) k:hipow(px,x); (k) 3 設誤差值$$epsilon=0.1$$ (%i7) epsilon:0.1; (epsilon) 0.1 參數h (%i8) h:ceiling(max(7/k,(k+epsilon*k-1)/(epsilon*k^2))); (h) 3 $$\widehat{M}$$的維度$$n=hk$$ (%i9) n:h*k; (n) 9 參數$$\delta$$，按照公式應該是$$\displaystyle \delta=\frac{1}{3}$$，本範例$$\displaystyle \delta=\frac{1}{9}$$ (%i11) delta:1/sqrt(h*k); delta:1/9; (delta) $$\displaystyle \frac{1}{3}$$ (delta) $$\displaystyle \frac{1}{9}$$ 希望能找到$$|\;x|\; Howgrave-Graham論文中回顧Coppersmith方法，但步驟3,4又和Coppersmith有些許不同，本文章就之前範例說明。  方法 範例 步驟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$$ 註： 1.原論文用$$c(x)$$，本文章和Coppersmith一致用$$r(x)$$。 2.原論文的$$\widehat{M}$$有行列互換，但本文章沒有行列互換，但不影響計算過程。 原論文 $$\widetilde{M}=\left[\matrix{ -1225&&&&&\cr 34300&-2450&&&&\cr -19250&1960&-140&&&\cr 58800&-11060&1960&-280&&\cr 27605&-4424&708&-112&16&\cr 42028&-6726&1064&-152&0&32}\right]$$，$$H_2^{-1}=\left[\matrix{ -5&4&-2&1&-1&-2\cr 138&-109&56&-18&31&57\cr -77&60&-32&8&-18&-32\cr 231&-171&104&-7&59&98\cr 109&-82&48&-6&27&46\cr 166&-125&73&-9&41&70}\right]$$ 本文章 $$\widetilde{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 &&&&-2450&34300\cr &&&&&-1225}\right]$$，$$H_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]$$ 參考資料： N. Howgrave-Graham. Finding small roots of univariate modular equations revisited. In Cryptography and Coding– Proc. IMA ’97, volume 1355 of Lecture Notes in Computer Science, pages 131–142. Springer, 1997. https://link.springer.com/chapter/10.1007/BFb0024458 請下載LLL.zip，解壓縮後將LLL.mac放到C:\maxima-5.45.0\share\maxima\5.45.0\share目錄下 要先載入LLL.mac才能使用LLL指令 (%i1) load("LLL.mac"); (%o1) C:/maxima-5.45.0/share/maxima/5.45.0/share/LLL.mac 同餘方程式 (%i2) px:x^2+14*x+19; (px) $$x^2+14x+19$$ $$p(x)\equiv 0\pmod{N}$$ (%i3) N:35; (N) 35 $$p(x)$$的次數$$k$$ (%i4) k:hipow(px,x); (k) 2 設誤差值$$epsilon=0.1$$ (%i5) epsilon:0.1; (epsilon) 0.1 參數$$h$$ (%i7) h:ceiling(max(7/k,(k+epsilon*k-1)/(epsilon*k^2))); h:3; (h) 4 (h) 3 $$\widehat{M}$$的維度$$n=hk$$ (%i8) n:h*k; (n) 6 參數$$\delta$$，按照公式應該是$$\displaystyle \delta=\frac{1}{\sqrt{6}}$$，本範例$$\delta=1$$ (%i10) delta:1/sqrt(h*k); delta:1; (delta) $$\displaystyle \frac{1}{\sqrt{6}}$$ (delta) 1 希望能找到$$|\;x|\;<X=\frac{1}{2}N^{1/k}$$，$$p(x)\equiv 0\pmod{N}$$ (%i11) X:floor(1/2*N^(1/k)); (X) 2 產生矩陣$$M$$ (%i14) kill(genlattice)$
genlattice[i,j]:=(
v:floor((k+j-h*k-1)/k),
u: (j-h*k-1)-k*(v-1),
if i<=h*k and j<=h*k then if i=j then delta*X^(1-i) else 0/*左上角矩陣*/
else if i<=h*k and j>h*k then (coeff(expand(x^u*px^v),x,i-1))/*右上角矩陣*/
else if i>h*k and j<=h*k then 0/*左下角矩陣*/
else if i>h*k and j>h*k then if i=j then N^v else 0)$/*右下角矩陣*/ M:genmatrix(genlattice,2*h*k-k,2*h*k-k); (M) $$\left[\matrix{\displaystyle 1&0&0&0&0&0&19&0&361&0\cr 0&\frac{1}{2}&0&0&0&0&14&19&532&361\cr 0&0&\frac{1}{4}&0&0&0&1&14&234&532\cr 0&0&0&\frac{1}{8}&0&0&0&1&28&234\cr 0&0&0&0&\frac{1}{16}&0&0&0&1&28\cr 0&0&0&0&0&\frac{1}{32}&0&0&0&1\cr 0&0&0&0&0&0&35&0&0&0\cr 0&0&0&0&0&0&0&35&0&0\cr 0&0&0&0&0&0&0&0&1225&0\cr 0&0&0&0&0&0&0&0&0&1225}\right]$$ 將矩陣$$M$$複製成另一個矩陣$$\widetilde{M}$$ (%i15) M_tilde:copymatrix(M)$

(%i17)
for i:n thru k+1 step -1 do
(for j:1 thru i-1 do
(M_tilde:rowop(M_tilde,j,i,M_tilde[j,i+n-k])),/*消掉右上角*/
j:i+n-k,
M_tilde:rowop(M_tilde,j,i,M_tilde[j,j]),/*消掉右下角N^v*/
M_tilde:rowswap(M_tilde,i,j)/*列交換*/
)$M_tilde; (%o17) $$\left[\matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}&0&0&0&0\cr 0&\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}&0&0&0&0\cr 0&0&-\frac{35}{4}&\frac{245}{4}&-\frac{2765}{8}&\frac{3675}{2}&0&0&0&0\cr 0&0&0&-\frac{35}{8}&\frac{245}{4}&-\frac{9625}{16}&0&0&0&0\cr 0&0&0&0&-\frac{1225}{16}&\frac{8575}{8}&0&0&0&0\cr 0&0&0&0&0&-\frac{1225}{32}&0&0&0&0\cr 0&0&\frac{1}{4}&-\frac{7}{4}&\frac{79}{8}&-\frac{105}{2}&1&0&0&0\cr 0&0&0&\frac{1}{8}&-\frac{7}{4}&\frac{275}{16}&0&1&0&0\cr 0&0&0&0&\frac{1}{16}&-\frac{7}{8}&0&0&1&0\cr 0&0&0&0&0&\frac{1}{32}&0&0&0&1}\right]$$ 計算矩陣$$H_1^{-1}=M\widetilde{M}^{-1}$$ (%i18) H1_inv:M.invert(M_tilde); (H1_inv) $$\left[\matrix{\displaystyle 1&0&0&0&0&0&19&0&361&0\cr 0&1&0&0&0&0&14&19&532&361\cr 0&0&0&0&0&0&1&14&234&532\cr 0&0&0&0&0&0&0&1&28&234\cr 0&0&0&0&0&0&0&0&1&28\cr 0&0&0&0&0&0&0&0&0&1\cr 0&0&1&0&0&0&35&0&0&0\cr 0&0&0&1&0&0&0&35&0&0\cr 0&0&0&0&1&0&0&0&1225&0\cr 0&0&0&0&0&1&0&0&0&1225}\right]$$ 產生$$r(x)$$ (%i19) rx:create_list(x^i,i,0,h*k-1); (rx) $$\left[1,x,x^2,x^3,x^4,x^5\right]$$ 產生$$r(x)$$ (%i21) for j:1 thru h*k-k do (print("j=",j, ",v=floor(","k+j-1"/"k",")=floor(",(k+j-1)/k,")=",v:floor((k+j-1)/k), ",u=(j-1)-k(v-1)=(",j,"-1)-",k,"(",v,"-1)","=",u: (j-1)-k*(v-1), ",-","x"^"u"*"p(x)"^"v"/"N"^"v","=","-","x"^u*"p(x)"^v/"N"^v), rx:append(rx,[-x^u*px^v/N^v]) )$
rx;

$$\displaystyle j=1,v=floor(\frac{k+j-1}{k})=floor(1)=1,u=(j-1)-k(v-1)=(1-1)-2(1-1)=0,-\frac{p(x)^v x^u}{N^v}=-\frac{p(x)}{N}$$
$$\displaystyle j=2,v=floor(\frac{k+j-1}{k})=floor(\frac{3}{2})=1,u=(j-1)-k(v-1)=(2-1)-2(1-1)=1,-\frac{p(x)^v x^u}{N^v}=-\frac{p(x)x}{N}$$
$$\displaystyle j=3,v=floor(\frac{k+j-1}{k})=floor(2)=2,u=(j-1)-k(v-1)=(3-1)-2(2-1)=0,-\frac{p(x)^v x^u}{N^v}=-\frac{p(x)^2}{N^2}$$
$$\displaystyle j=4,v=floor(\frac{k+j-1}{k})=floor(\frac{5}{2})=2,u=(j-1)-k(v-1)=(4-1)-2(2-1)=1,-\frac{p(x)^v x^u}{N^v}=-\frac{p(x)^2x}{N^2}$$
(%o21)　$$\displaystyle \left[1,x,x^2,x^3,x^4,x^5,\frac{-x^2-14x-19}{35},-\frac{x(x^2+14x+19)}{35},-\frac{(x^2+14x+19)^2}{1225},-\frac{x(x^2+14x+19)^2}{1225}\right]$$

(%i22)　rxH1_inv:args(rx.H1_inv)[1];
(rxH1_inv)　$$\displaystyle [1,x,\frac{-x^2-14x-19}{35},-\frac{x(x^2+14*x+19)}{35},-\frac{(x^2+14x+19)^2}{1225},-\frac{x(x^2+14x+19)^2}{1225},0,$$
$$x^3-x(x^2+14x+19)+14x^2+19x,$$
$$-(x^2+14x+19)^2+x^4+28x^3+234x^2+532x+361,$$
$$-x(x^2+14x+19)^2+x^5+28x^4+234x^3+532x^2+361x]$$

(%i23)　rxH1_inv:ratsimp(rxH1_inv);
(rxH1_inv)　$$\displaystyle \left[1,x,-\frac{x^2+14x+19}{35},-\frac{x^3+14x^2+19x}{35},-\frac{x^4+28x^3+234x^2+532x+361}{1225},-\frac{x^5+28x^4+234x^3+532x^2+361x}{1225},0,0,0,0\right]$$

(%i24)　rxH1_inv_short:rest(rxH1_inv,-(h*k-k));
(rxH1_inv_short)　$$\displaystyle \left[1,x,-\frac{x^2+14x+19}{35},-\frac{x^3+14x^2+19x}{35},-\frac{x^4+28x^3+234x^2+532x+361}{1225},-\frac{x^5+28x^4+234x^3+532x^2+361x}{1225}\right]$$

(%i25)　M_hat:genmatrix(lambda([i,j],M_tilde[i,j]),n,n);
(M_hat)　$$\left[\matrix{\displaystyle 1&0&-\frac{19}{4}&\frac{133}{4}&-\frac{3363}{16}&\frac{10507}{8}\cr 0&\frac{1}{2}&-\frac{7}{2}&\frac{177}{8}&-\frac{553}{4}&\frac{27605}{32}\cr 0&0&-\frac{35}{4}&\frac{245}{4}&-\frac{2765}{8}&\frac{3675}{2}\cr 0&0&0&-\frac{35}{8}&\frac{245}{4}&-\frac{9625}{16}\cr 0&0&0&0&-\frac{1225}{16}&\frac{8575}{8}\cr 0&0&0&0&0&-\frac{1225}{32}}\right]$$

$$\widehat{M}$$乘32倍變成整數
(%i26)　M_hat:M_hat*1/delta*X^(n-1);
(M_hat)　$$\left[\matrix{\displaystyle 32&0&-152&1064&-6726&42028\cr 0&16&-112&708&-4424&27605\cr 0&0&-280&1960&-11060&58800\cr 0&0&0&-140&1960&-19250\cr 0&0&0&0&-2450&34300\cr 0&0&0&0&0&-1225}\right]$$

LLL化簡
(%i27)　B2: LLL(M_hat);
(B2)　$$\left[\matrix{\displaystyle 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]$$

(%i28)　H2_inv:M_hat.invert(B2);
(H2_inv)　$$\left[\matrix{\displaystyle -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]$$

(%i29)　H2_inv_lastcolumn:transpose(col(H2_inv,n));
(H2_inv_lastcolumn)　$$[\matrix{-70&-46&-98&32&-57&2}]$$

(%i30)　hx:rxH1_inv_short.H2_inv_lastcolumn;
(hx)　$$\displaystyle -\frac{2(x^5+28x^4+234x^3+532x^2+361x)}{1225}+\frac{57(x^4+28x^3+234x^2+532x+361)}{1225}-\frac{32(x^3+14x^2+19x)}{35}+\frac{14(x^2+14x+19)}{5}-46x-70$$

(%i31)　factor(hx);
(%o31)　$$\displaystyle -\frac{(x-3)(2x-1)(x^3+3x^2+5x+1)}{1225}$$

(%i32)　x:3;
(x)　3

(%i33)　ev(mod(px,N),x=3);
(%o33)　0

TOP

 bugmens 發私訊 加為好友 目前離線 7# 大 中 小 發表於 2021-6-19 18:16  只看該作者 解三次同餘方程式$$p(x)=x^3-4x^2-3x-10\pmod{1131}$$。 參考資料 Finding Small Roots of Polynomial Equations Using Lattice Basis Reduction https://ntnuopen.ntnu.no/ntnu-xm ... e=1&isAllowed=y 請下載LLL.zip，解壓縮後將LLL.mac放到C:\maxima-5.45.0\share\maxima\5.45.0\share目錄下 要先載入LLL.mac才能使用LLL指令 (%i1)　load("LLL.mac"); (%o1)　C:/maxima-5.45.0/share/maxima/5.45.0/share/LLL.mac 同餘方程式$$p(x)$$ (%i2)　px:x^3-4*x^2-3*x-10; (px)　$$x^3-4x^2-3x-10$$ $$p(x)\equiv 0\pmod{N}$$ (%i3)　N:1131; (N)　1131 $$p(x)$$的次數$$k$$ (%i4)　k:hipow(px,x); (k)　3 設誤差值$$\epsilon=0.1$$ (%i5)　epsilon:0.1; (epsilon)　0.1 參數$$h$$ (%i6)　h:ceiling(max(7/k,(k+epsilon*k-1)/(epsilon*k^2))); (h)　3 $$\widehat{M}$$的維度$$n=hk$$ (%i7)　n:h*k; (n)　9 參數$$\delta$$，按照公式應該是$$\displaystyle \delta=\frac{1}{3}$$，本範例$$\displaystyle \delta=\frac{1}{9}$$ (%i9) delta:1/sqrt(h*k); delta:1/9; (delta)　$$\displaystyle \frac{1}{3}$$ (delta)　$$\displaystyle \frac{1}{9}$$ 希望能找到$$\displaystyle |\;x|\;h*k then (coeff(expand(x^u*px^v),x,i-1))/*右上角矩陣*/ else if i>h*k and j<=h*k then 0/*左下角矩陣*/ else if i>h*k and j>h*k then if i=j then N^v else 0)/*右下角矩陣*/ M:genmatrix(genlattice,2*h*k-k,2*h*k-k); (M) \(\left[\matrix{\displaystyle \frac{1}{9}&0&0&0&0&0&0&0&0&-10&0&0&100&0&0\cr 0&\frac{1}{54}&0&0&0&0&0&0&0&-3&-10&0&60&100&0\cr 0&0&\frac{1}{324}&0&0&0&0&0&0&-4&-3&-10&89&60&100\cr 0&0&0&\frac{1}{1944}&0&0&0&0&0&1&-4&-3&4&89&60\cr 0&0&0&0&\frac{1}{11664}&0&0&0&0&0&1&-4&10&4&89\cr 0&0&0&0&0&\frac{1}{69984}&0&0&0&0&0&1&-8&10&4\cr 0&0&0&0&0&0&\frac{1}{419904}&0&0&0&0&0&1&-8&10\cr 0&0&0&0&0&0&0&\frac{1}{2519424}&0&0&0&0&0&1&-8\cr 0&0&0&0&0&0&0&0&\frac{1}{15116544}&0&0&0&0&0&1\cr 0&0&0&0&0&0&0&0&0&1131&0&0&0&0&0\cr 0&0&0&0&0&0&0&0&0&0&1131&0&0&0&0\cr 0&0&0&0&0&0&0&0&0&0&0&1131&0&0&0\cr 0&0&0&0&0&0&0&0&0&0&0&0&1279161&0&0\cr 0&0&0&0&0&0&0&0&0&0&0&0&0&1279161&0\cr 0&0&0&0&0&0&0&0&0&0&0&0&0&0&1279161}\right]$$ 將矩陣$$M$$複製成另一個矩陣$$\widetilde{M}$$ (%i15)　M_tilde:copymatrix(M)$矩陣$$\widetilde{M}$$進行矩陣列運算 (%i17) for i:n thru k+1 step -1 do (for j:1 thru i-1 do (M_tilde:rowop(M_tilde,j,i,M_tilde[j,i+n-k])),/*消掉右上角*/ j:i+n-k, M_tilde:rowop(M_tilde,j,i,M_tilde[j,j]),/*消掉右下角N^v*/ M_tilde:rowswap(M_tilde,i,j)/*列交換*/ )$ M_tilde; (%o17)　$$\left[\matrix{\displaystyle \frac{1}{9}&0&0&\frac{5}{972}&\frac{5}{1458}&\frac{95}{34992}&\frac{245}{104976}&\frac{815}{419904}&\frac{1525}{944784}&0&0&0&0&0&0\cr 0&\frac{1}{54}&0&\frac{1}{648}&\frac{11}{5832}&\frac{97}{69984}&\frac{121}{104976}&\frac{2447}{2519424}&\frac{2035}{2519424}&0&0&0&0&0&0\cr 0&0&\frac{1}{324}&\frac{1}{486}&\frac{19}{11664}&\frac{49}{34992}&\frac{163}{139968}&\frac{305}{314928}&\frac{4069}{5038848}&0&0&0&0&0&0\cr 0&0&0&-\frac{377}{648}&-\frac{377}{972}&-\frac{7163}{23328}&-\frac{377}{1296}&-\frac{214513}{839808}&-\frac{280865}{1259712}&0&0&0&0&0&0\cr 0&0&0&0&-\frac{377}{3888}&-\frac{377}{5832}&-\frac{4147}{69984}&-\frac{4147}{69984}&-\frac{275587}{5038848}&0&0&0&0&0&0\cr 0&0&0&0&0&-\frac{377}{23328}&-\frac{377}{17496}&-\frac{377}{15552}&-\frac{10933}{419904}&0&0&0&0&0&0\cr 0&0&0&0&0&0&-\frac{142129}{46656}&-\frac{142129}{34992}&-\frac{142129}{31104}&0&0&0&0&0&0\cr 0&0&0&0&0&0&0&-\frac{142129}{279936}&-\frac{142129}{209952}&0&0&0&0&0&0\cr 0&0&0&0&0&0&0&0&-\frac{142129}{1679616}&0&0&0&0&0&0\cr 0&0&0&\frac{1}{1944}&\frac{1}{2916}&\frac{19}{69984}&\frac{1}{3888}&\frac{569}{2519424}&\frac{745}{3779136}&1&0&0&0&0&0\cr 0&0&0&0&\frac{1}{11664}&\frac{1}{17496}&\frac{11}{209952}&\frac{11}{209952}&\frac{731}{15116544}&0&1&0&0&0&0\cr 0&0&0&0&0&\frac{1}{69984}&\frac{1}{52488}&\frac{1}{46656}&\frac{29}{1259712}&0&0&1&0&0&0\cr 0&0&0&0&0&0&\frac{1}{419904}&\frac{1}{314928}&\frac{1}{279936}&0&0&0&1&0&0\cr 0&0&0&0&0&0&0&\frac{1}{2519424}&\frac{1}{1889568}&0&0&0&0&1&0\cr 0&0&0&0&0&0&0&0&\frac{1}{15116544}&0&0&0&0&0&1}\right]$$ 計算矩陣$$H_1^{-1}=M\widetilde{M}^{-1}$$ (%i18)　H1_inv:M.invert(M_tilde); (H1_inv)　$$\left[\matrix{\displaystyle 1&0&0&0&0&0&0&0&0&-10&0&0&100&0&0\cr 0&1&0&0&0&0&0&0&0&-3&-10&0&60&100&0\cr 0&0&1&0&0&0&0&0&0&-4&-3&-10&89&60&100\cr 0&0&0&0&0&0&0&0&0&1&-4&-3&4&89&60\cr 0&0&0&0&0&0&0&0&0&0&1&-4&10&4&89\cr 0&0&0&0&0&0&0&0&0&0&0&1&-8&10&4\cr 0&0&0&0&0&0&0&0&0&0&0&0&1&-8&10\cr 0&0&0&0&0&0&0&0&0&0&0&0&0&1&-8\cr 0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\cr 0&0&0&1&0&0&0&0&0&1131&0&0&0&0&0\cr 0&0&0&0&1&0&0&0&0&0&1131&0&0&0&0\cr 0&0&0&0&0&1&0&0&0&0&0&1131&0&0&0\cr 0&0&0&0&0&0&1&0&0&0&0&0&1279161&0&0\cr 0&0&0&0&0&0&0&1&0&0&0&0&0&1279161&0\cr 0&0&0&0&0&0&0&0&1&0&0&0&0&0&1279161}\right]$$ 產生$$r(x)$$ (%i19)　rx:create_list(x^i,i,0,h*k-1); (rx)　$$[1,x,x^2,x^3,x^4,x^5,x^6,x^7,x^8]$$ 產生$$r(x)$$ (%i21) for j:1 thru h*k-k do   (print("j=",j,            ",v=floor(","k+j-1"/"k",")=floor(",(k+j-1)/k,")=",v:floor((k+j-1)/k),             ",u=(j-1)-k(v-1)=(",j,"-1)-",k,"(",v,"-1)","=",u: (j-1)-k*(v-1),             ",-","x"^"u"*"p(x)"^"v"/"N"^"v","=","-","x"^u*"p(x)"^v/"N"^v),    rx:append(rx,[-x^u*px^v/N^v])   )$rx; $$\displaystyle j=1,v=floor(\frac{k+j-1}{k})=floor(1)=1,u=(j-1)-k(v-1)=(1-1)-3(1-1)=0,-\frac{p(x)^vx^u}{N^v}=-\frac{p(x)}{N}$$ $$\displaystyle j=2,v=floor(\frac{k+j-1}{k})=floor(4/3)=1,u=(j-1)-k(v-1)=(2-1)-3(1-1)=1,-\frac{p(x)^vx^u}{N^v}=-\frac{p(x)x}{N}$$ $$\displaystyle j=3,v=floor(\frac{k+j-1}{k})=floor(5/3)=1,u=(j-1)-k(v-1)=(3-1)-3(1-1)=2,-\frac{p(x)^vx^u}{N^v}=-\frac{p(x)x^2}{N}$$ $$\displaystyle j=4,v=floor(\frac{k+j-1}{k})=floor(2)=2,u=(j-1)-k(v-1)=(4-1)-3(2-1)=0,-\frac{p(x)^vx^u}{N^v}=-\frac{p(x)^2}{N^2}$$ $$\displaystyle j=5,v=floor(\frac{k+j-1}{k})=floor(7/3)=2,u=(j-1)-k(v-1)=(5-1)-3(2-1)=1,-\frac{p(x)^vx^u}{N^v}=-\frac{p(x)^2x}{N^2}$$ $$\displaystyle j=6,v=floor(\frac{k+j-1}{k})=floor(8/3)=2,u=(j-1)-k(v-1)=(6-1)-3(2-1)=2,-\frac{p(x)^vx^u}{N^v}=-\frac{p(x)^2*x^2}{N^2}$$ (%o21) $$\displaystyle [1,x,x^2,x^3,x^4,x^5,x^6,x^7,x^8,\frac{-x^3+4x^2+3x+10}{1131},-\frac{x(x^3-4x^2-3x-10)}{1131},-\frac{x^2(x^3-4x^2-3x-10)}{1131},$$ $$\displaystyle -\frac{(x^3-4x^2-3x-10)^2}{1279161},-\frac{x(x^3-4x^2-3x-10)^2}{1279161},-\frac{x^2(x^3-4x^2-3x-10)^2}{1279161}]$$ 計算$$r(x)H_1^{-1}$$ (%i22) rxH1_inv:args(rx.H1_inv)[1]; (rxH1_inv) $$\displaystyle [1,x,x^2,\frac{-x^3+4x^2+3x+10}{1131},-\frac{x(x^3-4x^2-3x-10)}{1131},-\frac{x^2(x^3-4x^2-3x-10)}{1131},-\frac{(x^3-4x^2-3x-10)^2}{1279161},-\frac{x(x^3-4x^2-3x-10)^2}{1279161},-\frac{x^2(x^3-4x^2-3x-10)^2}{1279161},0,$$ $$x^4-x(x^3-4x^2-3x-10)-4x^3-3x^2-10x,$$ $$x^5-4x^4-x^2(x^3-4x^2-3x-10)-3x^3-10x^2,$$ $$-(x^3-4x^2-3x-10)^2+x^6-8x^5+10x^4+4x^3+89x^2+60x+100,$$ $$-x(x^3-4x^2-3x-10)^2+x^7-8x^6+10x^5+4x^4+89x^3+60x^2+100x,$$ $$-x^2(x^3-4x^2-3x-10)^2+x^8-8x^7+10x^6+4x^5+89x^4+60x^3+100x^2]$$ 其中$$r(x)H_1^{-1}$$後面化簡為0 (%i23) rxH1_inv:ratsimp(rxH1_inv); (rxH1_inv) $$\displaystyle \left[1,x,x^2,\frac{-x^3+4x^2+3x+10}{1131},-\frac{x(x^3-4x^2-3x-10)}{1131},-\frac{x^2(x^3-4x^2-3x-10)}{1131},-\frac{(x^3-4x^2-3x-10)^2}{1279161},-\frac{x(x^3-4x^2-3x-10)^2}{1279161},-\frac{x^2(x^3-4x^2-3x-10)^2}{1279161},0,0,0,0,0,0\right]$$ 縮短$$r(x)H)_1^{-1}$$長度 (%i24) rxH1_inv_short:rest(rxH1_inv,-(h*k-k)); (rxH1_inv_short) $$\displaystyle \left[1,x,x^2,\frac{-x^3+4x^2+3x+10}{1131},-\frac{x(x^3-4x^2-3x-10)}{1131},-\frac{x^2(x^3-4x^2-3x-10)}{1131},-\frac{(x^3-4x^2-3x-10)^2}{1279161},-\frac{x(x^3-4x^2-3x-10)^2}{1279161},-\frac{x^2(x^3-4x^2-3x-10)^2}{1279161}\right]$$ 得到左上角矩陣$$\widehat{M}$$ (%i25) M_hat:genmatrix(lambda([i,j],M_tilde[i,j]),n,n); (M_hat) $$\left[\matrix{\displaystyle \frac{1}{9}&0&0&\frac{5}{972}&\frac{5}{1458}&\frac{95}{34992}&\frac{245}{104976}&\frac{815}{419904}&\frac{1525}{944784}\cr 0&\frac{1}{54}&0&\frac{1}{648}&\frac{11}{5832}&\frac{97}{69984}&\frac{121}{104976}&\frac{2447}{2519424}&\frac{2035}{2519424}\cr 0&0&\frac{1}{324}&\frac{1}{486}&\frac{19}{11664}&\frac{49}{34992}&\frac{163}{139968}&\frac{305}{314928}&\frac{4069}{5038848}\cr 0&0&0&-\frac{377}{648}&-\frac{377}{972}&-\frac{7163}{23328}&-\frac{377}{1296}&-\frac{214513}{839808}&-\frac{280865}{1259712}\cr 0&0&0&0&-\frac{377}{3888}&-\frac{377}{5832}&-\frac{4147}{69984}&-\frac{4147}{69984}&-\frac{275587}{5038848}\cr 0&0&0&0&0&-\frac{377}{23328}&-\frac{377}{17496}&-\frac{377}{15552}&-\frac{10933}{419904}\cr 0&0&0&0&0&0&-\frac{142129}{46656}&-\frac{142129}{34992}&-\frac{142129}{31104}\cr 0&0&0&0&0&0&0&-\frac{142129}{279936}&-\frac{142129}{209952}\cr 0&0&0&0&0&0&0&0&-\frac{142129}{1679616}}\right]$$ $$\widehat{M}$$乘1679616變成整數 (%i26) M_hat:M_hat*1/delta*X^(n-1); (M_hat) $$\left[\matrix{\displaystyle 1679616&0&0&77760&51840&41040&35280&29340&24400\cr 0&279936&0&23328&28512&20952&17424&14682&12210\cr 0&0&46656&31104&24624&21168&17604&14640&12207\cr 0&0&0&-8794656&-5863104&-4641624&-4397328&-3861234&-3370380\cr 0&0&0&0&-1465776&-977184&-895752&-895752&-826761\cr 0&0&0&0&0&-244296&-325728&-366444&-393588\cr 0&0&0&0&0&0&-46049796&-61399728&-69074694\cr 0&0&0&0&0&0&0&-7674966&-10233288\cr 0&0&0&0&0&0&0&0&-1279161}\right]$$ LLL化簡 (%i27) B2: LLL(M_hat); (B2) $$\left[\matrix{\displaystyle 0&0&46656&31104&24624&21168&17604&14640&12207\cr 0&279936&-46656&-7776&3888&-216&-180&42&3\cr 0&0&186624&124416&98496&-159624&-255312&-307884&-344760\cr 0&0&-46656&-31104&-24624&223128&308124&351804&-897780\cr 0&0&513216&342144&-1194912&-255744&-50652&-1824&94692\cr 1679616&0&-46656&46656&27216&19872&17676&14700&12193\cr 0&0&-513216&-342144&-270864&2210112&3063636&-4171566&-35880\cr 0&559872&3825792&-6197472&610416&67608&-231696&55866&135297\cr 0&0&-559872&-373248&-4692816&20511144&-17352684&1982268&-265239}\right]$$ 計算矩陣$$H_2^{-1}=\widehat{M}B_2^{-1}$$ (%i28) H2_inv:M_hat.invert(B2); (H2_inv) $$\left[\matrix{\displaystyle 1&0&0&0&0&1&0&0&0\cr 1&1&0&0&0&0&0&0&0\cr 1&0&0&0&0&0&0&0&0\cr -141&-2&6&0&3&0&0&1&0\cr -19&0&2&0&1&0&0&0&0\cr -4&0&1&0&0&0&0&0&0\cr -477&0&145&14&-3&0&4&0&1\cr -44&0&15&5&0&0&1&0&0\cr -3&0&1&1&0&0&0&0&0}\right]$$ 取矩陣$$H_2^{-1}$$最後一行 (%i29) H2_inv_lastcolumn:transpose(col(H2_inv,n)); (H2_inv_lastcolumn) $$[\matrix{0&0&0&0&0&0&1&0&0}]$$ 將$$[r(x)H_1^{-1}]_{sh}\cdot ((H_2^{-1})_{hk})^T$$相乘 (%i30) hx:rxH1_inv_short.H2_inv_lastcolumn; (hx) $$\displaystyle -\frac{x^6-8x^5+10x^4+4x^3+89x^2+60x+100}{1279161}$$ 將$$h(x)$$因式分解 (%i31) factor(hx); (%o31) $$\displaystyle -\frac{(x-5)^2(x^2+x+2)^2}{1279161}$$ 得到$$h(x)$$的解 (%i32) x:5; (x) 5 驗證答案 (%i33) ev(mod(px,N),x=5); (%o33) 0 UID210 帖子1136 閱讀權限200 上線時間6704 小時 註冊時間2008-12-16 最後登入2024-6-15 查看詳細資料 TOP 當初Coppersmith的方法比較麻煩，Howgrave-Graham提供改良的方法，方法如下。  方法 範例 問題敘述 設同餘方程式為$$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|\; 引理1： 假設lattice \(L$$經LLL化簡後向量$$b_1,b_2,\ldots,b_n$$，則$$\Vert\;b_1 \Vert\;\le 2^{(n-1)/4}\cdot(det(L))^{1/n}$$。 [證明] 設$$b_i$$是LLL化簡後的向量，符合以下兩個條件 (1)(size-reduced)對$$1\le j<i\le n$$，$$\displaystyle |\;\mu_{i,j}|\;\le \frac{1}{2}$$ (2)(Lovász condition)對$$i=2,3,\ldots,n$$，$$\displaystyle \frac{3}{4}\Vert\;b_{i-1}^2\Vert\;\le \Vert\;b_i^*\Vert\;^2+\mu_{i,i-1}^2 \Vert\;b_{i-1}^*\Vert\;^2$$ https://en.wikipedia.org/wiki/Le ... reduction_algorithm 將(2)式移項$$\displaystyle (\frac{3}{4}-\mu_{i,i-1}^2) \Vert\;b_{i-1}^2\Vert\;^2\le \Vert\;b_i^*\Vert\;^2$$ 將(1)式平方$$\mu_{i,i-1}^2\le \frac{1}{4}$$代入上式，得到對$$1<i\le n$$，$$\displaystyle \frac{1}{2}\Vert\;b_{i-1}^*\Vert\;^2\le \Vert\;b_i^*\Vert\;^2$$，$$\displaystyle \Vert\;b_{i-1}^*\Vert\;^2\le 2^{i-(i-1)} \Vert\;b_i^*\Vert\;^2$$ 由數學歸納法得知，對$$1\le j\le i\le n$$，$$\Vert\;b_j^*\Vert\;^2\le 2^{i-j}\cdot \Vert\;b_i^*\Vert\;^2$$ 由Gram-Schmidt正交化可知$$\displaystyle b_i^*=b_i-\sum_{j=1}^{i-1}\mu_{ij}b_j^*$$，$$\displaystyle b_i=b_i^*+\sum_{j=1}^{i-1}\mu_{ij}b_j^*$$ $$\displaystyle \Vert\;b_i\Vert\;^2=\Vert\;b_i^*\Vert\;^2+2\sum_{j=1}^{i-1}\mu_{ij}b_i^*\cdot b_j^*+\sum_{j=1}^{i-1}\mu_{ij}^2\Vert\;b_j^*\Vert\;^2$$ 因為Gram-Schmidt正交化，$$b_i^*\cdot b_j^*=0$$代入上式 $$\displaystyle \Vert\;b_i\Vert\;^2=\Vert\;b_i^*\Vert\;^2+\sum_{j=1}^{i-1}\mu_{ij}^2\Vert\;b_j^*\Vert\;^2$$ $$\displaystyle \le \Vert\;b_i^*\Vert\;^2+\sum_{j=1}^{i-1}\frac{1}{4}2^{i-j}\Vert\;b_i^*\Vert\;^2$$ $$\displaystyle =(1+\frac{1}{4}(2^i-2))\cdot \Vert\;b_i^*\Vert\;^2$$ $$\le 2^{i-1}\cdot \Vert\;b_i^*\Vert\;^2$$ 對$$1\le j\le i\le n$$，$$\Vert\;b_j\Vert\;^2\le 2^{j-1}\cdot \Vert\;b_j^*\Vert\;^2\le 2^{i-1}\cdot \Vert\;b_i^*\Vert\;^2$$ $$\Vert\;b_1\Vert\;^2\le 2^{n-1}\Vert\;b_n^*\Vert\;^2$$ $$\Vert\;b_1\Vert\;^2\le 2^{n-2}\Vert\;b_{n-1}^*\Vert\;^2$$ $$\Vert\;b_1\Vert\;^2\le 2^{0}\Vert\;b_1^*\Vert\;^2$$ 將上面各式相乘$$\displaystyle \Vert\;b_1\Vert\;^{2n}\le 2^{0+1+\ldots+(n-2)+(n-1)}\prod_{i=1}^n \Vert\;b_i^*\Vert\;^2$$ $$\displaystyle \Vert\;b_1\Vert\;^{2n}\le 2^{\frac{n(n-1)}{2}}\cdot det(L)^2$$ $$\displaystyle \Vert\;b_1\Vert\;\le 2^{\frac{n-1}{4}}\cdot det(L)^{\frac{1}{n}}$$ 參考資料： N. Howgrave-Graham. Finding small roots of univariate modular equations revisited. In Cryptography and Coding– Proc. IMA ’97, volume 1355 of Lecture Notes in Computer Science, pages 131–142. Springer, 1997. https://link.springer.com/chapter/10.1007/BFb0024458 請下載LLL.zip，解壓縮後將LLL.mac放到C:\maxima-5.45.0\share\maxima\5.45.0\share目錄下 要先載入LLL.mac才能使用LLL指令 (%i1) load("LLL.mac"); (%o1) C:/maxima-5.45.0/share/maxima/5.45.0/share/LLL.mac 同餘方程式 (%i2) px:x^2+14*x+19; (px) $$x^2+14x+19$$ $$p(x)\equiv 0\pmod{N}$$ (%i3) N:35; (N) 35 $$p(x)$$的次數$$k$$ (%i4) k:hipow(px,x); (k) 2 參數$$h\ge 2$$ (%i5) h:3; (h) 3 希望能找到$$|\;x|\;<X$$，$$p(x)\equiv 0\pmod{N}$$ (%i6) X:ceiling(2^(-1/2)*(h*k)^(-1/(h*k-1))*N^((h-1)/(h*k-1)))-1; (X) 2 產生$$q_{u,v}(x)$$方程組 (%i7) q_uv:create_list((v:floor((i-1)/k), u: (i-1)-k*v, N^(h-1-v)*x^u*px^v),i,1,h*k); (q_uv) $$[1225,1225x,35(x^2+14x+19),35x(x^2+14x+19),(x^2+14x+19)^2,x(x^2+14x+19)^2]$$ 用$$Xx$$取代原本的$$x$$ (%i8) q_uv:ev(q_uv,x=x*X); (q_uv) $$[1225,2450x,35(4x^2+28x+19),70x(4x^2+28x+19),(4x^2+28x+19)^2,2x(4x^2+28x+19)^2]$$ $$x^1,x^2,\ldots,x^{hk-1}$$ (%i9) xpower:create_list(x^i,i,1,h*k-1); (xpower) $$[x,x^2,x^3,x^4,x^5]$$ 取多項式$$q_{u,v}(x)$$係數(常數項在最後一行) (%i10) M:augcoefmatrix(q_uv,xpower); (M) $$\left[\matrix{0&0&0&0&0&1225\cr 2450&0&0&0&0&0\cr 980&140&0&0&0&665\cr 1330&1960&280&0&0&0\cr 1064&936&224&16&0&361\cr 722&2128&1872&448&32&0}\right]$$ 將常數項移到第一行 (%i11) M:addcol(col(M,h*k),submatrix(M,h*k)); (M) $$\left[\matrix{1225&0&0&0&0&0\cr 0&2450&0&0&0&0\cr 665&980&140&0&0&0\cr 0&1330&1960&280&0&0\cr 361&1064&936&224&16&0\cr 0&722&2128&1872&448&32}\right]$$ LLL化簡 (%i12) B: LLL(M); (B) $$\left[\matrix{3&16&-96&-64&-16&64\cr 49&100&0&160&0&64\cr 115&-166&16&104&96&64\cr 61&32&148&-128&48&128\cr 21&-74&-56&16&224&-128\cr -201&8&132&-32&-48&32}\right]$$ 第一列短向量$$b_1$$ (%i13) B[1]; (%o13) $$[3,16,-96,-64,-16,64]$$ 產生的方程式不需要再同餘$$N^{h-1}$$ (%i14) rx:sum(B[1][i+1]*(x/X)^i,i,0,h*k-1); (rx) $$2x^5-x^4-8x^3-24x^2+8x+3$$ 將$$r(x)$$因式分解 (%i15) factor(rx); (%o15) $$(x-3)(2x-1)(x^3+3x^2+5x+1)$$ 得到$$r(x)$$的解 (%i16) x:3; (x) 3 驗證答案 (%i17) ev(mod(px,N),x=3); (%o17) 0 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 解三次同餘方程式$$p(x)=x^3-4x^2-3x-10\pmod{1131}$$。 參考資料 Finding Small Roots of Polynomial Equations Using Lattice Basis Reduction https://ntnuopen.ntnu.no/ntnu-xm ... e=1&isAllowed=y 請下載LLL.zip，解壓縮後將LLL.mac放到C:\maxima-5.45.0\share\maxima\5.45.0\share目錄下 要先載入LLL.mac才能使用LLL指令 (%i1) load("LLL.mac"); (%o1) C:/maxima-5.45.0/share/maxima/5.45.0/share/LLL.mac 同餘方程式 (%i2) px:x^3-4*x^2-3*x-10; (px) $$x^3-4x^2-3x-10$$ $$p(x)\equiv 0\pmod{N}$$ (%i3) N:1131; (N) 1131 $$p(x)$$的次數$$k$$ (%i4) k:hipow(px,x); (k) 3 參數$$h\ge 2$$ (%i5) h:3; (h) 3 希望能找到$$|\;x|\;<X$$，$$p(x)\equiv 0\pmod{N}$$ 按照公式應該是3，本範例$$X=6$$ (%i7) X:ceiling(2^(-1/2)*(h*k)^(-1/(h*k-1))*N^((h-1)/(h*k-1)))-1; X:6; (X) 3 (X) 6 產生$$q_{u,v}(x)$$方程組 (%i8) q_uv:create_list((v:floor((i-1)/k), u: (i-1)-k*v, N^(h-1-v)*x^u*px^v),i,1,h*k); (q_uv) $$[1279161,1279161x,1279161x^2,1131(x^3-4x^2-3x-10),1131x(x^3-4x^2-3x-10),1131x^2(x^3-4x^2-3x-10),$$ $$(x^3-4x^2-3x-10)^2,x(x^3-4x^2-3x-10)^2,x^2(x^3-4x^2-3x-10)^2]$$ 用$$Xx$$取代原本的$$x$$ (%i8) q_uv:ev(q_uv,x=x*X); (q_uv) $$[1279161,7674966x,46049796x^2,1131(216x^3-144x^2-18x-10),6786x(216x^3-144x^2-18x-10),$$ $$40716x^2(216x^3-144x^2-18x-10),(216x^3-144x^2-18x-10)^2,6x(216x^3-144x^2-18x-10)^2,36x^2(216x^3-144x^2-18x-10)^2]$$ $$x^1,x^2,\ldots,x^{hk-1}$$ (%i9) xpower:create_list(x^i,i,1,h*k-1); (xpower) $$[x,x^2,x^3,x^4,x^5,x^6,x^7,x^8]$$ 取多項式$$q_{u,v}(x)$$係數(常數項在最後一行) (%i11) M:augcoefmatrix(q_uv,xpower); (M) $$\left[\matrix{0&0&0&0&0&0&0&0&1279161\cr 7674966&0&0&0&0&0&0&0&0\cr 0&46049796&0&0&0&0&0&0&0\cr -20358&-162864&244296&0&0&0&0&0&-11310\cr -67860&-122148&-977184&1465776&0&0&0&0&0\cr 0&-407160&-732888&-5863104&8794656&0&0&0&0\cr 360&3204&864&12960&-62208&46656&0&0&100\cr 600&2160&19224&5184&77760&-373248&279936&0&0\cr 0&3600&12960&115344&31104&466560&-2239488&1679616&0}\right]$$ 將常數項移到第一行 (%i12) M:addcol(col(M,h*k),submatrix(M,h*k)); (M) $$\left[\matrix{1279161&0&0&0&0&0&0&0&0\cr 0&7674966&0&0&0&0&0&0&0\cr 0&0&46049796&0&0&0&0&0&0\cr -11310&-20358&-162864&244296&0&0&0&0&0\cr 0&-67860&-122148&-977184&1465776&0&0&0&0\cr 0&0&-407160&-732888&-5863104&8794656&0&0&0\cr 100&360&3204&864&12960&-62208&46656&0&0\cr 0&600&2160&19224&5184&77760&-373248&279936&0\cr 0&0&3600&12960&115344&31104&466560&-2239488&1679616}\right]$$ LLL化簡 (%i12) B: LLL(M); (M) $$\left[\matrix{ 100&360&3204&864&12960&-62208&46656&0&0\cr -11310&-20358&-162864&244296&0&0&0&0&0\cr 400&2040&14976&22680&57024&-171072&-186624&279936&0\cr 1279161&0&0&0&0&0&0&0&0\cr -22920&-109656&-457488&-491184&1426896&186624&-139968&0&0\cr 1400&8040&59256&121176&322704&-451008&-746496&-839808&1679616\cr -53360&-196668&-1128060&-794880&-859248&972000&1632960&1959552&1679616\cr -22620&7634250&-325728&488592&0&0&0&0&0\cr -267849&3713268&20770668&14244552&11153376&9020160&7231680&5598720&5038848}\right]$$ 第一列短向量$$b_1$$ (%i14) B[1]; (%o14) $$[100,360,3204,864,12960,-62208,46656,0,0]$$ 產生的方程式不需要再同餘$$N^{h-1}$$ (%i15) rx:sum(B[1][i+1]*(x/X)^i,i,0,h*k-1); (rx) $$x^6-8x^5+10x^4+4x^3+89x^2+60x+100$$ 將$$r(x)$$因式分解 (%i16) factor(rx); (%o16) $$(x-5)^2(x^2+x+2)^2$$ 得到$$r(x)$$的解 (%i17) x:5; (x) 5 驗證答案 (%i18) ev(mod(px,N),x=5); (%o18) 0 TOP 將Coppersmith和Howgrave-Graham方法寫成副程式，放入LLL.zip，提供將來範例直接使用。 111.3.6補充 發現ceiling指令在處理超大浮點數會出現錯誤，改用bigfloat numbers。  修正前 修正後 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正確

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

Coppersmith_Howgrave方法副程式
(%i2)
Coppersmith_Howgrave(px,N,h):=block
([ak,inv_ak,k,X,q_uv,M,B,i,rx,x],
px:expand(px),/*先expand()確保coeff()取得到係數,例子3(x^2+x+1),x^2係數為0*/
if (ak:coeff(px,x,hipow(px,x)))#1 then
(print("p(x)不是monic多項式，同乘",ak^"-1","≡",inv_ak:inv_mod(ak,N),"mod(",N,")"),
print("p(x)變成monic多項式，",inv_ak,"(",px,")=",px:polymod(inv_ak*px,N),"(mod",N,")")
),
if h<2 then (print("參數h要≥2"),return([])),
fpprec:100,/*設定小數點以下100為有效位數*/
print("參數h=",h),
print("p(x)最高次方k=",k:hipow(px,x)),
print("X=ceiling(",2^(-1/2),"(hk)"^"-1/(hk-1)","N"^"(h-1)/(hk-1)",")=ceiling(",
2^(-1/2),h*k,""^("-1"/(h*k-1)),N^((h-1)/(h*k-1)),")=",X:ceiling(bfloat(2^(-1/2)*(h*k)^(-1/(h*k-1))*N^((h-1)/(h*k-1))))-1),
print("q_uv=N"^"h-1-v","x"^"u","p(x)"^"v","=",q_uv:create_list((v:floor((i-1)/k),u: (i-1)-k*v,N^(h-1-v)*x^u*px^v),i,1,h*k)),
print("用",X,"x取代x,得到q_uv=",q_uv:ev(q_uv,x=x*X)),
M:augcoefmatrix(q_uv,create_list(x^i,i,1,h*k-1)),
print("產生矩陣M=",M:addcol(col(M,h*k),submatrix(M,h*k))),
print("LLL化簡B=",B: LLL(M)),
print("產生不需要同餘N"^(h-1),"的方程式"),
printList:["r(x)=",B[1][1]],
for i:2 thru h*k do
(if B[1][ i ]>=0 then printList:append(printList,["+"]),
printList:append(printList,[B[1][ i ],"(",x/X,")"^(i-1)])
),
apply(print,printList),/*再用apply(print,)將全部內容印在同一行*/
print("r(x)=",rx:sum(B[1][i+1]*(x/X)^i,i,0,h*k-1),"=",factor(rx)),
print("整數解為",x:sublist(solve(rx,x),lambda([x],integerp(rhs(x))))),
return(x)
)$二次同餘方程式 (%i5) px:x^2+14*x+19; N:35; h:3; (px) $$x^2+14x+19$$ (N) 35 (h) 3 (%i6) solution:Coppersmith_Howgrave(px,N,h); 參數$$h=3$$ $$p(x)$$最高次方$$k=2$$ $$\displaystyle X=ceiling(\frac{1}{\sqrt{2}}(hk)^{-1/(hk-1)}N^{(h-1)/(hk-1)})=ceiling(\frac{1}{\sqrt{2}}6^{-1/5}35^{2/5})=2$$ $$q_{uv}=N^{h-1-v}x^{u}p(x)^{v}=[1225,1225x,35(x^2+14x+19),35x(x^2+14x+19),(x^2+14x+19)^2,x(x^2+14x+19)^2]$$ 用$$2x$$取代$$x$$,得到$$q_{uv}=[1225,2450x,35(4x^2+28x+19),70x(4x^2+28x+19),(4x^2+28x+19)^2,2x(4x^2+28x+19)^2]$$ 產生矩陣$$M=\left[\matrix{1225&0&0&0&0&0\cr 0&2450&0&0&0&0\cr 665&980&140&0&0&0\cr 0&1330&1960&280&0&0\cr 361&1064&936&224&16&0\cr 0&722&2128&1872&448&32}\right]$$ LLL化簡$$B=\left[\matrix{3&16&-96&-64&-16&64\cr 49&100&0&160&0&64\cr 115&-166&16&104&96&64\cr 61&32&148&-128&48&128\cr 21&-74&-56&16&224&-128\cr -201&8&132&-32&-48&32}\right]$$ 產生不需要同餘$$N^2$$的方程式 $$\displaystyle r(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$$ $$r(x)=2x^5-x^4-8x^3-24x^2+8x+3=(x-3)(2x-1)(x^3+3x^2+5x+1)$$ 整數解為$$[x=3]$$ (solution) $$[x=3]$$ 驗證答案 (%i7) ev(mod(px,N),solution); (%o7) 0 三次同餘方程式 (%i10) px:x^3-4*x^2-3*x-10; N:1131; h:3; (px) $$x^3-4x^2-3x-10$$ (N) 1131 (h) 3 (%i11) solution:Coppersmith_Howgrave(px,N,h); 參數$$h=3$$ $$p(x)$$最高次方$$k=3$$ $$\displaystyle X=ceiling(\frac{1}{\sqrt{2}}(hk)^{-1/(hk-1)} N^{(h-1)/(hk-1)})=ceiling(\frac{1}{\sqrt{2}} 9 ^{-1/8} 1131^{1/4})=3$$ $$q_{uv}=N^{h-1-v} x^u p(x)^v =[1279161,1279161x,1279161x^2,1131(x^3-4x^2-3x-10),$$ $$1131x(x^3-4x^2-3x-10),1131x^2(x^3-4x^2-3x-10),(x^3-4x^2-3x-10)^2,x(x^3-4x^2-3x-10)^2,x^2(x^3-4x^2-3x-10)^2]$$ 用$$3x$$取代$$x$$得到$$q_{uv}=1279161,3837483x,11512449x^2,1131(27x^3-36x^2-9x-10),$$ $$3393x(27x^3-36x^2-9x-10),10179x^2(27x^3-36x^2-9x-10),(27x^3-36x^2-9x-10)^2,3x(27x^3-36x^2-9x-10)^2,9x^2(27x^3-36x^2-9x-10)^2]$$ 產生矩陣$$M=\left[\matrix{1279161&0&0&0&0&0&0&0&0\cr 0&3837483&0&0&0&0&0&0&0\cr 0&0&11512449&0&0&0&0&0&0\cr -11310&-10179&-40716&30537&0&0&0&0&0\cr 0&-33930&-30537&-122148&91611&0&0&0&0\cr 0&0&-101790&-91611&-366444&274833&0&0&0\cr 100&180&801&108&810&-1944&729&0&0\cr 0&300&540&2403&324&2430&-5832&2187&0\cr 0&0&900&1620&7209&972&7290&-17496&6561}\right]$$ LLL化簡$$B=\left[\matrix{100&180&801&108&810&-1944&729&0&0\cr 100&480&1341&2511&1134&486&-5103&2187&0\cr 0&300&1440&4023&7533&3402&1458&-15309&6561\cr -10710&-9099&-35910&31185&4860&-11664&4374&0&0\cr -1020&-3108&-13203&-21114&-43335&-39609&-37908&-15309&39366\cr -10410&-40689&-60804&-76221&100845&-2916&-28431&13122&0\cr 1542&18561&31473&86157&29808&100602&181521&269001&426465\cr 1222511&-52875&-208521&136539&-9963&-13608&26973&4374&-6561\cr -225150&3376488&-1106784&-423009&379647&-50787&-80190&54675&59049}\right]$$ 產生不需要同餘$$N^2$$的方程式 $$\displaystyle r(x)=100 + 180\left(\frac{x}{3}\right)+801\left(\frac{x}{3}\right)^2+108\left(\frac{x}{3}\right)^3+810\left(\frac{x}{3}\right)^4-1944\left(\frac{x}{3}\right)^5+729\left(\frac{x}{3}\right)^6+0\left(\frac{x}{3}\right)^7+0\left(\frac{x}{3}\right)^8$$ $$r(x)=x^6-8x^5+10x^4+4x^3+89x^2+60x+100=(x-5)^2(x^2+x+2)^2$$ 整數解為$$[x=5]$$ (solution) $$[x=5]$$ 驗證答案 (%i12) ev(mod(px,N),solution); (%o12) 0 TOP  bugmens 發私訊 加為好友 目前離線 10# 大 中 小 發表於 2022-2-22 23:51 只看該作者 1-1.刻板訊息(Stereotyped Messages) 銀行要傳送底下的訊息給客戶 Your pin no is ****，其中****為四位數密碼 將明文按英文字母轉換成數字(空白$$=00,A=01,B=02,...,Z=26$$，不分大小寫) 設明文$$M=B+x$$，其中$$B=25152118001609140014150009190000$$，密碼$$0\le x <10000$$ 採用RSA方案將明文加密，其中公鑰$$e=3$$，$$N=54957464841358314276864542898551$$ 得到密文$$C\equiv M^e \equiv (B+x)^3\equiv 37393323096087665763922106857101 \pmod{N}$$要如何找出密碼$$x$$呢？ 參考資料： Cryptanalytic Attacks on RSA，https://books.google.com.tw/book ... e&q&f=false 請下載LLL.zip，解壓縮後將LLL.mac放到C:\maxima-5.45.1\share\maxima\5.45.1\share目錄下 要先載入LLL.mac才能使用Coppersmith_Howgrave指令 (%i1) load("LLL.mac"); (%o1) C:/maxima-5.45.1/share/maxima/5.45.1/share/LLL.mac 明文訊息 (%i2) m:"Your pin no is"; (m) Your pin no is 這個範例不區分大小寫，統一轉成大寫字母 (%i3) m:supcase(m); (m) YOUR PIN NO IS 明文訊息轉成list (%i4) mlist:charlist(m); (mlist) [Y,O,U,R, ,P,I,N, ,N,O, ,I,S] 明文轉成數字B (%i5) B:0; (B) 0 將明文訊息按照字母順序轉換成數字(空白=00,A=01,B=02,...,Z=26) (%i7) for i:1 thru length(mlist) do (if mlist[ i ]=" " then (B:B*100+0)/*空白就補上00*/ else/*其他就乘100倍再加上英文字母的順序*/ (B:B*100+cint(mlist[ i ])-cint("A")+1) )$ B; (%o7)　2515211800160914001415000919 最後四位數為密碼x (%i8)　B:B*10000; (B)　25152118001609140014150009190000 公鑰e (%i9)　e:3; (e)　3 公鑰N (%i10)　N:54957464841358314276864542898551; (N)　54957464841358314276864542898551 密文C (%i11)　C:37393323096087665763922106857101; (C)　37393323096087665763922106857101 明文M，其中x為四位數密碼 (%i12)　M:B+x; (M)　$$x+25152118001609140014150009190000$$ 產生方程式p(x)≡(B+x)^e-C(mod N) (%i13)　px:M^e-C; (px)　$$(x+25152118001609140014150009190000)^3-37393323096087665763922106857101$$ 方程式p(x)同餘N (%i14)　px:polymod(px,N); (px)　$$x^3+20498889163469105765585484671449x^2-23112443404493616937655279863053x+18283973072868139826273442498263$$ 參數h (%i15)　h:3; (h)　3 呼叫Coppersmith_Howgrave副程式，找符合p(x)≡0(mod N)的較小的解x (%i16)　x:Coppersmith_Howgrave(px,N,h); 參數$$h=3$$ $$p(x)$$最高次方$$k=3$$ $$\displaystyle X=ceiling(\frac{1}{\sqrt{2}}(hk)^{-1/(hk-1)}N^{(h-1)/(hk-1)})$$ $$=ceiling(\frac{1}{\sqrt{2}}9^{-1/8}54957464841358314276864542898551^{1/4})=46260610$$ $$q_{uv}=N^{h-1-v}x^u p(x)^v=$$ $$[3020322941789135243826751301254310584993059920451586964677899601,$$ $$3020322941789135243826751301254310584993059920451586964677899601x,$$ $$3020322941789135243826751301254310584993059920451586964677899601x^2,$$ $$54957464841358314276864542898551(x^3+20498889163469105765585484671449x^2-23112443404493616937655279863053x+18283973072868139826273442498263),$$ $$54957464841358314276864542898551x(x^3+20498889163469105765585484671449x^2-23112443404493616937655279863053x+18283973072868139826273442498263),$$ $$54957464841358314276864542898551x^2(x^3+20498889163469105765585484671449x^2-23112443404493616937655279863053x+18283973072868139826273442498263),$$ $$(x^3+20498889163469105765585484671449x^2-23112443404493616937655279863053x+18283973072868139826273442498263)^2,$$ $$x(x^3+20498889163469105765585484671449x^2-23112443404493616937655279863053x+18283973072868139826273442498263)^2,$$ $$x^2(x^3+20498889163469105765585484671449x^2-23112443404493616937655279863053x+18283973072868139826273442498263)^2]$$ 用$$46260610x$$取代$$x$$,得到$$q_{uv}=$$ $$[3020322941789135243826751301254310584993059920451586964677899601,$$ $$139721981684159887751924249514318172791235797686641888454048089061016610x,$$ $$6463624103118063744935544456324562407407970654820642611436221569296955598732100x^2,$$ $$54957464841358314276864542898551(98999742604948264981000x^3+43868525531133392517784211693380792380148972900x^2-1069195730482351460642265216185548242330x+18283973072868139826273442498263),$$ $$2542365847614788847019462641858137376110x(98999742604948264981000x^3+43868525531133392517784211693380792380148972900x^2-1069195730482351460642265216185548242330x+18283973072868139826273442498263),$$ $$117611394953827177084317023684568968482648027100x^2(98999742604948264981000x^3+43868525531133392517784211693380792380148972900x^2-1069195730482351460642265216185548242330x+18283973072868139826273442498263),$$ $$(98999742604948264981000x^3+43868525531133392517784211693380792380148972900x^2-1069195730482351460642265216185548242330x+18283973072868139826273442498263)^2,$$ $$46260610x(98999742604948264981000x^3+43868525531133392517784211693380792380148972900x^2-1069195730482351460642265216185548242330x+18283973072868139826273442498263)^2,$$ $$2140044037572100x^2(98999742604948264981000x^3+43868525531133392517784211693380792380148972900x^2-1069195730482351460642265216185548242330x+18283973072868139826273442498263)^2]$$ 產生矩陣$$M=\left[\matrix{ 3020322941789135243826751301254310584993059920451586964677899601&0&0&0&0&0&0&0&0\cr 0&139721981684159887751924249514318172791235797686641888454048089061016610&0&0&0&0&0&0&0\cr 0&0&6463624103118063744935544456324562407407970654820642611436221569296955598732100&0&0&0&0&0&0\cr 1004840807312492934121310085993087816338401741664749320802716913&-58760286766514250464246726367461673333231803685743085020341021553863830&2410902949519492989179980080581154246553453535301351223201730247704151548267900&5440774873514967046498526949032608069078072148942531000&0&0&0&0&0\cr 0&46484548699168383753141618577192698167382430994473719077419374052696930&-2718286709593876800168836752261861160016036509902723416322838065104888632736300&111529841095570952570189278315533349949653158149697041409558194314245150155317497419000&251693564521475219700920220763687359166473755234092339003910000&0&0&0&0\cr 0&0&2150403578398235925134420691768266304768993361087260873490057469495932126927300&-125749601340705593040658491150052576997649458730371025900378445822971862132447207143000&5159438482284180564178023830336345244014424384431456450801421899475512335726582174276365590000&11643497827837801763248586973862843084330167466119804398647668985100000&0&0&0\cr 334303671329367207597382428251924280469672863044332310758017169&-39098291891529790146672600165213743993545305783624348258638047456145580&2747361389197032065525895040706053126300958522505044634704406065907531371974300&-93808080400887705413187047147355847439306195234682022660264660430139194466387149708000&1924447532275702298105139918003157179495823605879799776741463766795883123756267581643242950000&8685945472081614468358429342848175207711673102374196684328376029800000&9800949035846008678895673107522190930361000000&0&0\cr 0&15465091760936037937451545534215250888338153144877269738375436628413090&-1808710832860221925357063953928888577525241908186990361297033844530242779603800&127094613754702113540787875379036848315089384835782092878652994296582604861668022323000&-4339619022274109793914334845135441389609242568335483524297665952941101520923694041653401880000&89026116756068676488745616742176033049356292460399124349923926144875298793670429650041221245199500000&401817135965233455091086640042055722495618701836422786877008115447926178000000&453397880977148227551007964314572140974967380210000000&0\cr 0&0&715424578566875285969650341855573377397564850755440873231788107446732875384900&-83672066441721911002392246317762282218349981070294168177721176838614194432567346318000&5879474360006910140686106995638225815533507147028029443643143494486432216289728330155597030000&-200753423138003906273451417680221051302571222849166152478959848559286650429857849820251779543946800000&4118402467066958176262030365319276016243382196556464335893334277056879696127458214572993419947888441695000000&18588305818204638424921273531195923376638043474361038338830390395571488229248580000000&20974462546710273066928434544050339130507985738616528100000000}\right]$$ LLL化簡$$B=\left[\matrix{ 1346829011992131838415424923205840084705445702496636688958&-45179677717016066583753308148255943279532835707102039947418400&-57317453167676354735698331555650210546427932428564618523281700&55022492206313287028619713807534065142711418176206799219594000&-9126018929197534844882170642391266050994818115932677074230000&-74312694674165829957248058752411116787238498594388701682800000&-19823407733951640707057856074266278764703362315244543316000000&138583699736138999822205248506077392755142831146437181570000000&20974462546710273066928434544050339130507985738616528100000000\cr -5902801572552400483890393706301403464838435984190741057521&198017000397961977217885428384176729067567197716265205355728090&42767563064370999055058464552273491314630668309914422404759500&-118669599523559088891420124095064243299234055073696904508477000&5351963749137648019221242354483616465414282780748646299580000&-112004086186351949887374756082813158190757018854244406606700000&-81397469992098637889082971258651279103671999211513531483000000&-10896835906406582990864300928074561497704329125231160360000000&0\cr 3508846630479685748619833227116965930963020713923238512016&-117708907048737798457372393976462193778029056413142461742828970&-19527888444159534716576393306673687254846408168280511459649900&27139572631435639962886919071578980327487934016822772654740000&152842267767879348291763951826981942119544813261287552570070000&-27976405711844657161410593106590342431253966526607082103400000&113524558112017051054823008390937950572260639715265074131000000&-73696712976382536265834206929658681977733154502070358350000000&-20974462546710273066928434544050339130507985738616528100000000\cr -698639478405741507601710852229901400525255812179741745660&23434582306738882194913520923528306099741489318995435888835520&77832343453161261306864164010036521096392268014746035430400000&-19810469901945597112216075834712042329629980808126434227417000&11981172299793958495319504252438495583021639688484388874570000&123052851048114992637170087912139575579626631163057082528500000&-77828623800639953659282136255768504523687584641815030167000000&45046935686004396852036235081258646064208160740318079740000000&83897850186841092267713738176201356522031942954466112400000000\cr 2608388682960311335109469583103966794580680761470012241110&-87504293274733197882640504831875268439796045643230655421800670&67355084330066865588347641681926665747584588920990302572315700&49518826646218754489406268633116221438926982129998391470769000&-76798282830980653021742983335907095096227676638334916897480000&8588117181290281381087324090049898257206127303677712526400000&128047976903282825900283462166286459364396690101948932088000000&88906907910860169021868087433507208597965866101930374390000000&-41948925093420546133856869088100678261015971477233056200000000\cr -1995198218937024623232349557084188775094976064244671057536&66932114210862830110104110182574512142599015426308136347603390&-7269506494572805968382600910891268087690791621484198916104800&8746942221093256881071752182172494956975331200299995572349000&135289672986284673880862945002578814813571416764191759148860000&57336532483012033414667813522314757646899794385904686577900000&98003299188098351389493461699129078727854830331097773587000000&76794339087563318362316609668062911023749796992816963810000000&-20974462546710273066928434544050339130507985738616528100000000\cr 1080486934579740147709503727342917433192987867804798211748&-36248047630075260993070370343206373336745272044257160933612290&50432291648410244801921487663386649765799516063041448619617700&-110728984816423069966245765896893991877601482453715569174801000&47751944909992951034160485499982734778235628595949271138960000&92499399504781570519595347939458299088542884224606869328000000&-23368916165677269442994314666846991564283577282956230451000000&47762871511471852576044187070952438440777872791839177960000000&-83897850186841092267713738176201356522031942954466112400000000\cr -1351209723281976538802605297703889071606362629555587092791&45325239305457343576462953756357480589591441740795953594944820&104141687489491357694257317408495876883875779940487417687370100&56013394445295195456052555118633049318801173303376655543288000&43928806144132011144005796648574152800734722604776425309230000&-52583333463842986422341946819648968524622281916459256843100000&-190189161265649279450477135329996455520381986431990693226000000&28230740167810844364671917022661043622253814284451493460000000&-41948925093420546133856869088100678261015971477233056200000000\cr 3020322941789135243826751301254310584993059920451586964677899601&0&0&0&0&0&0&0&0}\right]$$ 產生不需要同餘$$N^2$$的方程式 $$r(x)= 1346829011992131838415424923205840084705445702496636688958$$ $$\displaystyle -45179677717016066583753308148255943279532835707102039947418400\left(\frac{x}{46260610}\right)$$ $$\displaystyle -57317453167676354735698331555650210546427932428564618523281700\left(\frac{x}{46260610}\right)^2$$ $$\displaystyle +55022492206313287028619713807534065142711418176206799219594000\left(\frac{x}{46260610}\right)^3$$ $$\displaystyle -9126018929197534844882170642391266050994818115932677074230000\left(\frac{x}{46260610}\right)^4$$ $$\displaystyle -74312694674165829957248058752411116787238498594388701682800000\left(\frac{x}{46260610}\right)^5$$ $$\displaystyle -19823407733951640707057856074266278764703362315244543316000000\left(\frac{x}{46260610}\right)^6$$ $$\displaystyle +138583699736138999822205248506077392755142831146437181570000000\left(\frac{x}{46260610}\right)^7$$ $$\displaystyle +20974462546710273066928434544050339130507985738616528100000000\left(\frac{x}{46260610}\right)^8$$ $$r(x)= x^8+305655817x^7-2022600838087156x^6-350756908723576394560428x^5$$ $$-1992672579437965292192928201903x^4+555784194569846483233547842537557231074x^3$$ $$-26783305465388245970449493154965416028246066377x^2$$ $$-976633851499495285162761756670652273706136510242775440x$$ $$+1346829011992131838415424923205840084705445702496636688958$$ $$=(x-1379)(x^7+305657196x^6-2022179336813872x^5-350759697308881860889916x^4$$ $$-1993156277060554240279095396067x^3+555781446007340416729250497665006054681x^2$$ $$-26782539042774201848014823518529135984896661278x-976670784620835270787110169112284325384659682738677802)$$ 整數解為$$[x=1379]$$ (x)　$$[x=1379]$$ 驗算答案 (%i17)　mod((B+rhs(x[1]))^e-C,N); (%o17)　0 UID210 帖子1136 閱讀權限200 上線時間6704 小時 註冊時間2008-12-16 最後登入2024-6-15  查看詳細資料 TOP
17 12
﻿