問題敘述
令\(N=p^8q^5=80171134270603235454533\)是未知分解的整數，\(r>s\)和\(gcd(r,s)=1\)，給定\(N\)為輸入，能在多項式時間\(\log N\)和\(r=\Omega(\log^3 max(p,q))\)情況下回復質因數\(p\)和\(q\)。
步驟1：將\(r\)和\(s\)表示成\(\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}\)
設矩陣\(M=\left[\matrix{\lfloor\;r^{1/3}\rfloor\;&-s\cr0&r}\right]\)，經LLL化簡後短的非零向量\(v=(\lfloor\;r^{1/3}\rfloor\;\cdot\alpha,\gamma)\)，其中\(\gamma=-s\cdot\alpha+r\cdot\beta\)，\(\beta\in\mathbb{Z}\) 從\(v\)向量得到\(\alpha,\beta\)值，符合\(\alpha>0\)且\(0\le\beta\le\alpha\) Case 1：\(\beta=0\)或(\(\beta\ne0\)和\(\displaystyle\lfloor\;\frac{r}{\alpha}\rfloor\;\le\frac{s}{\beta}\)) 　\(\displaystyle u=\lfloor\;\frac{r}{\alpha}\rfloor\;\) 　\(a=r-u\cdot\alpha\) 　\(b=s-u\cdot\beta\) Case 2：\(\beta\ne0\)和\(\displaystyle\lfloor\;\frac{r}{\alpha}\rfloor\;>\frac{s}{\beta}\) 　\(\displaystyle u=\lceil\;\frac{r}{\alpha}\rceil\;\) 　\(a=r-u\cdot\alpha\) 　\(b=s-u\cdot\beta\)	設矩陣\(M=\left[\matrix{\lfloor\;8^{1/3}\rfloor\;&-5\cr0&8}\right]=\left[\matrix{2&-5\cr0&8}\right]\)，經LLL化簡後\(B=\left[\matrix{2&3\cr4&-2}\right]\) 原本短的非零向量\(v=(2,3)\)無法求得合適的\(u,\alpha,\beta,a,b\) 改用\(v=(4,-2)=(\lfloor\;r^{1/3}\rfloor\;\cdot \alpha,\gamma)\)，其中\(\gamma=-s\cdot\alpha+r\cdot\beta\)，\(\beta\in\mathbb{Z}\) \(4=\lfloor\;8^{1/3}\rfloor\;\cdot \alpha\)，得\(\alpha=2\) \(-2=-5\cdot 2+8\cdot\beta\)，得\(\beta=1\) 符合\(\alpha>0\)且\(0\le\beta\le\alpha\) \(\displaystyle \lfloor\;\frac{r}{\alpha}\rfloor\;=\lfloor\;\frac{8}{2}\rfloor\;=4\)，\(\displaystyle \frac{s}{\beta}=\frac{5}{1}=5\) 符合Case 1:\(\beta=0\)或\((\beta\ne0\)和\(\displaystyle \lfloor\;\frac{r}{\alpha}\rfloor\;\le\frac{s}{\beta})\) 　\(\displaystyle u=\lfloor\;\frac{r}{\alpha}\rfloor\;=\lfloor\;\frac{8}{2}\rfloor\;=4\) 　\(a=r-u\cdot\alpha=8-4\cdot2=0\) 　\(b=s-u\cdot\beta=5-4\cdot1=1\) \(\cases{8=4\cdot2+0\cr5=4\cdot1+1}\)
步驟2：根據\(a,b\ge0\)(Case1)使用BDH方法
\(a,b\ge0\)(Case1) \(\displaystyle N=p^rq^s=p^{u\cdot \alpha+a}\cdot q^{u\cdot\beta+b}=(p^{\alpha}q^{\beta})^u\cdot p^aq^b=P^u\cdot Q\)，其中\(P=p^{\alpha}q^{\beta}\)和\(Q=p^aq^b\)	\(N=p^8q^5=P^4\cdot Q\)，其中\(P=p^2q^1=p^2q\)和\(Q=p^0q^1=q\)
步驟2-1.設同餘方程式，計算參數\(X\)
設同餘方程式\(f(x)=(V+x)^u\pmod{P^u}\) 其中\(V\)是使得\(P=V+x_0\)的整數和\(V\)的高位元和\(P\)相同，能找到上限\(X= P\cdot Q^{-1/u}\)較小的解\(x_0\)，其中\(|\;x_0|\;< P\cdot Q^{-1/u}\)	\(V=\lfloor\;N^{1/4}\rfloor\;=532113\) \(P=p^2q=61^2\cdot 53=197213\)，\(Q=q=53\) \(X=P\cdot Q^{-1/4}=73091\) 但這樣\(V\)和\(X\)所需的矩陣\(M\)要非常大才能找到較小的解\(x_0\) 設同餘方程式\(f(x)=(V+x)^4\pmod{P^4}\) 取\(V=197000\)，\(V\)的高位元和\(P\)相同，上限\(X=1000\) 只要維度9的矩陣\(M\)經LLL化簡就能找到較小的解\(x_0=213\)，其中\(|\;x_0|\;<1000\)
步驟2-2.產生矩陣\(M\)
\(g_{i,k}(xX)=N^{m-k}(xX)^i f(xX)^k\) \(g_{i,k}(xX)\)，\(i=0,1,\ldots,u-1\)和\(k=0,1,\ldots,m-1\) \(g_{j,m}(xX)\)，\(j=0,1,\ldots,d-um-1\) 注意到對所有\(i,k\)，\(g_{i,k}(x_0)\equiv 0\pmod{P^{um}}\) 注意到對所有\(j,m\)，\(g_{j,m}(x_0)\equiv 0\pmod{P^{um}}\)	原本矩陣\(M\)需要\(d=2\cdot u\cdot(u+1)=2\cdot 4\cdot5=40\)，改取維度\(d=9\)減少LLL執行時間 設\(P^c>Q\)，取\(c=1\) \(\displaystyle m=\lfloor\;\frac{d}{u+c}-\frac{1}{2}\rfloor\;=\lfloor\;\frac{9}{4+1}-\frac{1}{2}\rfloor\;=1\)太小，改取\(m=2\) \(i=0,k=0,g_{0,0}(xX)=N^2\cdot1\cdot1=N^2=\bbox[border:1px solid black]{N^2}\) \(i=1,k=0,g_{1,0}(xX)=N^2(xX)\cdot1=N^2Xx=\bbox[border:1px solid black]{N^2X}x\) \(i=2,k=0,g_{2,0}(xX)=N^2(xX)^2\cdot1=N^2X^2x^2=\bbox[border:1px solid black]{N^2X^2}x^2\) \(i=3,k=0,g_{3,0}(xX)=N^2(xX)^3\cdot1=N^2X^3x^3=\bbox[border:1px solid black]{N^2X^3}x^3\) \(i=0,k=1,g_{0,1}(xX)=N\cdot1\cdot f(xX)=N(V+Xx)^4\) \(=NV^4+4NV^3Xx+6NV^2X^2x^2+4NVX^3x^3+\bbox[border:1px solid black]{NX^4}x^4\) \(i=1,k=1,g_{1,1}(xX)=N(xX)f(xX)=NXx(V+Xx)^4\) \(=NV^4Xx+4NV^3X^2x^2+6NV^2X^3x^3+4NVX^4x^4+\bbox[border:1px solid black]{NX^5}x^5\) \(i=2,k=1,g_{2,1}(xX)=N(xX)^2f(xX)=NX^2x^2(V+Xx)^4\) \(=NV^4X^2x^2+4NV^3X^3x^3+6NV^2X^4x^4+4NVX^5x^5+\bbox[border:1px solid black]{NX^6}x^6\) \(i=3,k=1,g_{3,1}(xX)=N(xX)^3f(xX)=NX^3x^3(V+Xx)^4\) \(=NV^4X^3x^3+4NV^3X^4x^4+6NV^2X^5x^5+4NVX^6x^6+{NX^7}x^7\) \(j=0,g_{0,2}(xX)=1\cdot f(xX)^2=(V+Xx)^8\) \(=V^8+8V^7Xx+28V^6X^2x^2+56V^5X^3x^3+70V^4X^4x^4+56V^3X^5x^5+28V^2X^6x^6+8VX^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_{2,0}(xX)\cr g_{3,0}(xX)\cr g_{0,1}(xX)\cr g_{1,1}(xX)\cr g_{2,1}(xX)\cr g_{3,1}(xX)\cr g_{0,2}(xX)}&\left[\matrix{N^2&&&&&&&&\cr 0&N^2X&&&&&&&\cr 0&0&N^2X^2&&&&&&\cr 0&0&0&N^2X^3&&&&&\cr *&*&*&*&NX^4&&&&\cr 0&*&*&*&*&NX^5&&&\cr 0&0&*&*&*&*&NX^6&&\cr 0&0&0&*&*&*&*&NX^7&\cr *&*&*&*&*&*&*&*&X^8}\right]}\) *代表非零數字
步驟2-3.經LLL化簡後的短向量產生不需要同餘\(P^{um}\)的方程式，得到公鑰\(N\)的因數\(P\)和\(Q\)
矩陣\(M\)經LLL化簡為\(B\) \(B=LLL(M)\) lattice經LLL化簡後第一列\(b_1\)為整個lattice中較短向量 所形成的方程式不需要再同餘\(P^{um}\)	本範例第一列\(b_1\)無法得到正確答案 lattice經LLL化簡後第二列\(b_2\)為整個lattice中較短向量 \(b_2=[520814821077069868175677184373000000000000,\) 　\(-2430603060877548431773082696764000000000000,\) 　\(-68074195511300390211470172818000000000000,\) 　\(-817458291481540650461827996000000000000,\) 　\(-5507602630239396764545467000000000000,\) 　\(-22691467064000000000000000000000000,\) 　\(-57592556000000000000000000000000,\) 　\(-83528000000000000000000000000,\) 　\(-53000000000000000000000000]\) 產生不需要同餘\(P^{um}=P^8\)的方程式 \(h(x)=520814821077069868175677184373000000000000\) 　\(\displaystyle-2430603060877548431773082696764000000000000\left(\frac{x}{1000}\right)\) 　\(\displaystyle-68074195511300390211470172818000000000000\left(\frac{x}{1000}\right)^2\) 　\(\displaystyle-817458291481540650461827996000000000000\left(\frac{x}{1000}\right)^3\) 　\(\displaystyle-5507602630239396764545467000000000000\left(\frac{x}{1000}\right)^4\) 　\(\displaystyle-22691467064000000000000000000000000\left(\frac{x}{1000}\right)^5\) 　\(\displaystyle-57592556000000000000000000000000\left(\frac{x}{1000}\right)^6\) 　\(\displaystyle-83528000000000000000000000000\left(\frac{x}{1000}\right)^7\) 　\(\displaystyle-53000000000000000000000000\left(\frac{x}{1000}\right)^8\) \(h(x)=-53(-213+x)(197000+x)^4(394213+x)(77701967369+394000x+x^2)\) 得到正整數解\(x=213\) 得到因數\(P=V+x=197000+213=197213\) \(N\)可分解成\(80171134270603235454533=197213^4\cdot53\) \(P=197213,Q=53\)
步驟3.從\(P,Q\)求出\(N\)的質因數\(p,q\)
已知\(P=p^{\alpha}q^{\beta}\)，\(Q=p^aq^b\)，\(\gamma=a\beta-b\alpha\)，則\(\cases{p=Q^{\displaystyle\frac{\beta}{\gamma}} \cdot P^{\displaystyle\frac{-b}{\gamma}}\cr q=Q^{\displaystyle\frac{-\alpha}{\gamma}} \cdot P^{\displaystyle\frac{a}{\gamma}}}\)	\(\alpha=2,\beta=1,a=0,b=1,\gamma=a\beta-b\alpha=-2\) \(\cases{p=Q^{\displaystyle\frac{\beta}{\gamma}} \cdot P^{\displaystyle\frac{-b}{\gamma}}=53^{\displaystyle\frac{1}{-2}}\cdot 197213^{\displaystyle\frac{-1}{-2}}=61\cr q=Q^{\displaystyle\frac{-\alpha}{\gamma}} \cdot P^{\displaystyle\frac{a}{\gamma}}=53^{\displaystyle\frac{-2}{-2}}\cdot 197213^{\displaystyle\frac{0}{-2}}=53}\)

請下載LLL.zip，解壓縮後將LLL.mac放到C:\maxima-5.49.0\share\maxima\5.49.0\share目錄下
要先載入LLL.mac才能使用LLL指令
(%i1)　load("LLL.mac");
(%o1)　C:/maxima-5.49.0/share/maxima/5.49.0/share/LLL.mac

要因數分解的公鑰\(N\)
(%i2)　N:80171134270603235454533;
(%o2)　\(80171134270603235454533\)

\(N=p^rq^s\)，因數\(p\)的次方\(r\)，因數\(q\)的次方\(s\)
(%i4)
r:8;
s:5;
(%o3)　\(8\)
(%o4)　\(5\)

將\(r,s\)表示成\(\cases{r=u\alpha+a\cr s=u\beta+b}\)
(%i10)
u:4;
alpha:2;
beta:1;
a:0;
b:1;
gamma:a*beta-b*alpha;
(%o5)　\(4\)
(%o6)　\(2\)
(%o7)　\(1\)
(%o8)　\(0\)
(%o9)　\(1\)
(%o10)　\(-2\)

假設\(Q< P^c\)
(%i11)　c:1;
(%o11)　\(1\)

矩陣維度\(d\)，按照BDH方法維度\(d=40\)，改成\(d=9\)但解的上限\(X\)也變小
(%i13)
d:2*u*(u+1);
d:9;
(%o12)　\(40\)
(%o13)　\(9\)

參數\(m\)，原本\(m=1\)無法得到正確答案，改取\(m=2\)
(%i15)
m:floor(d/(u+c)-1/2);
m:2;
(%o14)　\(1\)
(%o15)　\(2\)

希望能找到\(|\;x|\;<X\)，\(f(x)\equiv0\pmod{P^u}\)
(%i16)　X:1000;
(%o16)　\(1000\)

\(V\)的高位元和\(P\)相同，當作\(P\)的近似值
(%i17)　V:197000;
(%o17)　\(197000\)

同餘方程式\(f(x)=(V+x)^u \equiv0\pmod{P^u}\)
(%i18)　fx: ('V+x)^u;
(%o18)　\((x+V)^4\)

將\(x\)以\(Xx\)代替，\(f(Xx)=(V+Xx)^u \equiv0\pmod{P^u}\)
(%i19)　fXx:subst(x=x*'X,fx);
(%o19)　\((Xx+V)^4\)

以x升冪排序顯示
(%i20)　powerdisp:true;
(%o20)　true

\(g(xX)\)多項式
(%i21)　gxX:[];
(%o21)　\([]\)

產生\(g_{i,k}(xX)=N^{m-k}(Xx)^if^k(xX)\)多項式，\(i=0,\ldots,u-1\)，\(k=0,\ldots,m-1\)
(%i22)
for k:0 thru m-1 do
  (for i:0 thru u-1 do
     (print("i=",i,",k=",k,",g",i,",",k,"(xX)=N"^(m-k),"*","(xX)"^i,"*","f(xX)"^k,"=",gik:'N^(m-k)*(x*'X)^i*fXx^k,"=",expand(gik)),
      gxX:append(gxX,[gik])
     )
  );
\(i=0,k=0,g0,0(xX)=N^2*1*1=N^2=N^2\)
\(i=1,k=0,g1,0(xX)=N^2*(xX)*1=N^2Xx=N^2Xx\)
\(i=2,k=0,g2,0(xX)=N^2*(xX)^2*1=N^2X^2x^2=N^2X^2x^2\)
\(i=3,k=0,g3,0(xX)=N^2*(xX)^3*1=N^2X^3x^3=N^2X^3x^3\)
\(i=0,k=1,g0,1(xX)=N*1*f(xX)=N(V+Xx)^4=NV^4+4NV^3Xx+6NV^2X^2x^2+4NVX^3x^3+NX^4x^4\)
\(i=1,k=1,g1,1(xX)=N*(xX)*f(xX)=NXx(V+Xx)^4=NV^4Xx+4NV^3X^2x^2+6NV^2X^3x^3+4NVX^4x^4+NX^5x^5\)
\(i=2,k=1,g2,1(xX)=N*(xX)^2*f(xX)=NX^2x^2(V+Xx)^4=NV^4X^2x^2+4NV^3X^3x^3+6NV^2X^4x^4+4NVX^5x^5+NX^6x^6\)
\(i=3,k=1,g3,1(xX)=N*(xX)^3*f(xX)=NX^3x^3(V+Xx)^4=NV^4X^3x^3+4NV^3X^4x^4+6NV^2X^5x^5+4NVX^6x^6+NX^7x^7\)
(%o22)　done

產生\(g_{j,m}(xX)=x^jf^m(xX)\)多項式，\(j=0,\ldots,d-mu-1\)
(%i23)
for j:0 thru d-m*u-1 do
  (print("j=",j,",g",j,",",m,"(xX)=","(xX)"^j,"*f(xX)"^m,"=",gim: (x*'X)^j*fXx^m,"=",expand(gim)),
   gxX:append(gxX,[gim])
  );
\(j=0,g0,2(xX)=1*f(xX)^2=(V+Xx)^8=V^8+8V^7Xx+28V^6X^2x^2+56V^5X^3x^3+70V^4X^4x^4+56V^3X^5x^5+28V^2X^6x^6+8VX^7x^7+X^8x^8\)
(%o23)　done

全部的\(g(xX)\)多項式
(%i24)　gxX;
(%o24)　\([N^2,N^2Xx,N^2X^2x^2,N^2X^3x^3,N(V+Xx)^4,NXx(V+Xx)^4,NX^2x^2(V+Xx)^4,NX^3x^3(V+Xx)^4,(V+Xx)^8]\)

\(x^1,\ldots,x^{d-1}\)
(%i25)　xpower:create_list(x^i,i,1,d-1);
(%o25)　\([x,x^2,x^3,x^4,x^5,x^6,x^7,x^8]\)

取\(g(xX)\)多項式係數(常數項在最後一行)
(%i26)　M:augcoefmatrix(gxX,xpower);
(%o26)　\(\left[\matrix{0&0&0&0&0&0&0&0&N^2\cr
N^2X&0&0&0&0&0&0&0&0\cr
0&N^2X^2&0&0&0&0&0&0&0\cr
0&0&N^2X^3&0&0&0&0&0&0\cr
4NV^3X&6NV^2X^2&4NVX^3&NX^4&0&0&0&0&NV^4\cr
NV^4X&4NV^3X^2&6NV^2X^3&4NVX^4&NX^5&0&0&0&0\cr
0&NV^4X^2&4NV^3X^3&6NV^2X^4&4NVX^5&NX^6&0&0&0\cr
0&0&NV^4X^3&4NV^3X^4&6NV^2X^5&4NVX^6&NX^7&0&0\cr
8V^7X&28V^6X^2&56V^5X^3&70V^4X^4&56V^3X^5&28V^2X^6&8VX^7&X^8&V^8}\right]\)

將常數項移到第一行
(%i27)　M:addcol(col(M,d),submatrix(M,d));
(%o27)　\(\left[\matrix{N^2&0&0&0&0&0&0&0&0\cr
0&N^2X&0&0&0&0&0&0&0\cr
0&0&N^2X^2&0&0&0&0&0&0\cr
0&0&0&N^2X^3&0&0&0&0&0\cr
NV^4&4NV^3X&6NV^2X^2&4NVX^3&NX^4&0&0&0&0\cr
0&NV^4X&4NV^3X^2&6NV^2X^3&4NVX^4&NX^5&0&0&0\cr
0&0&NV^4X^2&4NV^3X^3&6NV^2X^4&4NVX^5&NX^6&0&0\cr
0&0&0&NV^4X^3&4NV^3X^4&6NV^2X^5&4NVX^6&NX^7&0\cr
V^8&8V^7X&28V^6X^2&56V^5X^3&70V^4X^4&56V^3X^5&28V^2X^6&8VX^7&X^8}\right]\)

將\(N=80171134270603235454533,V=197213,X=1000\)代入矩陣\(M\)
(%i28)　M:ev(M,[N=N,V=V,X=X]);
(%o28)　\(\left[\matrix{6427410770235092574143943139305425635110248089&0&0&0&0&0&0&0&0\cr
0&6427410770235092574143943139305425635110248089000&0&0&0&0&0&0&0\cr
0&0&6427410770235092574143943139305425635110248089000000&0&0&0&0&0&0\cr
0&0&0&6427410770235092574143943139305425635110248089000000000&0&0&0&0&0\cr
120748830390373400001175677184373000000000000&2451752901327378680226917303236000000000000&18668169299447045788529827182000000000000&63174853805235349538172004000000000000&80171134270603235454533000000000000&0&0&0&0\cr
0&120748830390373400001175677184373000000000000000&2451752901327378680226917303236000000000000000&18668169299447045788529827182000000000000000&63174853805235349538172004000000000000000&80171134270603235454533000000000000000&0&0&0\cr
0&0&120748830390373400001175677184373000000000000000000&2451752901327378680226917303236000000000000000000&18668169299447045788529827182000000000000000000&63174853805235349538172004000000000000000000&80171134270603235454533000000000000000000&0&0\cr
0&0&0&120748830390373400001175677184373000000000000000000000&2451752901327378680226917303236000000000000000000000&18668169299447045788529827182000000000000000000000&63174853805235349538172004000000000000000000000&80171134270603235454533000000000000000000000&0\cr
2268453123948987361000000000000000000000000&92119923815187304000000000000000000000000&1636648392655612000000000000000000000000&16615719722392000000000000000000000000&105429693670000000000000000000000000&428140888000000000000000000000000&1086652000000000000000000000000&1576000000000000000000000000&1000000000000000000000000}\right]\)

LLL化簡
(%i29)　B: LLL(M);
(%o29)　\(\left[\matrix{2268453123948987361000000000000000000000000&92119923815187304000000000000000000000000&1636648392655612000000000000000000000000&16615719722392000000000000000000000000&105429693670000000000000000000000000&428140888000000000000000000000000&1086652000000000000000000000000&1576000000000000000000000000&1000000000000000000000000\cr
520814821077069868175677184373000000000000&-2430603060877548431773082696764000000000000&-68074195511300390211470172818000000000000&-817458291481540650461827996000000000000&-5507602630239396764545467000000000000&-22691467064000000000000000000000000&-57592556000000000000000000000000&-83528000000000000000000000000&-53000000000000000000000000\cr
119574028217671068321357761887635110248089&-1120941543841003168053234143016000000000000&2618519389228227254415838318708000000000000&39977022196844180948953767576000000000000&287653869286346057041819502000000000000&1202647754392000000000000000000000000&3052405468000000000000000000000000&4426984000000000000000000000000&2809000000000000000000000000\cr
-241520619786717295077270256278597856642032&1006233591109786490302081721964050089220000&791289620910282234486801424154248089000000&-1025261299321869239983536773032000000000000&295501763176439064773555173486000000000000&985527115520611944767267972000000000000000&1714483878272561581454944000000000000000000&6207338904904808000000000000000000000000&3938666817833000000000000000000000000\cr
146111802828159872978714311180467622752981&-337364242705630748590601841116939841131000&-899218919995713091129794664660248089000000&-2698981263760596036060949910100000000000000&-3289903627281272224831697418325000000000000&-1009722386745134958108177997000000000000000&-1714560548593106805454944000000000000000000&-6207450101888920000000000000000000000000&-3938737374295000000000000000000000000\cr
61367641518645839679950446956111346617966&-57506707444030967438209001123160337309000&-542612286676673217701391991592248089000000&-3026902524618602725326328336604000000000000&2590332438445698909444733467517000000000000&-961953111791700696190903414000000000000000&-1714408988253107429454944000000000000000000&-6207230289938232000000000000000000000000&-3938597899707000000000000000000000000\cr
15067948572848914227471586284476558432910&-141458761630094005226905014839668317681000&335539551509200464614265223688160566000000&-94901188582953634568900965644267000000000&780356555960664279505166852075000000000000&-2333400442619330164545029877000000000000000&1004715999866625459367336000000000000000000&3758047457599007913741000000000000000000000&1172394756143066893000000000000000000000000\cr
-203445131193957092545439571131643721426395&1241053695755686421865190490359020206491000&-1100111943534622115960142187693663193000000&-1156898039491760619610370540935110000000000&450136837007525240038159764818000000000000&-1635079766422598279193272752000000000000000&-199868442363979553097839000000000000000000&846535899130441456508000000000000000000000&-3865583546108321988000000000000000000000000\cr
-233825991062131604151461386720904468484216&929448995310335846542698455837482677551000&1028704530536093855735204722429708747000000&-1376103751198842125959550070103822000000000&829839950910549569092835862550000000000000&2286782227716711908322343822000000000000000&-3321284626741256170546210000000000000000000&4165942424452207105995000000000000000000000&-760406771341748937000000000000000000000000}\right]\)

找出\(N\)的因數\(P,Q\)
(%i30)
for i:1 thru d do
  (print("第",i,"列向量B[",i,"]=",B[ i ]),
   print("產生不需要同餘P"^"um","=P"^(u*m),"的方程式h(x)"),
   printList:["h(x)=",B[ i ][1]],
   for j:2 thru d do
    (if B[ i ][j]>=0 then printList:append(printList,["+"]),/*若係數為正則補印+號*/
     printList:append(printList,[B[ i ][j],"(",x/X,")"^(j-1)])
    ),
   apply(print,printList),/*再用apply(print,)將全部內容印在同一行*/
   print("h(x)=",hx:sum(B[ i ][j+1]*(x/X)^j,j,0,d-1),"=",factor(hx)),
   print("正整數解為",posIntRoot:sublist(solve(hx,x),lambda([x],integerp(rhs(x)) and rhs(x)>0))),
   if length(posIntRoot)>0 then/*若有正整數解*/
     (for root in posIntRoot do
        (x:rhs(root),
         print("當正整數解x=",x,"時，可能的因數P=V+x=",V,"+",x,"=",P: V+x),
         if mod(N,P^u)=0 then
            (print("N可被P"^u,"整除，N可分解成",N,"=",P,""^u,"*",Q:N/(P^u)),
             i:d/*將i設為d，直接結束for迴圈*/
            )
         else
           (print("N無法被P"^u,"整除"))
        )
     ),
   print("－－－－－－－－－")
  );
第1列向量\(B[1]=[2268453123948987361000000000000000000000000,92119923815187304000000000000000000000000,\)
　\(1636648392655612000000000000000000000000,16615719722392000000000000000000000000,\)
　\(105429693670000000000000000000000000,428140888000000000000000000000000,\)
　\(1086652000000000000000000000000,1576000000000000000000000000,1000000000000000000000000]\)
產生不需要同餘\(P^{um}=P^8\)的方程式\(h(x)\)
\(h(x)=2268453123948987361000000000000000000000000\)
\(\displaystyle+92119923815187304000000000000000000000000\left(\frac{x}{1000}\right)\)
\(\displaystyle+1636648392655612000000000000000000000000\left(\frac{x}{1000}\right)^2\)
\(\displaystyle+16615719722392000000000000000000000000\left(\frac{x}{1000}\right)^3\)
\(\displaystyle+105429693670000000000000000000000000\left(\frac{x}{1000}\right)^4\)
\(\displaystyle+428140888000000000000000000000000\left(\frac{x}{1000}\right)^5\)
\(\displaystyle+1086652000000000000000000000000\left(\frac{x}{1000}\right)^6\)
\(\displaystyle+1576000000000000000000000000\left(\frac{x}{1000}\right)^7\)
\(\displaystyle+1000000000000000000000000\left(\frac{x}{1000}\right)^8\)
\(h(x)=2268453123948987361000000000000000000000000\)
　\(+92119923815187304000000000000000000000x\)
　\(+1636648392655612000000000000000000x^2\)
　\(+16615719722392000000000000000x^3\)
　\(+105429693670000000000000x^4\)
　\(+428140888000000000x^5\)
　\(+1086652000000x^6+1576000x^7+x^8\)
\(=(197000+x)^8\)
正整數解為\([]\)
－－－－－－－－－
第2列向量\(B[2]=[520814821077069868175677184373000000000000,-2430603060877548431773082696764000000000000,\)
　\(-68074195511300390211470172818000000000000,-817458291481540650461827996000000000000,\)
　\(-5507602630239396764545467000000000000,-22691467064000000000000000000000000,\)
　\(-57592556000000000000000000000000,-83528000000000000000000000000,-53000000000000000000000000]\)
產生不需要同餘\(P^um=p^8\)的方程式\(h(x)\)
\(h(x)=520814821077069868175677184373000000000000\)
\(\displaystyle-2430603060877548431773082696764000000000000\left(\frac{x}{1000}\right)\)
\(\displaystyle-68074195511300390211470172818000000000000\left(\frac{x}{1000}\right)^2\)
\(\displaystyle-817458291481540650461827996000000000000\left(\frac{x}{1000}\right)^3\)
\(\displaystyle-5507602630239396764545467000000000000\left(\frac{x}{1000}\right)^4\)
\(\displaystyle-22691467064000000000000000000000000\left(\frac{x}{1000}\right)^5\)
\(\displaystyle-57592556000000000000000000000000\left(\frac{x}{1000}\right)^6\)
\(\displaystyle-83528000000000000000000000000\left(\frac{x}{1000}\right)^7\)
\(\displaystyle-53000000000000000000000000\left(\frac{x}{1000}\right)^8\)
\(h(x)=520814821077069868175677184373000000000000\)
　\(-2430603060877548431773082696764000000000x\)
　\(-68074195511300390211470172818000000x^2\)
　\(-817458291481540650461827996000x^3\)
　\(-5507602630239396764545467x^4\)
　\(-22691467064000000000x^5\)
　\(-57592556000000x^6\)
　\(-83528000x^7-53x^8\)
\(=-53(-213+x)(197000+x)^4(394213+x)(77701967369+394000x+x^2)\)
正整數解為\([x=213]\)
當正整數解\(x=213\)時，可能的因數\(P=V+x=197000+213=197213\)
\(N\)可被\(P^4\)整除，\(N\)可分解成\(80171134270603235454533=197213^4\cdot53\)
－－－－－－－－－
(%o30)　done

\(N=P^uQ\)的\(P,Q\)值
(%i32)
P;
Q;
(%o31)　\(197213\)
(%o32)　\(53\)

\(N=p^rq^s\)的質因數\(p,q\)
(%i34)
p: Q^(beta/gamma)*P^(-b/gamma);
q: Q^(-alpha/gamma)*P^(a/gamma);
(%o34)　\(61\)
(%o35)　\(53\)

問題敘述
令\(N=p^8q^3=28540809637096203437\)是未知分解的整數，\(r>s\)和\(gcd(r,s)=1\)，給定\(N\)為輸入，能在多項式時間\(\log N\)和\(r=\Omega(\log^3 max(p,q))\)情況下回復質因數\(p\)和\(q\)。
步驟1：將\(r\)和\(s\)表示成\(\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}\)
設矩陣\(M=\left[\matrix{\lfloor\;r^{1/3}\rfloor\;&-s\cr0&r}\right]\)，經LLL化簡後短的非零向量\(v=(\lfloor\;r^{1/3}\rfloor\;\cdot\alpha,\gamma)\)，其中\(\gamma=-s\cdot\alpha+r\cdot\beta\)，\(\beta\in\mathbb{Z}\) 從\(v\)向量得到\(\alpha,\beta\)值，符合\(\alpha>0\)且\(0\le\beta\le\alpha\) Case 1：\(\beta=0\)或(\(\beta\ne0\)和\(\displaystyle\lfloor\;\frac{r}{\alpha}\rfloor\;\le\frac{s}{\beta}\)) 　\(\displaystyle u=\lfloor\;\frac{r}{\alpha}\rfloor\;\) 　\(a=r-u\cdot\alpha\) 　\(b=s-u\cdot\beta\) Case 2：\(\beta\ne0\)和\(\displaystyle\lfloor\;\frac{r}{\alpha}\rfloor\;>\frac{s}{\beta}\) 　\(\displaystyle u=\lceil\;\frac{r}{\alpha}\rceil\;\) 　\(a=r-u\cdot\alpha\) 　\(b=s-u\cdot\beta\)	設矩陣\(M=\left[\matrix{\lfloor\;r^{1/3}\rfloor\;&-s\cr0&r}\right]=\left[\matrix{2&-3\cr0&8}\right]\)，經LLL化簡後\(B=\left[\matrix{2&-3\cr4&2}\right]\) 原本短的非零向量\(v=(2,-3)\)無法求得合適的\(u,\alpha,\beta,a,b\) 改用\(v=(4,2)=(\lfloor\;r^{1/3}\rfloor\;\cdot \alpha,\gamma)\)，其中\(\gamma=-s\cdot\alpha+r\cdot\beta\)，\(\beta\in\mathbb{Z}\) \(4=\lfloor\;8^{1/3}\rfloor\;\cdot \alpha\)，得\(\alpha=2\) \(2=-3\cdot 2+8\cdot\beta\)，得\(\beta=1\) 符合\(\alpha>0\)且\(0\le\beta\le\alpha\) \(\displaystyle \lfloor\;\frac{r}{\alpha}\rfloor\;=\lfloor\;\frac{8}{2}\rfloor\;=4\)，\(\displaystyle \frac{s}{\beta}=\frac{3}{1}=3\) 符合Case 2:\(\beta\ne0\)和\(\displaystyle \lfloor\;\frac{r}{\alpha}\rfloor\;>\frac{s}{\beta})\) 　\(\displaystyle u=\lceil\;\frac{r}{\alpha}\rceil\;=\lceil\;\frac{8}{2}\rceil\;=4\) 　\(a=r-u\cdot\alpha=8-4\cdot2=0\) 　\(b=s-u\cdot\beta=3-4\cdot1=-1\) \(\cases{8=4\cdot2+0\cr3=4\cdot1-1}\)
步驟2：根據\(a,b\le0\)(Case2)使用Coppersmith方法
\(a,b\le0\)(Case2) \(\displaystyle N=p^rq^s=p^{u\cdot\alpha+a}q^{u\cdot\beta+b}=\frac{(p^{\alpha}q^{\beta})^u}{p^{-a}q^{-b}}=\frac{P^u}{Q}\)，其中\(P=p^{\alpha}q^{\beta}\)和\(Q=p^{-a}q^{-b}\)	\(\displaystyle N=p^8q^3=\frac{P^4}{Q}\)，其中\(P=p^2q^1=p^2q\)和\(Q=p^0q^1=q^1\)
步驟2-1.設同餘方程式，計算參數\(X\)
設同餘方程式\(f(x)=(X\cdot t+x)^u \equiv0\pmod{N}\) 其中\(X=\lfloor\;N^{1/u}\rfloor\;\)和\(|\;x_0|\;<X\) 針對\(t\)進行窮舉，其中\(t\)的範圍為\(\displaystyle0\le t\le \frac{P}{X}\le\frac{2P}{N^{1/u}}=2Q^{1/u}\)	\(X=\lfloor\;N^{1/4}\rfloor\;=73091\)，\(0\le t\le 2Q^{1/4}=5\) \(P=X\cdot t+x_0\)，\(x_0=P-X\cdot t\) \(x_0=197213-73091\cdot0=197213\) \(x_0=197213-73091\cdot1=124122\) \(x_0=197213-73091\cdot2=51031\) \(x_0=197213-73091\cdot3=-22060\)，當\(t=3\)時才有較小的解\(x_0\) \(x_0=197213-73091\cdot4=-95151\) \(x_0=197213-73091\cdot5=-168242\) 但這樣\(X\)所需的矩陣\(M\)要非常大才能找到較小的解\(x_0\) 設同餘方程式\(f(x)=(X\cdot t+x)^4\pmod{N}\) 取\(V=X\cdot t=197000\)，Coppersmith方法計算上限\(X=316\) 只要維度8的矩陣\(M\)經LLL化簡就能找到較小的解\(x_0=213\)，其中\(|\;x_0|\;<316\)
步驟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}}\)	\(u=0,v=0,q_{0,0}(xX)=N=\bbox[border:1px solid black]{N}\) \(u=1,v=0,q_{1,0}(xX)=NXx=\bbox[border:1px solid black]{NX}x\) \(u=2,v=0,q_{2,0}(xX)=N(Xx)^2=\bbox[border:1px solid black]{NX^2}x^2\) \(u=3,v=0,q_{3,0}(xX)=N(Xx)^3=\bbox[border:1px solid black]{NX^3}x^3\) \(u=0,v=1,q_{0,1}(xX)=(V+Xx)^4\) \(=V^4+4V^3Xx+6V^2X^2x^2+4VX^3x^3+\bbox[border:1px solid black]{X^4}x^4\) \(u=1,v=1,q_{1,1}(xX)=(Xx)(V+Xx)^4\) \(=V^4Xx+4V^3X^2x^2+6V^2X^3x^3+4VX^4x^4+\bbox[border:1px solid black]{X^5}x^5\) \(u=2,v=1,q_{2,1}(xX)=(Xx)^2(V+Xx)^4\) \(=V^4X^2x^2+4V^3X^3x^3+6V^2X^4x^4+4VX^5x^5+\bbox[border:1px solid black]{X^6}x^6\) \(u=3,v=1,q_{3,1}(xX)=(Xx)^3(V+Xx)^4\) \(=V^4X^3x^3+4V^3X^4x^4+6V^2X^5x^5+4VX^6x^6+\bbox[border:1px solid black]{X^7}x^7\)
\(M=\matrix{&\matrix{1&　x&　x^2&x^3　&x^4&x^5&　x^6&x^7}\cr \matrix{q_{0,0}(xX)\cr q_{1,0}(xX)\cr q_{2,0}(xX)\cr q_{3,0}(xX)\cr q_{0,1}(xX)\cr q_{1,1}(xX)\cr q_{2,1}(xX)\cr q_{3,1}(xX)}&\left[\matrix{N&&&&&&&\cr 0&NX&&&&&&\cr 0&0&NX^2&&&&&\cr 0&0&0&NX^3&&&&\cr *&*&*&*&X^4&&&\cr 0&*&*&*&*&X^5&&\cr 0&0&*&*&*&*&X^6&\cr 0&0&0&*&*&*&*&X^7}\right]}\) *代表非零數字
步驟2-3.經LLL化簡後的短向量產生不需要同餘\(N^{h-1}\)的方程式，得到公鑰\(N\)的因數\(P\)和\(Q\)
矩陣\(M\)經LLL化簡為\(B\) \(B=LLL(M)\) lattice經LLL化簡後第一列\(b_1\)為整個lattice中較短向量 所形成的方程式不需要再同餘\(N^{h-1}\)	lattice經LLL化簡後第一列\(b_1\)為整個lattice中較短向量 \(b_1=[-214382400364144710,\) 　\(262262951620456068,\) 　\(970699742880291792,\) 　\(-1149094400899629312,\) 　\(-786698634624195328,\) 　\(278086338099347456,\) 　\(557584281975848960,\) 　\(314636844829229056]\) 產生不需要同餘\(N^{h-1}=N\)的方程式 \(r(x)=-214382400364144710\) 　\(\displaystyle+262262951620456068\left(\frac{x}{316}\right)\) 　\(\displaystyle+970699742880291792\left(\frac{x}{316}\right)^2\) 　\(\displaystyle-1149094400899629312\left(\frac{x}{316}\right)^3\) 　\(\displaystyle-786698634624195328\left(\frac{x}{316}\right)^4\) 　\(\displaystyle+278086338099347456\left(\frac{x}{316}\right)^5\) 　\(\displaystyle+557584281975848960\left(\frac{x}{316}\right)^6\) 　\(\displaystyle+314636844829229056\left(\frac{x}{316}\right)^7\) \(r(x)=(x-213)^3(x^4+1199x^3+718310x^2+226574471x+22184534430)\) 得到整數解\(x=213\) 得到因數\(P=V+x=197000+213=197213\) \(N\)可分解成\(\displaystyle28540809637096203437=\frac{197213^4}{53}\) \(P=197213,Q=53\)
步驟3.從\(P,Q\)求出\(N\)的質因數\(p,q\)
已知\(P=p^{\alpha}q^{\beta}\)，\(Q=p^{-a}q^{-b}\)，\(\gamma=-a\beta+b\alpha\)，則\(\cases{p=Q^{\displaystyle\frac{\beta}{\gamma}} \cdot P^{\displaystyle\frac{b}{\gamma}}\cr q=Q^{\displaystyle\frac{-\alpha}{\gamma}} \cdot P^{\displaystyle\frac{-a}{\gamma}}}\)	\(\alpha=2,\beta=1,a=0,b=-1,\gamma=-a\beta+b\alpha=-2\) \(\cases{p=Q^{\displaystyle\frac{\beta}{\gamma}} \cdot P^{\displaystyle\frac{b}{\gamma}}=53^{\displaystyle\frac{1}{-2}} \cdot 197213^{\displaystyle\frac{-1}{-2}}=61\cr q=Q^{\displaystyle\frac{-\alpha}{\gamma}} \cdot P^{\displaystyle\frac{a}{\gamma}}=53^{\displaystyle\frac{-2}{-2}} \cdot 197213^{\displaystyle\frac{0}{-2}}=53}\)

請下載LLL.zip，解壓縮後將LLL.mac放到C:\maxima-5.49.0\share\maxima\5.49.0\share目錄下
要先載入LLL.mac才能使用Coppersmith_Howgrave指令
(%i1)　load("LLL.mac");
(%o1)　C:/maxima-5.49.0/share/maxima/5.49.0/share/LLL.mac

要因數分解的公鑰\(N\)
(%i2)　N:28540809637096203437;
(%o2)　\(28540809637096203437\)

\(N=p^rq^s\)，因數\(p\)的次方\(r\)，因數\(q\)的次方\(s\)
(%i4)
r:8;
s:3;
(%o3)　\(8\)
(%o4)　\(3\)

將\(r,s\)表示成\(\cases{r=u\alpha+a\cr s=u\beta+b}\)
(%i10)
u:4;
alpha:2;
beta:1;
a:0;
b:-1;
gamma:-a*beta+b*alpha;
(%o5)　\(4\)
(%o6)　\(2\)
(%o7)　\(1\)
(%o8)　\(0\)
(%o9)　\(-1\)
(%o10)　\(-2\)

\(V\)的高位元和\(P\)相同，當作\(P\)的近似值
(%i11)　V:197000;
(%o11)　\(197000\)

同餘方程式\(f(x)=(V+x)^u\equiv0\pmod{N}\)
(%i12)　fx: ('V+x)^u;
(%o12)　\((x+V)^4\)

Coppersmith_Howgrave方法副程式,參數\(h=2\)
(%i13)　x:Coppersmith_Howgrave(fx,N,2);
參數\(h=2\)
\(p(x)\)最高次方\(k=4\)
\(\displaystyle X=ceiling(\frac{1}{\sqrt{2}}(hk)^{-1/(hk-1)}N^{(h-1)/(hk-1)})=ceiling(\frac{1}{\sqrt{2}}8^{-1/7}619081497^{1/7})=316\)
\(q_{uv}=N^{h-1-v}x^up(x)^v=[28540809637096203437,28540809637096203437x,28540809637096203437x^2,28540809637096203437x^3,\)
\(x^4+4Vx^3+6V^2x^2+4V^3x+V^4,x(x^4+4Vx^3+6V^2x^2+4V^3x+V^4),x^2(x^4+4Vx^3+6V^2x^2+4V^3x+V^4),x^3(x^4+4Vx^3+6V^2x^2+4V^3x+V^4)]\)
用\(316x\)取代\(x\),得到\(q_{uv}=[28540809637096203437,9018895845322400286092x,2849971087121878490405072x^2,900590863530513602968002752x^3,\)
\(9971220736x^4+24864942848000x^3+23251869024000000x^2+9663751472000000000x+1506138481000000000000,\)
\(316x(9971220736x^4+24864942848000x^3+23251869024000000x^2+9663751472000000000x+1506138481000000000000),\)
\(99856x^2(9971220736x^4+24864942848000x^3+23251869024000000x^2+9663751472000000000x+1506138481000000000000),\)
\(31554496x^3(9971220736x^4+24864942848000x^3+23251869024000000x^2+9663751472000000000x+1506138481000000000000)]\)
產生矩陣\(M=\left[\matrix{28540809637096203437&0&0&0&0&0&0&0\cr
0&9018895845322400286092&0&0&0&0&0&0\cr
0&0&2849971087121878490405072&0&0&0&0&0\cr
0&0&0&900590863530513602968002752&0&0&0&0\cr
1506138481000000000000&9663751472000000000&23251869024000000&24864942848000&9971220736&0&0&0\cr
0&475939759996000000000000&3053745465152000000000&7347590611584000000&7857321939968000&3150905752576&0&0\cr
0&0&150396964158736000000000000&964983566988032000000000&2321838633260544000000&2482913733029888000&995686217814016&0\cr
0&0&0&47525440674160576000000000000&304934807168218112000000000&733701008110331904000000&784600739637444608000&314636844829229056}\right]\)
LLL化簡\(B=\left[\matrix{-214382400364144710&262262951620456068&970699742880291792&-1149094400899629312&-786698634624195328&278086338099347456&557584281975848960&314636844829229056\cr
-95647068587766726&182979578697288624&-11740466593266768&93960183407089280&326727727726846464&-1172332296114931712&-373382331680256000&1258547379316916224\cr
563806567324327383&-1713882702679529004&741868428215794752&1343812760321008064&-686844257598941440&533048178880539648&-742781918489255936&-314636844829229056\cr
339672331849247613&-1051715069006529168&836490663580953744&-511700036361113088&1179476536175185408&-648320914932780032&557584281975848960&-943910534487687168\cr
380209352163547656&-229641609525161168&809752168407502960&-1587976988878818624&93307054123140096&254958689875439616&-1300366200465104896&-629273689658458112\cr
12884067955383654&1107969310258392544&-1103177827036703360&630163920939967104&-1502628534289998592&-1230204982072495104&742781918489255936&-629273689658458112\cr
-2380570610455190403&901304238417789672&2592981941171391968&1408390870111434112&460521577533715200&777917668536230912&995686217814016&-629273689658458112\cr
16254669409485033140&9971967498989572660&6766766811505476528&3583338340143789952&2952987490748172800&3784414259565920256&1674744218363174912&1573184224146145280}\right]\)
產生不需要同餘\(N\)的方程式
\(r(x)=-214382400364144710\)
　\(\displaystyle+262262951620456068\left(\frac{x}{316}\right)\)
　\(\displaystyle+970699742880291792\left(\frac{x}{316}\right)^2\)
　\(\displaystyle-1149094400899629312\left(\frac{x}{316}\right)^3\)
　\(\displaystyle-786698634624195328\left(\frac{x}{316}\right)^4\)
　\(\displaystyle+278086338099347456\left(\frac{x}{316}\right)^5\)
　\(\displaystyle+557584281975848960\left(\frac{x}{316}\right)^6\)
　\(\displaystyle+314636844829229056\left(\frac{x}{316}\right)^7\)
\(r(x)=x^7+560x^6+88256x^5-78896923x^4-36416186172x^3+9720995662557x^2+829946049431823x-214382400364144710\)
\(=(x-213)^3(x^4+1199x^3+718310x^2+226574471x+22184534430)\)
整數解為\([x=213]\)
(%o13)　\([x=213]\)

\(\displaystyle N=\frac{P^u}{Q}\)的\(P\)值
(%i14)　P:V+rhs(x[1]);
(%o14)　\(197213\)

\(\displaystyle N=\frac{P^u}{Q}\)的\(Q\)值
(%i15)　Q: (P^u)/N;
(%o15)　\(53\)

\(N=p^rq^s\)的質因數\(p,q\)
(%i17)
p: Q^(beta/gamma)*P^(b/gamma);
q: Q^(-alpha/gamma)*P^(-a/gamma);
(%o16)　\(61\)
(%o17)　\(53\)

4-3.針對大的\(r\)和\(s\)，分解RSA公鑰\(n=p^rq^s\)
Boneh等人證明當\(r\ge \log p\)時，\(N=p^rq\)可以在多項式時間內找到質因數\(p\)和\(q\)。
https://math.pro/db/viewthread.php?tid=3498&page=2#pid25544
Coron等人證明\(N=p^rq^s\)可以在多項式時間內找到質因數，但需要更強的條件\(r\ge (\log p)^3\)。
https://math.pro/db/viewthread.php?tid=3498&page=2#pid28281
在本篇論文中，Coron等人再次證明當\(r\ge \log p\)時，\(N=p^rq^s\)也能在多項式時間內找到質因數，這與\(N=p^rq\)條件完全相同。

方法	範例1	範例2
問題敘述
Theorem 4 令\(N=p^rq^s\)是未知分解的整數，\(gcd(r,s)=1\)，給定\(N\)為輸入，能在多項式時間\(\log N\)和\(r=\Omega(\log q)\)情況下回復質因數\(p\)和\(q\)。	令\(N=p^8q^5=80171134270603235454533\)是未知分解的整數，求質因數\(p\)和\(q\)	令\(N=p^8q^3=125740963503977\)是未知分解的整數，求質因數\(p\)和\(q\)
步驟1：找到符合\(\alpha\cdot s-\beta\cdot r=1\)的\(\alpha\)和\(\beta\)
\(gcd(r,s)=1\)，Bézout恆等式可以找到兩個正整數\(\alpha=s^{-1}\pmod{r}\)和\(\displaystyle \beta=\frac{\alpha\cdot s-1}{r}\)使得\(\alpha\cdot s-\beta\cdot r=1\)	\(\alpha=5^{-1}\equiv5\pmod{8}\) \(\displaystyle \beta=\frac{5\cdot5-1}{8}=3\) 得到\(5\cdot5-3\cdot8=1\)	\(\alpha=3^{-1}\equiv3\pmod{8}\) \(\displaystyle \beta=\frac{3\cdot3-1}{8}=1\) 得到\(3\cdot3-1\cdot8=1\)
步驟2：根據\(N^{\alpha}=P^rq\)使用BDH方法
\(N^{\alpha}=(p^rq^s)^{\alpha}=p^{\alpha r}q^{\alpha s}=p^{\alpha r}q^{\beta r+1}=(p^{\alpha}q^{\beta})^rq\) \(N^{\alpha}=P^rq\)，其中\(P=p^\alpha q^\beta\)	\(N^5=P^8q\)，其中\(P=p^5q^3\)	\(N^3=P^8q\)，其中\(P=p^3q^1\)
步驟2-1.設同餘方程式，計算參數\(X\)
設同餘方程式\(f(x)=(V+x)^r\pmod{P^r}\) 其中\(V\)是使得\(P=V+x_0\)的整數和\(V\)的高位元和\(P\)相同，能找到上限\(X=P\cdot q^{-1/r}\)較小的解\(x_0\)，其中\(|\;x_0|\;< P\cdot q^{-1/r}\) 若\(x_0\)是\(f(x)\equiv 0\pmod{P^r}\)的解，則\(f(x_0)=(V+x_0)^r=P^r\equiv 0\pmod{P^r}\)	\(V=\lfloor\;N^{5/8}\rfloor\;=206543374177592\) \(P=p^5q^3=61^5\cdot 53^3=125740963503977\) \(X=P\cdot q^{-1/8}=76549489742110\) 但這樣\(V\)和\(X\)所需的矩陣\(M\)要非常大才能找到較小的解\(x_0\) 設同餘方程式\(f(x)=(V+x)^8\pmod{P^8}\) 取\(V=125740963500000\)，\(V\)的高位元和\(P\)相同，上限\(X=100000\) 只要維度9的矩陣\(M\)經LLL化簡就能找到較小的解\(x_0=3977\)，其中\(|\;x_0|\;<100000\)	\(V=\lfloor\;N^{3/8}\rfloor\;=19760587\) \(P=p^5q^1=61^5\cdot 53=44763603953\) \(X=P\cdot q^{-1/8}=27251509342\) 但這樣\(V\)和\(X\)所需的矩陣\(M\)要非常大才能找到較小的解\(x_0\) 設同餘方程式\(f(x)=(V+x)^8\pmod{P^8}\) 取\(V=12020000\)，\(V\)的高位元和\(P\)相同，上限\(X=100000\) 只要維度9的矩陣\(M\)經LLL化簡就能找到較小的解\(x_0=9993\)，其中\(|\;x_0|\;<100000\)
步驟2-2.產生矩陣\(M\)
\(g_{i,k}(xX)=N^{\alpha(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-rm-1\) 注意到對所有\(i,k\)，\(g_{i,k}(x_0)\equiv 0\pmod{P^{rm}}\) 注意到對所有\(j,m\)，\(g_{j,m}(x_0)\equiv 0\pmod{P^{rm}}\)	\(i=0,k=0,g_{0,0}(xX)=N^5\cdot1\cdot1=\bbox[border:1px solid black]{N^5}\) \(i=1,k=0,g_{1,0}(xX)=N^5\cdot(xX)\cdot1=\bbox[border:1px solid black]{N^5X}x\) \(i=2,k=0,g_{2,0}(xX)=N^5\cdot(xX)^2\cdot1=\bbox[border:1px solid black]{N^5X^2}x^2\) \(i=3,k=0,g_{3,0}(xX)=N^5\cdot(xX)^3\cdot1=\bbox[border:1px solid black]{N^5X^3}x^3\) \(i=4,k=0,g_{4,0}(xX)=N^5\cdot(xX)^4\cdot1=\bbox[border:1px solid black]{N^5X^4}x^4\) \(i=5,k=0,g_{5,0}(xX)=N^5\cdot(xX)^5\cdot1=\bbox[border:1px solid black]{N^5X^5}x^5\) \(i=6,k=0,g_{6,0}(xX)=N^5\cdot(xX)^6\cdot1=\bbox[border:1px solid black]{N^5X^6}x^6\) \(i=7,k=0,g_{7,0}(xX)=N^5\cdot(xX)^7\cdot1=\bbox[border:1px solid black]{N^5X^7}x^7\) \(j=0,g_{0,1}(xX)=1\cdot f(xX)=(V+Xx)^8=\) \(V^8+8V^7Xx+28V^6X^2x^2+56V^5X^3x^3+70V^4X^4x^4\) \(+56V^3X^5x^5+28V^2X^6x^6+8VX^7x^7+\bbox[border:1px solid black]{X^8}x^8\)	\(i=0,k=0,g_{0,0}(xX)=N^3\cdot1\cdot1=\bbox[border:1px solid black]{N^3}\) \(i=1,k=0,g_{1,0}(xX)=N^3\cdot(xX)\cdot1=\bbox[border:1px solid black]{N^3X}x\) \(i=2,k=0,g_{2,0}(xX)=N^3\cdot(xX)^2\cdot1=\bbox[border:1px solid black]{N^3X^2}x^2\) \(i=3,k=0,g_{3,0}(xX)=N^3\cdot(xX)^3\cdot1=\bbox[border:1px solid black]{N^3X^3}x^3\) \(i=4,k=0,g_{4,0}(xX)=N^3\cdot(xX)^4\cdot1=\bbox[border:1px solid black]{N^3X^4}x^4\) \(i=5,k=0,g_{5,0}(xX)=N^3\cdot(xX)^5\cdot1=\bbox[border:1px solid black]{N^3X^5}x^5\) \(i=6,k=0,g_{6,0}(xX)=N^3\cdot(xX)^6\cdot1=\bbox[border:1px solid black]{N^3X^6}x^6\) \(i=7,k=0,g_{7,0}(xX)=N^3\cdot(xX)^7\cdot1=\bbox[border:1px solid black]{N^3X^7}x^7\) \(j=0,g_{0,1}(xX)=1\cdot f(xX)=(V+Xx)^8=\) \(V^8+8V^7Xx+28V^6X^2x^2+56V^5X^3x^3+70V^4X^4x^4\) \(+56V^3X^5x^5+28V^2X^6x^6+8VX^7x^7+\bbox[border:1px solid black]{X^8}x^8\)
\(N=p^8q^5\)的矩陣\(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_{2,0}(xX)\cr g_{3,0}(xX)\cr g_{4,0}(xX)\cr g_{5,0}(xX)\cr g_{6,0}(xX)\cr g_{7,0}(xX)\cr g_{0,1}(xX)}&\left[\matrix{N^3&&&&&&&&\cr 0&N^5X&&&&&&&\cr 0&0&N^5X^2&&&&&&\cr 0&0&0&N^5X^3&&&&&\cr 0&0&0&0&N^5X^4&&&&\cr 0&0&0&0&0&N^5X^5&&&\cr 0&0&0&0&0&0&N^5X^6&&\cr 0&0&0&0&0&0&0&N^5X^7&\cr *&*&*&*&*&*&*&*&X^8}\right]}\) \(N=p^8q^3\)的矩陣\(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_{2,0}(xX)\cr g_{3,0}(xX)\cr g_{4,0}(xX)\cr g_{5,0}(xX)\cr g_{6,0}(xX)\cr g_{7,0}(xX)\cr g_{0,1}(xX)}&\left[\matrix{N^3&&&&&&&&\cr 0&N^3X&&&&&&&\cr 0&0&N^3X^2&&&&&&\cr 0&0&0&N^3X^3&&&&&\cr 0&0&0&0&N^3X^4&&&&\cr 0&0&0&0&0&N^3X^5&&&\cr 0&0&0&0&0&0&N^3X^6&&\cr 0&0&0&0&0&0&0&N^3X^7&\cr *&*&*&*&*&*&*&*&X^8}\right]}\) *代表非零數字
步驟2-3.經LLL化簡後的短向量產生不需要同餘\(P^{rm}\)的方程式，得到公鑰\(N\)的因數\(P\)和\(q\)
矩陣\(M\)經LLL化簡為\(B\) \(B=LLL(M)\) lattice經LLL化簡後第一列\(b_1\)為整個lattice中較短向量 所形成的方程式不需要再同餘\(P^{rm}\)	lattice經LLL化簡後第一列\(b_1\)為整個lattice中較短向量 所形成的方程式不需要再同餘\(P^8\) \(h(x)=-53(-3977+x)(251481927003977+x)\) \((31621579804816808123694816529+251481927000000x+x^2)\) \((499962154676199102476804875602387403050998979642971607841\) \(+7952255823848096743172491500000000000000000x\) \(+94864739411449993500000000000x^2\) \(+502963854000000x^3+x^4)\) 得到正整數解\(x=3977\) 得到因數\(P=V+x=125740963500000+3977\) \(=125740963503977\) \(N^5\)可分解成\(125740963503977^8\cdot 53\) \(P=125740963503977,q=53\)	lattice經LLL化簡後第二列\(b_2\)為整個lattice中較短向量 所形成的方程式不需要再同餘\(P^8\) \(h(x)=-53(-9993+x)(24049993+x)\) \((289201131580049+24040000x+x^2)\) \((41818676133224591928094842401\) \(+6946617632000000000000x\) \(+866882400000000x^2+48080000x^3+x^4)\) 得到正整數解\(x=9993\) 得到因數\(P=V+x=12020000+9993\) \(=12029993\) \(N^3\)可分解成\(12029993^8\cdot 53\) \(P=12029993,q=53\)
步驟3：從\(P,q\)求出\(N\)的質因數\(p\)
已知\(P=p^\alpha q^\beta\)，則\(\displaystyle p=\left(\frac{P}{q^\beta}\right)^{1/\alpha}\)	\(\displaystyle p=\left(\frac{125740963503977}{53^3}\right)^{1/5}=61\)	\(\displaystyle p=\left(\frac{12029993}{53^1}\right)^{1/3}=61\)

參考資料：
Coron, J.-S., & Zeitoun, R. (2016). Improved factorization of \(N=p^rq^s\) (Cryptology ePrint Archive, Report 2016/551).
https://eprint.iacr.org/2016/551


要先載入LLL.mac才能使用LLL指令
(%i1)　load("LLL.mac");
(%o1)　C:/maxima-5.49.0/share/maxima/5.49.0/share/LLL.mac

要因數分解的公鑰N
(%i2)　N:80171134270603235454533;
(%o2)　\(80171134270603235454533\)

\(N=p^rq^s\)，因數\(p\)的次方\(r\)，因數\(q\)的次方\(s\)
(%i4)
r:8;
s:5;
(%o3)　\(8\)
(%o4)　\(5\)

求出\(\alpha,\beta\)符合\(\alpha s-\beta r=1\)
(%i6)
alpha:inv_mod(s,r);
beta: (alpha*s-1)/r;
(%o5)　\(5\)
(%o6)　\(3\)

假設\(q< P^c\)
(%i7)　c:1;
(%o7)　\(1\)

矩陣維度\(d\)，按照BDH方法維度\(d=144\)，改成\(d=9\)但解的上限\(X\)也變小
(%i9)
d:2*r*(r+1);
d:9;
(%o8)　\(144\)
(%o9)　\(9\)

參數\(m\)，原本\(m=1\)無法得到正確答案，改取\(m=2\)
(%i11)
m:floor(d/(r+c)-1/2);
m:1;
(%o10)　\(0\)
(%o11)　\(1\)

希望能找到\(|\;x|\;<X\)，\(f(x)\equiv 0\pmod{P^r}\)
(%i12)　X:100000;
(%o12)　\(100000\)

\(V\)的高位元和\(P\)相同，當作\(P\)的近似值
(%i13)　V:125740963500000;
(%o13)　\(125740963500000\)

同餘方程式\(f(x)=(V+x)^r \equiv0\pmod{P^}\)
(%i14)　fx: ('V+x)^r;
(%o14)　\((x+V)^8\)

將\(x\)以\(Xx\)代替，\(f(Xx)=(V+Xx)^u\equiv0\pmod{P^r}\)
(%i15)　fXx:subst(x=x*'X,fx);
(%o15)　\((Xx+V)^8\)

以\(x\)升冪排序顯示
(%i16)　powerdisp:true;
(%o16)　\(true\)

\(g(xX)\)多項式
(%i17)　gxX:[];
(%o17)　\([]\)

產生\(g_{i,k}(xX)=N^{\alpha(m-k)}(Xx)^if^k(xX)\)多項式，\(i=0,\ldots,r-1，k=0,\ldots,m-1\)
(%i18)
for k:0 thru m-1 do
  (for i:0 thru r-1 do
     (print("i=",i,",k=",k,",g",i,",",k,"(xX)=N"^(alpha*(m-k)),"*","(xX)"^i,"*","f(xX)"^k,"=",gik:'N^(alpha*(m-k))*(x*'X)^i*fXx^k,"=",expand(gik)),
      gxX:append(gxX,[gik])
     )
  );
\(i=0,k=0,g_{0,0}(xX)=N^5*1*1=N^5=N^5\)
\(i=1,k=0,g_{1,0}(xX)=N^5*(xX)*1=N^5Xx=N^5Xx\)
\(i=2,k=0,g_{2,0}(xX)=N^5*(xX)^2*1=N^5X^2x^2=N^5X^2x^2\)
\(i=3,k=0,g_{3,0}(xX)=N^5*(xX)^3*1=N^5X^3x^3=N^5X^3x^3\)
\(i=4,k=0,g_{4,0}(xX)=N^5*(xX)^4*1=N^5X^4x^4=N^5X^4x^4\)
\(i=5,k=0,g_{5,0}(xX)=N^5*(xX)^5*1=N^5X^5x^5=N^5X^5x^5\)
\(i=6,k=0,g_{6,0}(xX)=N^5*(xX)^6*1=N^5X^6x^6=N^5X^6x^6\)
\(i=7,k=0,g_{7,0}(xX)=N^5*(xX)^7*1=N^5X^7x^7=N^5X^7x^7\)
(%o18)　done

產生\(g_{j,m}=x^jf^m(xX)\)多項式，\(j=0,\ldots,d-mr-1\)
(%i19)
for j:0 thru d-m*r-1 do
  (print("j=",j,",g",j,",",m,"(xX)=","(xX)"^j,"*f(xX)"^m,"=",gim: (x*'X)^j*fXx^m,"=",expand(gim)),
   gxX:append(gxX,[gim])
  );
\(j=0,g_{0,1}(xX)=1*f(xX)=(V+Xx)^8=V^8+8V^7Xx+28V^6X^2x^2+56V^5X^3x^3+70V^4X^4x^4+56V^3X^5x^5+28V^2X^6x^6+8VX^7x^7+X^8x^8\)
(%o19)　done

全部的\(g(xX)\)多項式
(%i20)　gxX;
(%o20)　\([N^5,N^5Xx,N^5X^2x^2,N^5X^3x^3,N^5X^4x^4,N^5X^5x^5,N^5X^6x^6,N^5X^7x^7,(V+Xx)^8]\)

\(x^1,\ldots,x^{d-1}\)
(%i21)　xpower:create_list(x^i,i,1,d-1);
(%o21)　\([x,x^2,x^3,x^4,x^5,x^6,x^7,x^8]\)

取\(g(xX)\)多項式係數(常數項在最後一行)
(%i22)　M:augcoefmatrix(gxX,xpower);
(%o22)　\(\left[\matrix{0&0&0&0&0&0&0&0&N^5\cr
N^5X&0&0&0&0&0&0&0&0\cr
0&N^5X^2&0&0&0&0&0&0&0\cr
0&0&N^5X^3&0&0&0&0&0&0\cr
0&0&0&N^5X^4&0&0&0&0&0\cr
0&0&0&0&N^5X^5&0&0&0&0\cr
0&0&0&0&0&N^5X^6&0&0&0\cr
0&0&0&0&0&0&N^5X^7&0&0\cr
8V^7X&28V^6X^2&56V^5X^3&70V^4X^4&56V^3X^5&28V^2X^6&8VX^7&X^8&V^8}\right]\)

將常數項移到第一行
(%i23)　M:addcol(col(M,d),submatrix(M,d));
(%o23)　\(\left[\matrix{N^5&0&0&0&0&0&0&0&0\cr
0&N^5X&0&0&0&0&0&0&0\cr
0&0&N^5X^2&0&0&0&0&0&0\cr
0&0&0&N^5X^3&0&0&0&0&0\cr
0&0&0&0&N^5X^4&0&0&0&0\cr
0&0&0&0&0&N^5X^5&0&0&0\cr
0&0&0&0&0&0&N^5X^6&0&0\cr
0&0&0&0&0&0&0&N^5X^7&0\cr
V^8&8V^7X&28V^6X^2&56V^5X^3&70V^4X^4&56V^3X^5&28V^2X^6&8VX^7&X^8}\right]\)

將\(N=80171134270603235454533,V=125740963500000,X=100000\)代入矩陣M
(%i24)　M:ev(M,[N=N,V=V,X=X]);
(%o24)　\(\left[\matrix{3311998568856210568811927703086899658426172387868564177766496487544053158361488556283428687867077689884956712107893&0&0&0&0&0&0&0&0\cr
0&331199856885621056881192770308689965842617238786856417776649648754405315836148855628342868786707768988495671210789300000&0&0&0&0&0&0&0\cr
0&0&33119985688562105688119277030868996584261723878685641777664964875440531583614885562834286878670776898849567121078930000000000&0&0&0&0&0&0\cr
0&0&0&3311998568856210568811927703086899658426172387868564177766496487544053158361488556283428687867077689884956712107893000000000000000&0&0&0&0&0\cr
0&0&0&0&331199856885621056881192770308689965842617238786856417776649648754405315836148855628342868786707768988495671210789300000000000000000000&0&0&0&0\cr
0&0&0&0&0&33119985688562105688119277030868996584261723878685641777664964875440531583614885562834286878670776898849567121078930000000000000000000000000&0&0&0\cr
0&0&0&0&0&0&3311998568856210568811927703086899658426172387868564177766496487544053158361488556283428687867077689884956712107893000000000000000000000000000000&0&0\cr
0&0&0&0&0&0&0&331199856885621056881192770308689965842617238786856417776649648754405315836148855628342868786707768988495671210789300000000000000000000000000000000000&0\cr
62490539019210977115313051534131340080406482111493092575802679148753906250000000000000000000000000000000000000000&397582695597594825907711779441749482572759080927469384793143750000000000000000000000000000000000000000000&1106671522038704507522714527351401430135102140557514375000000000000000000000000000000000000000000&1760240245079248987181038305550126359792212250000000000000000000000000000000000000000000&1749867541256005433723511973834730437500000000000000000000000000000000000000000&1113315815338733544044148810000000000000000000000000000000000000000000&442702117253433303000000000000000000000000000000000000000000&100592770800000000000000000000000000000000000000000&10000000000000000000000000000000000000000}\right]\)

LLL化簡
(%i25)　B: LLL(M);
(%o25)　\(\left[\matrix{838028781700335971777938634164628835959430271248954492660096127111488556283428687867077689884956712107893&-21071882866672525773108724310412722576356231289155877394036618750000000000000000000000000000000000000000000&-58653590668051338898703869949624275797160413449548261875000000000000000000000000000000000000000000&-93292732989200196320595030194156697068987249250000000000000000000000000000000000000000000&-92742979686568287987346134613240713187500000000000000000000000000000000000000000&-59005738212952877834339886930000000000000000000000000000000000000000000&-23463212214431965059000000000000000000000000000000000000000000&-5331416852400000000000000000000000000000000000000000&-530000000000000000000000000000000000000000\cr
1455603616945450164635734122287123559788231947307759251070652971625203321324538295872481408960167851726863821&63215657876979755459793006882724077503363981789992502108089798648855628342868786707768988495671210789300000&-921894875650012371888342709364005791895391990918485119037606863003750000000000000000000000000000000000000000000&-1466339767072028793366678328918651544920589050390861875394500000000000000000000000000000000000000000000&-1457698953324813668783719723245411930655944363738375000000000000000000000000000000000000000000&-927429797100171683531736082646073842534820000000000000000000000000000000000000000000&-368785863924198291804776922456966000000000000000000000000000000000000000000&-83797186501301211496437600000000000000000000000000000000000000000&-8330338833981220000000000000000000000000000000000000000\cr
62391856940021854052956340370265284211828079399902171939519489529305892915054844854860212266627596922365735059785&2481319964547718870007243738884429588728310588213631270004166834050000000000000000000000000000000000000000000000&6906754675787907450721381728632533947896054620853696134605000000000000000000000000000000000000000000000&10985687533383514196980654961551227413484953327646000000000000000000000000000000000000000000000&10920951322859390007955377804894134016124500000000000000000000000000000000000000000000&6948221816582081468116237429590960000000000000000000000000000000000000000000&2762910997012553298955848000000000000000000000000000000000000000000&627801092047132800000000000000000000000000000000000000000&62410160000000000000000000000000000000000000000\cr
3309068049759099212784933914724289596466198154879114302833351276051359855172357675652386929893170206829756145715&131593929588904953866237560940665787668541560227108252875864584244665108043822814870335793525977427818909700000&-395097803483788981592002686484268498126782368213990316584535785003812165713121329223101150432878921070000000000&-52679707180011390299109264929166203799525057953264003039126034477630062250000000000000000000000000000000000000000000&-52369277395440220142647929655364661452913331972026764212688367937500000000000000000000000000000000000000000&-33318833218859640847366613127862448073519546060756414810000000000000000000000000000000000000000000&-13248997101433710919260855324948439763434589103000000000000000000000000000000000000000000&-3010496848361412904522752745215521650800000000000000000000000000000000000000000&-299275666076136447821432586010000000000000000000000000000000000000000\cr
-12173792995729164570909489033509365696302788302790150146486346096958124054088681103036919051751469471273239112932&-484147658320326389152807290620855724945135691354593021476334844748717150236486712830694417698512569481090300000&-395097805197705829129368423757831683814734643327478197990784481541514456722556694318807091125472500000000000000&-628431330888769321589250306258121974410884235553798978152071312132922310115043287892107000000000000000&-3292481698750672616736318892326734665623647091603738271840722039197410589584125000000000000000000000000000000000000000000&-2094771095817583816581026209379561285530405271057900409258894879835980000000000000000000000000000000000000000000&-832970830471481084436348465462315821021367182007437222023074000000000000000000000000000000000000000000&-189271387163336469545378041185058046740754383630106400000000000000000000000000000000000000000&-18815605302258606196517855653406263140805580000000000000000000000000000000000000000\cr
18957883835475332378963744344465003908379046858910709546994486677441101972911430643330855031189353341047026213460&753952089775797206309290939576384679085061131518904482968717136122869931387322531246560532568141620345939800000&-263398533801427998971792949738429256846970845733293953533673979175366617423846999369234203000000000000000000000&-418954215825502242110293595353958388981122839468768590330825609071091009134580075600000000000000000000&-416485411917396197332197946926379314905125209523275792231011504328789210700000000000000000000&-210718828720043047471124409068928418600907352056209326038986161229694882823425325990000000000000000000000000000000000000000000&-83790843832703352663241048359283654845267410431529469725665877067060521937000000000000000000000000000000000000000000&-19039333267919567644259393492668908250132687707507158380221636493200000000000000000000000000000000000000000&-1892713871633364695453780411491449666891240230904063970790000000000000000000000000000000000000000\cr
14950931725159633427091188044383004358803819932015910962903619917727112955793168278201530599563389199291492850326&594606486004324437933026673630629076224465808199060450076007001738223580574089937679690637431858379654060200000&263398537555141096001167752364394220304999496502575110674542607604903410748822031761875000000000000000000000000&418954221796051524611019466801515673617372108815716384540894038250157691449250000000000000000000000000&416485417852762362333715005692551888248983503311270142029822721863187500000000000000000000000&264979943693695245039992082257299953486666898849567121078930000000000000000000000000&-13169926795002690466945275566808026162556692942266838036993403876592227774115510686609693000000000000000000000000000000000000000000&-2992530136882262595115751727117273387330975180862164878238155261515013141422174800000000000000000000000000000000000000000&-297489582311243244441553023322951691408322871335219735118197505850491310000000000000000000000000000000000000000\cr
-20473129545372057371673755189475462563139776559727869484661579037980556650478954580833949844154563818747274326980&-814217684430156425521267828497483986764900933541950341786696482186769641030432016969529681284070810172969900000&131699265683651798115137630411037516171183677717146601546041619224402531530133125000000000000000000000000000000&209477105976926601353961520123133963692243662053928195875549528812704750000000000000000000000000000000&208242704034280961822319661288357675591776881499250039422862312500000000000000000000000000000&132489968734353438812209935889894895288774771635498110000000000000000000000000000000&52683693939705432117278923144999956712107893000000000000000000000000000000&-752567245428725169539730032389030066431811025272390744977072643825540616438536837469493741186000000000000000000000000000000000000000000&-74813253422056564877893793177931834683274379521554121956552432873788641722008997237950000000000000000000000000000000000000000\cr
19037690731404546329186831791645661014939163724644340498097672130785141263863867623816248031524743620377251296617&757133944597224170960183256343170510364806072176592501556064398323892307812500000000000000000000000000000000000&2107482503973563554219656824246536639809365905342433419039472680781250000000000000000000000000000000000&3352101726138854589291669972365905466931412379932071093187500000000000000000000000000000000000&3332348537056953787867696325913219070938855558328125000000000000000000000000000000000&2120135519436800744964990713412638401447500000000000000000000000000000000000&843056813158903758903116212169250000000000000000000000000000000000&191563169617559210789300000000000000000000000000000000000&-32924816987506726167363188917020065406391732355667095092746928167367402492918393259761254015136066400000000000000000000000000000000000000000}\right]\)

找出\(N\)的因數\(P,q\)
(%i26)
for i:1 thru d do
  (print("第",i,"列向量B[",i,"]=",B[ i ]),
   print("產生不需要同餘P"^"rm","=P"^(r*m),"的方程式h(x)"),
   printList:["h(x)=",B[ i ][1]],
   for j:2 thru d do
    (if B[ i ][j]>=0 then printList:append(printList,["+"]),/*若係數為正則補印+號*/
     printList:append(printList,[B[ i ][j],"(",x/X,")"^(j-1)])
    ),
   apply(print,printList),/*再用apply(print,)將全部內容印在同一行*/
   print("h(x)=",hx:sum(B[ i ][j+1]*(x/X)^j,j,0,d-1),"=",factor(hx)),
   print("正整數解為",posIntRoot:sublist(solve(hx,x),lambda([x],integerp(rhs(x)) and rhs(x)>0))),
   if length(posIntRoot)>0 then/*若有正整數解*/
     (for root in posIntRoot do
        (x:rhs(root),
         print("當正整數解x=",x,"時，可能的因數P=V+x=",V,"+",x,"=",P: V+x),
         if mod(N^alpha,P^r)=0 then
            (print("N"^alpha,"可被P"^r,"整除，N"^alpha,"可分解成",N,""^alpha,"=",P,""^r,"*",q: (N^alpha)/(P^r)),
             i:d/*將i設為d，直接結束for迴圈*/
            )
         else
           (print("N"^alpha,"無法被P"^r,"整除"))
        )
     ),
   print("－－－－－－－－－")
  );
第1列向量\(B[1]=[838028781700335971777938634164628835959430271248954492660096127111488556283428687867077689884956712107893,\)
\(-21071882866672525773108724310412722576356231289155877394036618750000000000000000000000000000000000000000000,\)
\(-58653590668051338898703869949624275797160413449548261875000000000000000000000000000000000000000000,\)
\(-93292732989200196320595030194156697068987249250000000000000000000000000000000000000000000,\)
\(-92742979686568287987346134613240713187500000000000000000000000000000000000000000,\)
\(-59005738212952877834339886930000000000000000000000000000000000000000000,\)
\(-23463212214431965059000000000000000000000000000000000000000000,\)
\(-5331416852400000000000000000000000000000000000000000,\)
\(-530000000000000000000000000000000000000000]\)
產生不需要同餘\(P^{rm}=P^8\)的方程式\(h(x)\)
\(h(x)= 838028781700335971777938634164628835959430271248954492660096127111488556283428687867077689884956712107893\)
\(\displaystyle-21071882866672525773108724310412722576356231289155877394036618750000000000000000000000000000000000000000000 \left(\frac{x}{100000}\right)\)
\(\displaystyle-58653590668051338898703869949624275797160413449548261875000000000000000000000000000000000000000000 \left(\frac{x}{100000}\right)^2\)
\(\displaystyle-93292732989200196320595030194156697068987249250000000000000000000000000000000000000000000 \left(\frac{x}{100000}\right)^3\)
\(\displaystyle-92742979686568287987346134613240713187500000000000000000000000000000000000000000 \left(\frac{x}{100000}\right)^4\)
\(\displaystyle-59005738212952877834339886930000000000000000000000000000000000000000000 \left(\frac{x}{100000}\right)^5\)
\(\displaystyle-23463212214431965059000000000000000000000000000000000000000000 \left(\frac{x}{100000}\right)^6\)
\(\displaystyle-5331416852400000000000000000000000000000000000000000 \left(\frac{x}{100000}\right)^7\)
\(\displaystyle-530000000000000000000000000000000000000000 \left(\frac{x}{100000}\right)^8\)
\(h(x)= 838028781700335971777938634164628835959430271248954492660096127111488556283428687867077689884956712107893\)
\(-210718828666725257731087243104127225763562312891558773940366187500000000000000000000000000000000000000x\)
\(-5865359066805133889870386994962427579716041344954826187500000000000000000000000000000000x^2\)
\(-93292732989200196320595030194156697068987249250000000000000000000000000000x^3\)
\(-927429796865682879873461346132407131875000000000000000000000x^4\)
\(-5900573821295287783433988693000000000000000000x^5\)
\(-23463212214431965059000000000000x^6-53314168524000000x^7-53x^8\)
\(=-53(-3977+x)(251481927003977+x)(31621579804816808123694816529+251481927000000x+x^2)\)
\((499962154676199102476804875602387403050998979642971607841+7952255823848096743172491500000000000000000x+94864739411449993500000000000x^2+502963854000000x^3+x^4)\)
正整數解為\([x=3977]\)
當正整數解\(x=3977\)時，可能的因數\(P=V+x=125740963500000+3977=125740963503977\)
\(N^5\)可被\(P^8\)整除，\(N^5\)可分解成\(80171134270603235454533^5=125740963503977^8*53\)
－－－－－－－－－
(%o26)　done

\(N=P^rq\)的\(P,q\)值
(%i28)
P;
q;
(%o27)　\(125740963503977\)
(%o28)　\(53\)

\(N=p^rq^s\)的質因數\(p\)
(%i29)　p: (P/(q^beta))^(1/alpha);
(%o29)　\(61\)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
要先載入LLL.mac才能使用LLL指令
(%i1)　load("LLL.mac");
(%o1)　C:/maxima-5.49.0/share/maxima/5.49.0/share/LLL.mac

要因數分解的公鑰\(N\)
(%i2)　N:28540809637096203437;
(%o2)　\(28540809637096203437\)

\(N=p^rq^s\)，因數\(p\)的次方\(r\)，因數\(q\)的次方\(s\)
(%i4)
r:8;
s:3;
(%o3)　\(8\)
(%o4)　\(3\)

求出\(\alpha,\beta\)符合\(\alpha s-\beta r=1\)
(%i6)
alpha:inv_mod(s,r);
beta: (alpha*s-1)/r;
(%o5)　\(3\)
(%o6)　\(1\)

假設\(q< P^c\)
(%i7)　c:1;
(%o7)　\(1\)

矩陣維度\(d\)，按照BDH方法維度\(d=144\)，改成\(d=9\)但解的上限\(X\)也變小
(%i9)
d:2*r*(r+1);
d:9;
(%o8)　\(144\)
(%o9)　\(9\)

參數\(m\)，原本\(m=1\)無法得到正確答案，改取\(m=2\)
(%i11)
m:floor(d/(r+c)-1/2);
m:1;
(%o10)　\(0\)
(%o11)　\(1\)

希望能找到\(|\;x|\;<X\)，\(f(x)\equiv 0\pmod{P^r}\)
(%i12)　X:100000;
(%o12)　\(100000\)

\(V\)的高位元和\(P\)相同，當作\(P\)的近似值
(%i13)　V:12020000;
(%o13)　\(12020000\)

同餘方程式\(f(x)=(V+x)^r\equiv0\pmod{P^r}\)
(%i14)　fx: ('V+x)^r;
(%o14)　\((x+V)^8\)

將\(x\)以\(Xx\)代替，\(f(Xx)=(V+Xx)^u\equiv0\pmod{P^u}\)
(%i15)　fXx:subst(x=x*'X,fx);
(%o15)　\((Xx+V)^8\)

以\(x\)升冪排序顯示
(%i16)　powerdisp:true;
(%o16)　true

g(xX)多項式
(%i17)　gxX:[];
(%o17)　\([]\)

產生\(g_{i,k}(xX)=N^{\alpha(m-k)}(Xx)^if^k(xX)\)多項式，\(i=0,\ldots,r-1\)，\(k=0,\ldots,m-1\)
(%i18)
for k:0 thru m-1 do
  (for i:0 thru r-1 do
     (print("i=",i,",k=",k,",g",i,",",k,"(xX)=N"^(alpha*(m-k)),"*","(xX)"^i,"*","f(xX)"^k,"=",gik:'N^(alpha*(m-k))*(x*'X)^i*fXx^k,"=",expand(gik)),
      gxX:append(gxX,[gik])
     )
  );
\(i=0,k=0,g_{0,0}(xX)=N^3*1*1=N^3=N^3\)
\(i=1,k=0,g_{1,0}(xX)=N^3*(xX)*1=N^3Xx=N^3Xx\)
\(i=2,k=0,g_{2,0}(xX)=N^3*(xX)^2*1=N^3X^2x^2=N^3X^2x^2\)
\(i=3,k=0,g_{3,0}(xX)=N^3*(xX)^3*1=N^3X^3x^3=N^3X^3x^3\)
\(i=4,k=0,g_{4,0}(xX)=N^3*(xX)^4*1=N^3X^4x^4=N^3X^4x^4\)
\(i=5,k=0,g_{5,0}(xX)=N^3*(xX)^5*1=N^3X^5x^5=N^3X^5x^5\)
\(i=6,k=0,g_{6,0}(xX)=N^3*(xX)^6*1=N^3X^6x^6=N^3X^6x^6\)
\(i=7,k=0,g_{7,0}(xX)=N^3*(xX)^7*1=N^3X^7x^7=N^3X^7x^7\)
(%o18)　done

產生\(gj,m=x^jf^m(xX)\)多項式，\(j=0,\ldots,d-mr-1\)
(%i19)
for j:0 thru d-m*r-1 do
  (print("j=",j,",g",j,",",m,"(xX)=","(xX)"^j,"*f(xX)"^m,"=",gim: (x*'X)^j*fXx^m,"=",expand(gim)),
   gxX:append(gxX,[gim])
  );
\(j=0,g_{0,1}(xX)=1*f(xX)=(V+Xx)^8=V^8+8V^7Xx+28V^6X^2x^2+56V^5X^3x^3+70V^4X^4x^4+56V^3X^5x^5+28V^2X^6x^6+8VX^7x^7+X^8x^8\)
(%o19)　done

全部的\(g(xX)\)多項式
(%i20)　gxX;
(%o20)　\([N^3,N^3Xx,N^3X^2x^2,N^3X^3x^3,N^3X^4x^4,N^3X^5x^5,N^3X^6x^6,N^3X^7x^7,(V+Xx)^8]\)

\(x^1,\ldots,x^{d-1}\)
(%i21)　xpower:create_list(x^i,i,1,d-1);
(%o21)　\([x,x^2,x^3,x^4,x^5,x^6,x^7,x^8]\)

取\(g(xX)\)多項式係數(常數項在最後一行)
(%i22)　M:augcoefmatrix(gxX,xpower);
(%o22)　\(\left[\matrix{0&0&0&0&0&0&0&0&N^3\cr
N^3X&0&0&0&0&0&0&0&0\cr
0&N^3X^2&0&0&0&0&0&0&0\cr
0&0&N^3X^3&0&0&0&0&0&0\cr
0&0&0&N^3X^4&0&0&0&0&0\cr
0&0&0&0&N^3X^5&0&0&0&0\cr
0&0&0&0&0&N^3X^6&0&0&0\cr
0&0&0&0&0&0&N^3X^7&0&0\cr
8V^7X&28V^6X^2&56V^5X^3&70V^4X^4&56V^3X^5&28V^2X^6&8VX^7&X^8&V^8}\right]\)

將常數項移到第一行
(%i23)　M:addcol(col(M,d),submatrix(M,d));
(%o23)　\(\left[\matrix{N^3&0&0&0&0&0&0&0&0\cr
0&N^3X&0&0&0&0&0&0&0\cr
0&0&N^3X^2&0&0&0&0&0&0\cr
0&0&0&N^3X^3&0&0&0&0&0\cr
0&0&0&0&N^3X^4&0&0&0&0\cr
0&0&0&0&0&N^3X^5&0&0&0\cr
0&0&0&0&0&0&N^3X^6&0&0\cr
0&0&0&0&0&0&0&N^3X^7&0\cr
V^8&8V^7X&28V^6X^2&56V^5X^3&70V^4X^4&56V^3X^5&28V^2X^6&8VX^7&X^8}\right]\)

將N=28540809637096203437,V=12020000,X=100000代入矩陣M
(%i24)　M:ev(M,[N=N,V=V,X=X]);
(%o24)　\(\left[\matrix{23248710345123657468134328259470385913821371086862454574453&0&0&0&0&0&0&0&0\cr
0&2324871034512365746813432825947038591382137108686245457445300000&0&0&0&0&0&0&0\cr
0&0&232487103451236574681343282594703859138213710868624545744530000000000&0&0&0&0&0&0\cr
0&0&0&23248710345123657468134328259470385913821371086862454574453000000000000000&0&0&0&0&0\cr
0&0&0&0&2324871034512365746813432825947038591382137108686245457445300000000000000000000&0&0&0&0\cr
0&0&0&0&0&232487103451236574681343282594703859138213710868624545744530000000000000000000000000&0&0&0\cr
0&0&0&0&0&0&23248710345123657468134328259470385913821371086862454574453000000000000000000000000000000&0&0\cr
0&0&0&0&0&0&0&2324871034512365746813432825947038591382137108686245457445300000000000000000000000000000000000&0\cr
435748340010089115770905600000000000000000000000000000000&29001553411653185741824000000000000000000000000000000000&844471189191232529920000000000000000000000000000000000&14051101317657779200000000000000000000000000000000000&146122101889120000000000000000000000000000000000000&972526468480000000000000000000000000000000000000&4045451200000000000000000000000000000000000000&9616000000000000000000000000000000000000000&10000000000000000000000000000000000000000}\right]\)

LLL化簡
(%i25)　B: LLL(M);
(%o25)　\(\left[\matrix{435748340010089115770905600000000000000000000000000000000&29001553411653185741824000000000000000000000000000000000&844471189191232529920000000000000000000000000000000000&14051101317657779200000000000000000000000000000000000&146122101889120000000000000000000000000000000000000&972526468480000000000000000000000000000000000000&4045451200000000000000000000000000000000000000&9616000000000000000000000000000000000000000&10000000000000000000000000000000000000000\cr
154048324588934332276331459470385913821371086862454574453&-1537082330817618844316672000000000000000000000000000000000&-44756973027135324085760000000000000000000000000000000000&-744708369835862297600000000000000000000000000000000000&-7744471400123360000000000000000000000000000000000000&-51543902829440000000000000000000000000000000000000&-214408913600000000000000000000000000000000000000&-509648000000000000000000000000000000000000000&-530000000000000000000000000000000000000000\cr
-162077502404949082084842450965751684547382737906557646169&1969746834731448319990210651038591382137108686245457445300000&-67638556629548419673269959680000000000000000000000000000000000&-1125433554568193338989516800000000000000000000000000000000000&-11703759926873890796480000000000000000000000000000000000000&-77895240777862833920000000000000000000000000000000000000&-324023464134204800000000000000000000000000000000000000&-770200770464000000000000000000000000000000000000000&-800957540000000000000000000000000000000000000000\cr
87220936077297233833936445458984902777586946580566832800&-154727708058322026594316065857010289948709452362040924500000&64359466104766379520753782431219138213710868624545744530000000000&-3867266954827484331145133590886400000000000000000000000000000000000&-40217002442049545872973519040000000000000000000000000000000000000&-267667237551078508305980160000000000000000000000000000000000000&-1113424449047747538710400000000000000000000000000000000000000&-2646599593648080672000000000000000000000000000000000000000&-2752287430998420000000000000000000000000000000000000000\cr
-233434692118334022597684293766737694092551986370100805523&295525473625723809809721065774713941553796294549374956600000&-5357639286362459416256127776735436591631086030108644500000000000&2514419498929525577045153368226784221371086862454574453000000000000000&-241744965948676455309455939123358560000000000000000000000000000000000000&-1608951520457081233340804919290240000000000000000000000000000000000000&-6692809985262401137024978865600000000000000000000000000000000000000&-15908747290854293170965008000000000000000000000000000000000000000&-16544038364033166775130000000000000000000000000000000000000000\cr
-80355031977576963910331735981628533374277985872028238083&-447185200983208957421279946670410859076722164531721890200000&26478759410143305042897159436286875916506979478069003080000000000&-139259721222713919221685778306986732813640217708668978000000000000000&102994493217168852524036029709324106617108686245457445300000000000000000000&-15472665823754732632019359666671076654080000000000000000000000000000000000000&-64362170647898222262975705768182515200000000000000000000000000000000000000&-152988282975750468892264572779136000000000000000000000000000000000000000&-159097632046329522558511410960000000000000000000000000000000000000000\cr
-40443476365409749484193604988054792214696446631026566061&-561685344343178240977187710601846132546380858634123263700000&-31884790900934610106038165006078870418926097637290190150000000000&-947743298341827982221950254140889377166934743575884376000000000000000&-1934178769803323643646597837208997797420425703303278000000000000000000000&4023071328046830777824751355072427264894228624545744530000000000000000000000000&-967067722046208518513167461910768663523081600000000000000000000000000000000000000&-2298711010330897358006102833160847785888000000000000000000000000000000000000000&-2390506458330800081121155192554958180000000000000000000000000000000000000000\cr
31156380980572790621916638150948120326616891766232167301&437897915743825333528960852849801674657688827585613369500000&-11653354955499128611201546807571595482544728003931500320000000000&-990294677818161707446796864322645515989653785808583821000000000000000&13780943213159012661417941597264430890622942619565038500000000000000000000&-696300717285279503810927226287355336757173239720056080000000000000000000000000&131523483249032682493274470141233355055914009654574453000000000000000000000000000000&-55261656338579530390900487247445316568733813104000000000000000000000000000000000000000&-57468444611667564882384034159156943187119190000000000000000000000000000000000000000\cr
120577116226244450410584228304991235897568351045664623996&-823174264658206956978173181351743115801469008310135119400000&18239188888812267849589997764242285029720881766635610490000000000&1032846503505308722998111581410710393214444101876947094000000000000000&483552969392167431832275942497110883299042810085553100000000000000000000&-1965115613307936641951005238356059624681667417664628040000000000000000000000000&65761734898371355118114397942739700770960514381859615000000000000000000000000000000&2486788759905632242541953624413038528313911266625445300000000000000000000000000000000000&-2417708556284947838166795220459041366829876034499770000000000000000000000000000000000000000}\right]\)

找出N的因數P,q
(%i26)
for i:1 thru d do
  (print("第",i,"列向量B[",i,"]=",B[ i ]),
   print("產生不需要同餘P"^"rm","=P"^(r*m),"的方程式h(x)"),
   printList:["h(x)=",B[ i ][1]],
   for j:2 thru d do
    (if B[ i ][j]>=0 then printList:append(printList,["+"]),/*若係數為正則補印+號*/
     printList:append(printList,[B[ i ][j],"(",x/X,")"^(j-1)])
    ),
   apply(print,printList),/*再用apply(print,)將全部內容印在同一行*/
   print("h(x)=",hx:sum(B[ i ][j+1]*(x/X)^j,j,0,d-1),"=",factor(hx)),
   print("正整數解為",posIntRoot:sublist(solve(hx,x),lambda([x],integerp(rhs(x)) and rhs(x)>0))),
   if length(posIntRoot)>0 then/*若有正整數解*/
     (for root in posIntRoot do
        (x:rhs(root),
         print("當正整數解x=",x,"時，可能的因數P=V+x=",V,"+",x,"=",P: V+x),
         if mod(N^alpha,P^r)=0 then
            (print("N"^alpha,"可被P"^r,"整除，N"^alpha,"可分解成",N,""^alpha,"=",P,""^r,"*",q: (N^alpha)/(P^r)),
             i:d/*將i設為d，直接結束for迴圈*/
            )
         else
           (print("N"^alpha,"無法被P"^r,"整除"))
        )
     ),
   print("－－－－－－－－－")
  );
第1列向量\(B[1]=[435748340010089115770905600000000000000000000000000000000,\)
\(29001553411653185741824000000000000000000000000000000000,\)
\(844471189191232529920000000000000000000000000000000000,\)
\(14051101317657779200000000000000000000000000000000000,\)
\(146122101889120000000000000000000000000000000000000,\)
\(972526468480000000000000000000000000000000000000,\)
\(4045451200000000000000000000000000000000000000,\)
\(9616000000000000000000000000000000000000000,\)
\(10000000000000000000000000000000000000000]\)
產生不需要同餘\(P^{rm}=P^8\)的方程式\(h(x)\)
\(h(x)=435748340010089115770905600000000000000000000000000000000\)
\(\displaystyle+29001553411653185741824000000000000000000000000000000000\left(\frac{x}{100000}\right)\)
\(\displaystyle+844471189191232529920000000000000000000000000000000000\left(\frac{x}{100000}\right)^2\)
\(\displaystyle+14051101317657779200000000000000000000000000000000000\left(\frac{x}{100000}\right)^3\)
\(\displaystyle+146122101889120000000000000000000000000000000000000\left(\frac{x}{100000}\right)^4\)
\(\displaystyle+972526468480000000000000000000000000000000000000\left(\frac{x}{100000}\right)^5\)
\(\displaystyle+4045451200000000000000000000000000000000000000\left(\frac{x}{100000}\right)^6\)
\(\displaystyle+9616000000000000000000000000000000000000000\left(\frac{x}{100000}\right)^7\)
\(\displaystyle+10000000000000000000000000000000000000000\left(\frac{x}{100000}\right)^8\)
\(h(x)=435748340010089115770905600000000000000000000000000000000\)
\(+290015534116531857418240000000000000000000000000000x\)
\(+84447118919123252992000000000000000000000000x^2\)
\(+14051101317657779200000000000000000000x^3\)
\(+1461221018891200000000000000000x^4\)
\(+97252646848000000000000x^5+4045451200000000x^6+96160000x^7+x^8\)
\(=(12020000+x)^8\)
正整數解為\([]\)
－－－－－－－－－
第2列向量\(B[2]=[154048324588934332276331459470385913821371086862454574453,\)
\(-1537082330817618844316672000000000000000000000000000000000,\)
\(-44756973027135324085760000000000000000000000000000000000,\)
\(-744708369835862297600000000000000000000000000000000000,\)
\(-7744471400123360000000000000000000000000000000000000,\)
\(-51543902829440000000000000000000000000000000000000,\)
\(-214408913600000000000000000000000000000000000000,\)
\(-509648000000000000000000000000000000000000000,\)
\(-530000000000000000000000000000000000000000]\)
產生不需要同餘\(P^{rm}=P^8\)的方程式\(h(x)\)
\(h(x)=154048324588934332276331459470385913821371086862454574453\)
\(\displaystyle-1537082330817618844316672000000000000000000000000000000000\left(\frac{x}{100000}\right)\)
\(\displaystyle-44756973027135324085760000000000000000000000000000000000\left(\frac{x}{100000}\right)^2\)
\(\displaystyle-744708369835862297600000000000000000000000000000000000\left(\frac{x}{100000}\right)^3\)
\(\displaystyle-7744471400123360000000000000000000000000000000000000\left(\frac{x}{100000}\right)^4\)
\(\displaystyle-51543902829440000000000000000000000000000000000000\left(\frac{x}{100000}\right)^5\)
\(\displaystyle-214408913600000000000000000000000000000000000000\left(\frac{x}{100000}\right)^6\)
\(\displaystyle-509648000000000000000000000000000000000000000\left(\frac{x}{100000}\right)^7\)
\(\displaystyle-530000000000000000000000000000000000000000\left(\frac{x}{100000}\right)^8\)
\(h(x)=154048324588934332276331459470385913821371086862454574453\)
\(-15370823308176188443166720000000000000000000000000000x\)
\(-4475697302713532408576000000000000000000000000x^2\)
\(-744708369835862297600000000000000000000x^3\)
\(-77444714001233600000000000000000x^4\)
\(-5154390282944000000000000x^5\)
\(-214408913600000000x^6-5096480000x^7-53x^8\)
\(=-53(-9993+x)(24049993+x)(289201131580049+24040000x+x^2)
\((41818676133224591928094842401+6946617632000000000000x+866882400000000x^2+48080000x^3+x^4)\)
正整數解為\([x=9993]\)
當正整數解\(x=9993\)時，可能的因數\(P=V+x=12020000+9993=12029993\)
\(N^3\)可被\(P^8\)整除，\(N^3\)可分解成\(28540809637096203437^3=12029993^8*53\)
(%o26)　done

\(N=P^rq\)的\(P,q\)值
(%i28)
P;
q;
(%o27)　\(12029993\)
(%o28)　\(53\)

\(N=p^rq^s\)的質因數\(p\)
(%i29)　p: (P/(q^beta))^(1/alpha);
(%o29)　\(61\)