用Maxima學密碼學-Lattice Reduction應用-整數關係
整數關係是給定實數\(x_1,x_2,\ldots,x_n\)，要找到不全為0的整數\(a_1,a_2,\ldots,a_n\)使得\(a_1x_1+a_2x_2+\ldots+a_n x_n=0\)。
到
https://github.com/andrejv/identify下載identify.mac和integer_relation.lisp
將兩個檔案放到C:/maxima-5.45.0/share/maxima/5.45.0/share/資料夾
\(x=(4,8,9,10,11)\)
\(-2\times 4+8=0\)
\(8-9-10+11=0\)
\(8-2\times 9+10=0\)
\(4+8+9-10-11=0\)
\(x=(8,16,18,20,22)\)
\(-2\times 8+16=0\)
\(16-18-20+22=0\)
\(16-2\times 18+20=0\)
\(8+16+18-20-22=0\)
| Coppersmith Splitting System(CSS) | 可變參數的Splitting System(PSS) | 參數相依的Splitting System(PDSS) |
定義
假設\(m\)和\(t\)都是偶數且\(0<t<m\)，定義\((m,t)\)的splitting system是符合以下2點的數對\((X,\cal{B})\)
1.集合\(X\)有\(m\)個元素，集合\(\cal{B}\)有\(\displaystyle \frac{m}{2}\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。
2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle \frac{t}{2}\)。 | 定義
假設\(m\)、\(t\)和\(t_s\)和都是整數且\(0<t<m\)、\(0\le t_s \le t\)，定義\((m,t,t_s)\)的可變參數splitting system是符合以下2點的數對\((X,\cal{B})\)
1.集合\(X\)有\(m\)個元素，集合\(\cal{B}\)有\(\displaystyle \Bigg\lfloor\; \frac{t_s m}{t}\Bigg\rfloor\;\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。
2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle t_s\)。
| 定義
假設\(m\)、\(t\)、\(t_1\)、\(t_2\)、\(m_1\)和\(m_2\)和都是整數且\(0<t<m\)、\(t=t_1+t_2\)、\(\displaystyle m_1=\frac{t_1m}{t}\)、\(\displaystyle m_2=\frac{t_2m}{t}\)、，定義\((m,m_1,m_2,t_1,t_2)\)的可變參數splitting system是符合以下2點的數對\((X,\cal{B})\)
1.集合\(X\)有\(m\)個元素\((m=m_1+m_2)\)，集合\(\cal{B}\)有\(m_2\)個\(X\)的子集合，\(\cal{B}\)稱為區塊(blocks)。
2.對所有\(X\)的子集合\(Y\)，\(Y\)有\(t\)個元素，存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle t_2\)。 |
產生\(\displaystyle (\frac{m}{2};m,t)\)的Coppersmith splitting system方法
令\(X=Z_m\)，定義
\(B_i=\{\;i+j\pmod{m}:0\le j\le m/2-1\}\;\)
\(\cal B\)\(=\{\;B_i:0\le i \le m/2-1\}\;\) | 產生\(\displaystyle (m;m,t,t_s)\)的可變參數splitting system方法
令\(X=Z_m\)，定義
\(B_i=\{\;i+j\pmod{m}:0\le j\le \Bigg\lfloor\;\frac{t_sm}{t}\Bigg\rfloor\;-1\}\;\)
\(\cal B\)\(=\{\;B_i:0\le i \le m-1\}\;\) | 產生\(\displaystyle (m;m_1,m_2,t_1,t_2)\)的參數相依splitting system方法
令\(X=Z_m\)，定義
\(B_i=\{\;i+j\pmod{m}:0\le j\le m_2\}\;\)
\(\cal B\)\(=\{\;B_i:0\le i \le m_2-1\}\;\) |
以\(m=8,t=4\)為例(解\(x\)有8位元，其中有4個1，分成2個1和2個1分別列舉)
\(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1,2,3\}\;\)，\(B_1=\{\;1,2,3,4\}\;\)，\(B_2=\{\;2,3,4,5\}\;\)，\(B_3=\{\;3,4,5,6\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3\}\;\)
子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3\)和\(Y\)交集2個元素。
子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3\)和\(Y\)交集2個元素。
子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_0\)和\(Y\)交集2個元素。
子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0\)和\(Y\)交集2個元素。
子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_2,B_3\)和\(Y\)交集2個元素。 | 以\(m=8,t=4,t_s=1\)為例(解\(x\)有8位元，其中有4個1，分成1個1和3個1分別列舉)
\(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1\}\;\)，\(B_1=\{\;1,2\}\;\)，\(B_2=\{\;2,3\}\;\)，\(B_3=\{\;3,4\}\;\)，\(B_4=\{\;4,5\}\;\)，\(B_5=\{\;5,6\}\;\)，\(B_6=\{\;6,7\}\;\)，\(B_7=\{\;7,0\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;\)
子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_0,B_1,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。 | 以\(m=8,t=4,t_1=3,t_2=1,m_1=6,m_2=2\)為例(解\(x\)有8位元，其中有4個1，分成3個1和1個1分別列舉)
\(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\)，\(B_0=\{\;0,1\}\;\)，\(B_1=\{\;1,2\}\;\)，\(B_2=\{\;2,3\}\;\)，\(B_3=\{\;3,4\}\;\)，\(B_4=\{\;4,5\}\;\)，\(B_5=\{\;5,6\}\;\)，\(B_6=\{\;6,7\}\;\)，\(B_7=\{\;7,0\}\;\)，\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\}\;\)
子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素，存在\(B_0,B_1,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素，存在\(B_0,B_1,B_2,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。
子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素，存在\(B_3,B_4,B_5,B_6,B_7\)和\(Y\)交集1個元素。 |
令\(\displaystyle n_1>\frac{n_2}{2}\)，對任意的\(n_1,n_2\)，令\(k\in Z^{+}\backslash\; \{\;1\}\;\)是大於1的整數且滿足\(\displaystyle \frac{k+1}{2k+1}n_2 \le n_1<\frac{k}{2k-1}n_2\)。
假設\(t_1\)和\(t_2\)滿足\(\matrix{\displaystyle \frac{2k+1}{k+1}t_1-\frac{3k+1}{k+1}\le t_2\le \frac{2k-1}{k}t_1+\frac{3k-2}{k}\cr
\frac{2k-1}{k}t_1<t_2\le \frac{2k+1}{k+1}t_1}\)
則\(N=2n_2-n_1+1\)就足以產生一組參數相依的Splitting system。
\(\cal{B}=\{\;B_i：0 \le i \le 2 n_2-n_1\}\;\)
令\(\displaystyle \frac{1}{2}n_2\le n_1 \le \frac{2}{3}n_2\)，假設\(t_2=2t_1,2t_1-1,2t_1-2\)
則\(N=\cases{\displaystyle 2n_1\frac{1}{3}\lceil\;t_1-1\rceil\;-n_2(\frac{1}{3}\lceil\;t_1-1\rceil\;-1)+1, if t_2=2t_1\cr
2n_1\frac{1}{4}\lceil\;t_1-2\rceil\;-n_2(\frac{1}{4}\lceil\;t_1-2\rceil\;-1)+1, if t_2=2t_1-1\cr
2n_1\frac{1}{5}\lceil\;t_1-3\rceil\;-n_2(\frac{1}{5}\lceil\;t_1-3\rceil\;-1)+1, if t_2=2t_1-2}\)就足夠產生一組參數相依的Splitting system。
\(\cal A, B\)
q:2;
v:2;
node[1,1]:v;
p:181;
for i:0 thru q-1 do
(for j:0 thru 2^i-1 do
(expL:product(X1[k],k,1+(2*j+1)*(2^(q-i-1)),(2*j+2)*(2^(q-i-1))),
print(expL),
node[i+2,2*j+1]:power_mod(node[i+1,j+1],expL,p),
expR:product(X1[k],k,1+2*j*(2^(q-i-1)),(2*j+1)*(2^(q-i-1))),
print(expR),
node[i+2,2*j+2]:power_mod(node[i+1,j+1],expR,p)
)
);
複製內容到剪貼板
代碼:
void main()
{
for(i=0;i<5;i++)
{printf(i);
}
}Pohlig Hellman
解\( a^x \equiv b \pmod p \)，求\( x= \)？
將\( p-1 \)作質因數分解
\( p-1=q_1^{m_1}\times q_2^{m_2}\times ... \times q_n^{m_n} \)
取\( q=q_1 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
將x用q進位表示
令\( x=x_0+x_1 q+x_2 q^2+...+x_{k-1} q^{k-1} \)，\( 0\le x_i <q \)
代入原式
\( \displaystyle b \equiv a^{x_0+x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}} \pmod p \)
兩邊同取\( \displaystyle \frac{p-1}{q} \)次方
\( \displaystyle b^{\frac{p-1}{q}} \equiv a^{\frac{p-1}{q}x_0} \times a^{(p-1)(x_1+x_2 q+...+x_k q^{k-2})}\pmod p \)
利用費馬小定理\( a^{p-1} \equiv 1\pmod p \)
\( \displaystyle b^{\frac{p-1}{q}} \equiv a^{\frac{p-1}{q}x_0}\pmod p \)
將\( x_0=0,1,2,...,q-1 \)一一代入檢驗上式，符合等式的就是我們要找的\( x_0 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
\( \displaystyle b \equiv a^{x_0+x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}} \pmod p \)
將\( a^{x_0} \)移到另一邊
\( ba^{-x_0}=a^{x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}}\pmod p \)
令\( b_1=ba^{-x_0} \)得
\( b_1=a^{x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}}\pmod p \)
兩邊同取\( \displaystyle \frac{p-1}{q^2} \)次方
\( \displaystyle b_1^{\frac{p-1}{q^2}}=a^{\frac{p-1}{q}x_1}\times a^{(p-1)(x_2+x_3 q+...+x_{k-1} q^{k-3})}\pmod p \)
利用費馬小定理\( a^{p-1} \equiv 1\pmod p \)
\( \displaystyle b_1^{\frac{p-1}{q^2}}=a^{\frac{p-1}{q}x_1}\pmod p \)
將\( x_1=0,1,2,...,q-1 \)一一代入檢驗上式，符合等式的就是我們要找的\( x_1 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
\( b_1=a^{x_1 q+x_2 q^2+...+x_{k-1} q^{k-1}}\pmod p \)
將\( a^{x_1 q} \)移到另一邊
\( b_1 a^{-x_1 q}=a^{x_2 q^2+x_3 q^3+...+x_{k-1} q^{k-1}}\pmod p \)
令\( b_2=b_1 a^{-x_1 q} \)得
\( b_2=a^{x_2 q^2+x_3 q^3+...+x_{k-1} q^{k-1}}\pmod p \)
兩邊同取\( \displaystyle \frac{p-1}{q^3} \)次方
\( \displaystyle b_2^{\frac{p-1}{q^3}}=a^{\frac{p-1}{q}x_2} \times a^{(p-1)(x_3+x_4 q+...+x_{k-1} q^{k-4})}\pmod p \)
利用費馬小定理\( a^{p-1} \equiv 1\pmod p \)
\( \displaystyle b_2^{\frac{p-1}{q^3}}=a^{\frac{p-1}{q}x_2}\pmod p \)
將\( x_2=0,1,2,...,q-1 \)一一代入檢驗上式，符合等式的就是我們要找的\( x_2 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
重複上面的步驟直到\( q^{k+1} \)無法整除\( p-1 \)為止
將收集到的\( x_0,x_1,...,x_k \)重新組合出\( x \equiv x_0+x_1 q_1+x_2 q_1^2+...+x_{k-1} q_1^{k-1}\pmod {q_1^k} \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
換第二個質因數\( q_2 \)
令\( q=q_2 \)仿照上面的步驟找出\( x_0,x_1,...,x_k \)
並重新組合出\( x \equiv x_0+x_1 q_2+x_2 q_2^2+...+x_{k-1} q_2^{k-1}\pmod {q_2^k} \)
解\( a^x \equiv b \pmod p \)的方法
(1)baby step,giant step
(2)index caculus
(3)Pohlig Hellman
(4)Pollard's rho
| 離散對數問題
Discrete Logarithm Problem，DLP
\( a^x \equiv b \pmod p \)，解\( x \) | 橢圓曲線離散對數問題
Elliptic Curve Discrete Logarithm Problem，ECDLP
\( P,Q \in E(F_p) \)，\( Q=kP \)，解\( k \)
|
| baby step,giant step | D | a |
| index caculus | F | a |
| Pohlig-Hellman | H | a |
| Pohlig Hellman | J | a |
| Pollard's rho | J | a |
https://sites.google.com/a/g2.nc ... 15-08/15th_pentagon
\( v=\left[ \matrix{1&1&7&2\cr 9&8&4&6\cr 1&8&5&7\cr 2&3&1&1} \right] \)
\( \matrix{arr1 \cr arr2}=\matrix{0&1 \cr 2&3} \)
\(thread 0\)
\( v_0=\left[ \matrix{1&1&7&2} \right] \)
\( v_2=\left[ \matrix{1&8&5&7} \right] \)
進行\(Gauss\) \(Reduction\)
| \(thread 1\)
\( v_1=\left[ \matrix{9&8&4&6} \right] \)
\( v_3=\left[ \matrix{2&3&1&1} \right] \)
進行\(Gauss\) \(Reduction\)
|
\( \Vert\; v_0 \Vert\;=\sqrt{55}<\Vert\; v_2 \Vert\;=\sqrt{139} \)
兩向量不需交換 | \( \Vert\; v_1 \Vert\;=\sqrt{197}>\Vert\; v_3 \Vert\;=\sqrt{15} \)
兩向量交換
\( v_1=\left[ \matrix{2&3&1&1} \right] \)
\( v_3=\left[ \matrix{9&8&4&6} \right] \) |
\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_2}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{58}{55} \Bigg\rceil\;=\Bigg\lfloor\;1.054 \Bigg\rceil\;=1 \)
\( v_2=v_2-q \times v_0=\left[ \matrix{0&7&-2&5} \right] \)
得到更短的向量 | \( \displaystyle q=\Bigg\lfloor\; \frac{v_1 \cdot v_3}{v_1 \cdot v_1} \Bigg\rceil\;=\Bigg\lfloor\; \frac{52}{15} \Bigg\rceil\;=\Bigg\lfloor\; 3.466 \Bigg\rceil\;=3 \)
\( v_3=v_3-q \times v_1=\left[ \matrix{3&-1&1&3} \right] \)
得到更短的向量 |
\( \Vert\; v_0 \Vert\;=\sqrt{55}<\Vert\; v_2 \Vert\;=\sqrt{78} \)
兩向量不需交換 | \( \Vert\; v_1 \Vert\;=\sqrt{15}<\Vert\; v_3 \Vert\;=\sqrt{20} \)
兩向量不需交換 |
\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_2}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{3}{55} \Bigg\rceil\;=\Bigg\lfloor\; 0.054 \Bigg\rceil\;=0 \)
\(v_0\)和\(v_2\)化簡結束 | \( \displaystyle q=\Bigg\lfloor\; \frac{v_1 \cdot v_3}{v_1 \cdot v_1} \Bigg\rceil\;=\Bigg\lfloor\; \frac{7}{15} \Bigg\rceil\;=\Bigg\lfloor\; 0.466 \Bigg\rceil\;=0 \)
\(v_1\)和\(v_3\)化簡結束 |
\( v=\left[ \matrix{1&1&7&2 \cr 2&3&1&1 \cr 0&7&-2&5 \cr 3&-1&1&3} \right] \)
\( \matrix{arr1 \cr arr2}=\matrix{0&2 \cr 3&1} \)
\(thread\) 0
\( v_0=\left[ \matrix{1&1&7&2} \right] \)
\( v_3=\left[ \matrix{3&-1&1&3} \right]\)
進行\(Gauss\) \(Reduction\) | \(thread\) 1
\( v_1=\left[ \matrix{2&3&1&1} \right] \)
\( v_2=\left[ \matrix{0&7&-2&5} \right] \)
進行\(Gauss\) \(Reduction\) |
\( \Vert\; v_0 \Vert\;=\sqrt{55}>\Vert\; v_3 \Vert\;=\sqrt{20} \)
兩向量交換
\( v_0=\left[ \matrix{3&-1&1&3} \right] \)
\( v_3=\left[ \matrix{1&1&7&2} \right] \) | \( \Vert\; v_1 \Vert\;=\sqrt{15}<\Vert\; v_2 \Vert\;=\sqrt{78} \)
兩向量不需交換 |
\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_3}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{15}{20} \Bigg\rceil\;=\Bigg\lfloor\; 0.75 \Bigg\rceil\;=1 \)
\( v_3=v_3-q \times v_0=\left[ \matrix{-2&2&6&-1} \right] \)
得到更短的向量 | \( \displaystyle q=\Bigg\lfloor\; \frac{v_1 \cdot v_2}{v_1 \cdot v_1} \Bigg\rceil\;=\Bigg\lfloor\; \frac{24}{15} \Bigg\rceil\;=\Bigg\lfloor\; 1.6 \Bigg\rceil\;=2 \)
\( v_2=v_2-q \times v_1=\left[ \matrix{-4&1&-4&3} \right] \)
得到更短的向量 |
\( \Vert\; v_0 \Vert\;=\sqrt{20}<\Vert\; v_3 \Vert\;=\sqrt{45} \)
兩向量不需交換 | \( \Vert\; v_1 \Vert\;=\sqrt{15}<\Vert\; v_2 \Vert\;=\sqrt{42} \)
兩向量不需交換 |
\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_3}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{-5}{20} \Bigg\rceil\;=\Bigg\lfloor\; -0.25 \Bigg\rceil\;=0 \)
\(v_0\)和\(v_3\)化簡結束 | \( \displaystyle q=\Bigg\lfloor\; \frac{v_1 \cdot v_2}{v_1 \cdot v_1} \Bigg\rceil\;=\Bigg\lfloor\; \frac{-6}{15} \Bigg\rceil\;=\Bigg\lfloor\; -0.4 \Bigg\rceil\;=0 \)
\(v_1\)和\(v_2\)化簡結束 |
\(v=\left[ \matrix{3&-1&1&3 \cr 2&3&1&1 \cr -4&1&-4&3 \cr -2&2&6&-1} \right] \)
\( \matrix{arr1 \cr arr2}=\matrix{0&3 \cr 1&2} \)
\(thread\) 0
\( v_0=\left[ \matrix{3&-1&1&3} \right] \)
\( v_1=\left[ \matrix{2&3&1&1} \right] \)
進行\(Gauss\) \(Reduction\) | \(thread\) 1
\( v_2=\left[ \matrix{-4&1&-4&3} \right] \)
\( v_3=\left[ \matrix{-2&2&6&-1} \right] \)
進行\(Gauss\) \(Reduction\) |
\( \Vert\; v_0 \Vert\;=\sqrt{20}>\Vert\; v_1 \Vert\;=\sqrt{15} \)
兩向量交換
\( v_0=\left[ \matrix{2&3&1&1} \right] \)
\( v_1=\left[ \matrix{3&-1&1&3} \right] \) | \( \Vert\; v_2 \Vert\;=\sqrt{42}<\Vert\; v_3 \Vert\;=\sqrt{45} \)
兩向量不需交換 |
\( \displaystyle q=\Bigg\lfloor\; \frac{v_0 \cdot v_1}{v_0 \cdot v_0} \Bigg\rceil\;=\Bigg\lfloor\; \frac{7}{15} \Bigg\rceil\;=\Bigg\lfloor\; 0.466 \Bigg\rceil\;=0 \)
\(v_0\)和\(v_1\)化簡結束 | \( \displaystyle q=\Bigg\lfloor\; \frac{v_2 \cdot v_3}{v_2 \cdot v_2} \Bigg\rceil\;=\Bigg\lfloor\; \frac{-17}{42} \Bigg\rceil\;=\Bigg\lfloor\; -0.404 \Bigg\rceil\;=0 \)
\(v_2\)和\(v_3\)化簡結束 |
\( v=\left[ \matrix{2&3&1&1\cr 3&-1&1&3\cr -4&1&-4&3\cr -2&2&6&-1} \right] \)
\(for\) \(i=1\) \(to\) \(n-1\)
\(for\) \(j=i+1\) \(to\) \(n\)
\(v_i\)和\(v_j\)進行\(Gauss\) \(Reduction\)
\(end\)
\(end\)
第1輪
\( \matrix{array1:&1&&2&→&3&→&4\cr &&↗&&&&&↓ \cr array2:&5&←&6&←&7&←&8 }\)，\( \matrix{v_1和v_5\cr v_2和v_6\cr v_3和v_7\cr v_4和v_8} \)同時進行\(Gauss\) \(Reduction\)
第2輪
\( \matrix{array1:&1&&5&→&2&→&3\cr &&↗&&&&&↓ \cr array2:&6&←&7&←&8&←&4 }\)，\( \matrix{v_1和v_6\cr v_5和v_7\cr v_2和v_8\cr v_3和v_4} \)同時進行\(Gauss\) \(Reduction\)
第3輪
\( \matrix{array1:&1&&6&→&5&→&2\cr &&↗&&&&&↓ \cr array2:&7&←&8&←&4&←&3 }\)，\( \matrix{v_1和v_7\cr v_6和v_8\cr v_4和v_5\cr v_2和v_3} \)同時進行\(Gauss\) \(Reduction\)
第4輪
\( \matrix{array1:&1&&7&→&6&→&5\cr &&↗&&&&&↓ \cr array2:&8&←&4&←&3&←&2 }\)，\( \matrix{v_1和v_8\cr v_4和v_7\cr v_3和v_6\cr v_2和v_5} \)同時進行\(Gauss\) \(Reduction\)
第5輪
\( \matrix{array1:&1&&8&→&7&→&6\cr &&↗&&&&&↓ \cr array2:&4&←&3&←&2&←&5 }\)，\( \matrix{v_1和v_4\cr v_3和v_8\cr v_2和v_7\cr v_5和v_6} \)同時進行\(Gauss\) \(Reduction\)
第6輪
\( \matrix{array1:&1&&4&→&8&→&7\cr &&↗&&&&&↓ \cr array2:&3&←&2&←&5&←&6 }\)，\( \matrix{v_1和v_3\cr v_2和v_4\cr v_5和v_8\cr v_6和v_7} \)同時進行\(Gauss\) \(Reduction\)
第7輪
\( \matrix{array1:&1&&3&→&4&→&8\cr &&↗&&&&&↓ \cr array2:&2&←&5&←&6&←&7 }\)，\( \matrix{v_1和v_2\cr v_3和v_5\cr v_4和v_6\cr v_8和v_8} \)同時進行\(Gauss\) \(Reduction\)
第8輪
\( \matrix{array1:&1&&2&→&3&→&4\cr &&↗&&&&&↓ \cr array2:&5&←&6&←&7&←&8 }\)，回到初始值
\( \matrix{1& &2&\rightarriw&3&\rightarriw&4\cr &\nearrow& & & & &\downarrow \cr 5&\leftarrow&6&\leftarrow&7&\leftarrow&8} \)
array1:１ ２→３→４
↗ ↓
array2:５←６←７←８
←→↖↗↓
[tr][td][/td][td][/td][/tr]
\( \left[ \matrix{4 & 9 & 3 & -5 & -5 & -1 & 7 & -1 & -5 \cr -2 & -8 & -7 & -1 & -3 & 6 & -3 & 9 & 8 \cr 1 & -3 & -2 & 3 & 9 & 7 & 2 & 7 & -2 \cr -5 & 6 & 4 & -2 & -2 & -7 & -2 & -9 & 1 \cr 1 & -2 & -2 & 7 & 7 & -3 & -9 & -5 & -4 \cr 7 & 1 & -4 & 3 & -2 & 9 & 9 & 7 & 6} \right] \)
| \( \matrix{4 & 9 & 3 & -5 & -5 & -1 & 7 & -1 & -5} \) | \( \matrix{-2 & -8 & -7 & -1 & -3 & 6 & -3 & 9 & 8} \) | \( \matrix{1 & -3 & -2 & 3 & 9 & 7 & 2 & 7 & -2} \) |
