# 用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

(%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,))
)\$

TOP

﻿