4-1.針對大的r和s，分解RSA公鑰n=prqs

RSA　n=prq	RSA　n=prqs
產生公鑰和私鑰
產生兩個隨機質數pq 計算n=prq 計算L=LCM(p−1q−1) 找ed符合ed1(modL)和GCD(ep)=1 en是公鑰，dpq是私鑰	產生兩個隨機質數pq 計算n=prqs 計算L=LCM(p−1q−1) 找ed符合ed1(modL)和GCD(eL)=GCD(en)=1 en是公鑰，dpq是私鑰
加密
cme(modn) m為明文，c為密文	相同
解密
無法使用mcd(modn)來回復明文	無法使用mcd(modn)來回復明文
利用中國餘數定理快速解密
mqcd(modq) 設dqd(modq−1)，mqcdq(modq) 利用中國餘數定理 m(mpq(q−1(modpr))+mqpr(p−r(modq)))(modn) mpm(modpr)的mp無法用mpcd(modpr)直接計算 用Takagi的方法計算mp	利用中國餘數定理 m(mpqs(q−s(modpr))+mqpr(p−r(modqs)))(modn) mpm(modpr)的mp無法用mpcd(modpr)直接計算 mqm(modqs)的mq無法用mqcd(modqs)直接計算 用Takagi的方法分別計算mpmq

先介紹n=prqs
假設密文c經pr同餘後為cp，明文m經pr同餘後為m_p，密文c_p和明文m_p的關係為c_p\equiv m_p^e \pmod{p^r}。
設明文m_p以p進位表示成m_p\equiv X_0+pX_1+p^2X_2+\ldots+p^{r-1}X_{r-1}\pmod{p^r}
設密文c_p以p進位表示成c_p\equiv A_0+pA_1+p^2A_2+\ldots+p^{r-1}A_{r-1}\pmod{p^r}

c_p[ i ]=A_0+pA_1+\ldots+p^iA_i=(X_0+pX_1+\ldots+p^iX_i)^e \pmod{p^{i+1}}
設F_i=(X_0+pX_1+\ldots+p^iX_i)^e
注意到F_r\pmod{p^r}=A和A[r-1]=A
c_p[ i ]=A_0+pA_1+\ldots+p^iA_i\pmod{p^{i+1}}
　=(X_0+pX_1+\ldots+p^iX_i)^e\pmod{p^{i+1}}
　=(X_0+pX_1+\ldots+p^{i-1}X_{i-1})^e+eX_0^{e-1}p^iX_i\pmod{p^{i+1}}
　=F_i+eX_0^{e-1}p^iX_i\pmod{p^{i+1}}
得到
X_0=A_0^{d\pmod{p-1}}\pmod{p}
\displaystyle X_i=\frac{e^{-1}X_0^{1-e}(c_p[ i ]-F_i\pmod{p^{i+1}})}{p^i}\pmod{p}，1\le i \le r-1

RSA　n=p^rq的遞迴關係式	RSA　n=p^rq^s的遞迴關係式
K_0=c^{d_p}\pmod{p} A_{i+1}=A_i+p^iK_i F_i=(A_i)^e\pmod{p^{i+1}} \displaystyle K_{i}\equiv \frac{(c_p-F_i)(eF_i)^{-1}A_i}{p^i}\pmod{p^{i+1}}，1\le i \le r-1	X_0=c^{d_p}\pmod{p} A_{i+1}=A_i+p^iX_i F_i=(A_i)^e\pmod{p^{i+1}} \displaystyle X_i=\frac{e^{-1}X_0^{1-e}(c_p[ i ]-F_i\pmod{p^{i+1}})}{p^i}\pmod{p}，1\le i \le r-1 e^{-1}和X_0^{1-e}同餘p，與Takagi演算法相比，雖然整體速度影響不大，但比較簡單。

Lim, S., Kim, S., Yie, I., Lee, H. (2000). A Generalized Takagi-Cryptosystem with a Modulus of the Form prqs . In: Roy, B., Okamoto, E. (eds) Progress in Cryptology —INDOCRYPT 2000. INDOCRYPT 2000. Lecture Notes in Computer Science, vol 1977. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44495-5_25
https://link.springer.com/chapter/10.1007/3-540-44495-5_25

再介紹如何分解
4-2.針對大的r和s，分解RSA公鑰n=p^rq^s

問題敘述 令N=p^rq^s是未知分解的整數，r>s和gcd(r,s)=1，給定N作為輸入，能在多項式時間log N，在r=\Omega(log^3 max(p,q))情況下回復質因數p和q。
步驟1：從r和s找出u,\alpha,\beta,a,b使得\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}
引理1 令r和s是兩個整數，r>s>0，能在多項式時間內計算u,\alpha,\beta,a,b使得\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}。 其中\displaystyle 0<\alpha\le 2r^{1/3},0\le \beta\le \alpha,|\;a|\;<\alpha,|\;b|\;\le \frac{6r^{2/3}}{\alpha},u>\frac{r}{\alpha}-1，這裡a和b都同時\ge 0(Case1)，或同時\le 0(Case2)。
當a和b都同時\ge 0(Case1) 步驟2：N=P^u\cdot Q利用BDH方法解出P和Q	當a和b都同時\le 0(Case2) 步驟2：\displaystyle N=\frac{P^u}{Q}利用Coppersmith方法解出P和Q
a\ge 0,b\ge 0 N=p^rq^s=p^{u\cdot α+a}\cdot q^{u\cdot β+b}=(p^{α}q^{β})^u\cdot p^a q^b=P^u\cdot Q，其中P=p^αq^β和Q=p^aq^b 論文的定理6 令p和q是兩個整數且p\ge 2和q\ge 2，令N=p^rq。假如r=\Omega(log q)，能在多項式時間log N內分解出因數p和q。	a\le 0,b\le 0 \displaystyle N=p^rq^s=p^{u\cdot α+a}q^{u\cdot β+b}=(p^{α}q^{β})^up^aq^b=\frac{P^u}{Q}，其中P=p^αq^β和Q=p^{-a}q^{-b} 從P^u=Q\cdot N得到P^u\equiv 0\pmod{N} P=X\cdot t+x_0，其中X=\lfloor\;N^{1/u}\rfloor\;和|\;x_0|\;\le X 多項式方程式(X\cdot t+x_0)^u\equiv 0\pmod{N} \displaystyle 0\le t\le \frac{P}{X}\le 2\frac{P}{N^{1/u}}=2Q^{1/u} 應用Coppersmith方法求x_0，進而得到N的因數P=X\cdot t+x_0
步驟3：從P=p^{\alpha}q^{\beta}和Q=p^aq^b回復質因數p和q
設矩陣\left[\matrix{a&b\cr \alpha&\beta}\right]，其行列式值為a\beta-b\alpha=\gamma 若\gamma=0，則\beta \cdot r=\alpha \cdot s 則\gamma\ne 0 \cases{\displaystyle Q^{\frac{β}{γ}}\cdot P^{\frac{-b}{γ}}=(p^aq^b)^{\frac{β}{γ}}\cdot(p^{α}q^{β})^{\frac{-b}{γ}}=p^{\frac{aβ-bα}{γ}}\cdot q^{\frac{bβ-bβ}{γ}}=p^1\cdot q^0=p\cr Q^{\frac{-α}{γ}}\cdot P^{\frac{a}{γ}}=(p^aq^b)^{\frac{-α}{γ}}\cdot (p^{α}q^{β})^{\frac{a}{γ}}=p^{\frac{aα-aα}{γ}}\cdot q^{\frac{aβ-bα}{γ}}=p^0\cdot q^1=q}

a和b都同時\ge 0(Case1)的範例 N=p^rq^s=p^8q^5 M=\left[\matrix{\lfloor\; r^{1/3} \rfloor\;&-s\cr 0&r}\right]=\left[\matrix{\lfloor\; 8^{1/3} \rfloor\;&-5\cr 0&r}\right]=\left[\matrix{2&-5\cr 0&8}\right] Gauss-Lagrange演算法化簡 B=\left[\matrix{2&3\cr 4&-2}\right] 較短向量v=(4,-2)=(\lfloor 8^{1/3} \rfloor\cdot \alpha,\gamma)，\gamma=-s\cdot \alpha+r\cdot \beta \cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}，\cases{8=4\cdot 2+0\cr 5=4\cdot 1+1} N=(p^{\alpha}q^{\beta})^up^aq^b=(p^2q)^4q

a和b都同時\le 0(Case2)的範例 N=p^rq^s=p^8q^3 M=\left[\matrix{\lfloor\; r^{1/3} \rfloor\;&-s\cr 0&r}\right]=\left[\matrix{\lfloor\; 8^{1/3} \rfloor\;&-3\cr 0&8}\right]=\left[\matrix{2&-3\cr 0&8}\right] Gauss-Lagrange演算法化簡 B=\left[\matrix{2&-3\cr 4&2}\right] 較短向量v=(4,2)=(\lfloor 8^{1/3} \rfloor\cdot \alpha,\gamma)，\gamma=-s\cdot \alpha+r\cdot \beta \cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}，\cases{8=4\cdot 2+0\cr 3=4\cdot 1-1} N=(p^{\alpha}q^{\beta})^up^aq^b=(p^2q)^4q^{-1}

－－－－－－－－－－－－－－－－－－－－－

方法	範例
問題敘述 令N=p^rq^s是未知分解的整數，r>s和gcd(r,s)=1，給定N作為輸入，能在多項式時間log N，在r=\Omega(log^3 max(p,q))情況下回復質因數p和q。
N=p^8q^5=(p^2q)^4q	N=p^8q^3=(p^2q)^4q^{-1}
步驟1：從r和s找出u,\alpha,\beta,a,b使得\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}
引理1 令r和s是兩個整數，r>s>0，能在多項式時間內計算u,\alpha,\beta,a,b使得\cases{r=u\cdot \alpha+a\cr s=u\cdot \beta+b}。 其中\displaystyle 0<\alpha\le 2r^{1/3},0\le \beta\le \alpha,|\;a|\;<\alpha,|\;b|\;\le \frac{6r^{2/3}}{\alpha},u>\frac{r}{\alpha}-1，這裡a和b都同時\ge 0(Case1)，或同時\le 0(Case2)。 M=\left[\matrix{\lfloor\; r^{1/3} \rfloor\;&-s\cr 0&r}\right] M=\left[\matrix{\lfloor\; 8^{1/3} \rfloor\;&-5\cr 0&r}\right]=\left[\matrix{2&-5\cr 0&8}\right] LLL化簡 B=\left[\matrix{2&3\cr 4&-2}\right] 較短向量v=(4,-2)=(\lfloor 8^{1/3} \rfloor\cdot \alpha,\gamma)
\cases{8=4\cdot 2+0\cr 5=4\cdot 1+1}	\cases{8=4\cdot 2+0\cr 3=4\cdot 1-1}
步驟2：N=P^u\cdot Q利用BDH方法解出P和Q	步驟2：\displaystyle N=\frac{P^u}{Q}利用Coppersmith方法解出P和Q
a\ge 0,b\ge 0 N=p^rq^s=p^{u\cdot α+a}\cdot q^{u\cdot β+b}=(p^{α}q^{β})^u\cdot p^a q^b=P^u\cdot Q，其中P=p^αq^β和Q=p^aq^b 論文的定理6 令p和q是兩個整數且p\ge 2和q\ge 2，令N=p^rq。假如r=\Omega(log q)，能在多項式時間log N內分解出因數p和q。	a\le 0,b\le 0 \displaystyle N=p^rq^s=p^{u\cdot α+a}q^{u\cdot β+b}=(p^{α}q^{β})^up^aq^b=\frac{P^u}{Q}，其中P=p^αq^β和Q=p^{-a}q^{-b} 從P^u=Q\cdot N得到P^u\equiv 0\pmod{N} P=X\cdot t+x_0，其中X=\lfloor\;N^{1/u}\rfloor\;和|\;x_0|\;\le X 多項式方程式(X\cdot t+x_0)^u\equiv 0\pmod{N} \displaystyle 0\le t\le \frac{P}{X}\le 2\frac{P}{N^{1/u}}=2Q^{1/u} 應用Coppersmith方法求x_0，進而得到N的因數P=X\cdot t+x_0
步驟2-1：列舉因數P的近似值\tilde{P}	步驟2-1：
步驟2-2：設同餘方程式，計算參數X
步驟2-3：產生矩陣M
步驟2-4：經LLL化簡後的短向量產生不需要同餘p^{um}的方程式，得到公鑰N的因數P
步驟3：從P=p^{\alpha}q^{\beta}和Q=p^aq^b回復質因數p和q
設矩陣\left[\matrix{a&b\cr \alpha&\beta}\right]，其行列式值為a\beta-b\alpha=\gamma 若\gamma=0，則\beta \cdot r=\alpha \cdot s 則\gamma\ne 0 \cases{\displaystyle Q^{\frac{β}{γ}}\cdot P^{\frac{-b}{γ}}=(p^aq^b)^{\frac{β}{γ}}\cdot(p^{α}q^{β})^{\frac{-b}{γ}}=p^{\frac{aβ-bα}{γ}}\cdot q^{\frac{bβ-bβ}{γ}}=p^1\cdot q^0=p\cr Q^{\frac{-α}{γ}}\cdot P^{\frac{a}{γ}}=(p^aq^b)^{\frac{-α}{γ}}\cdot (p^{α}q^{β})^{\frac{a}{γ}}=p^{\frac{aα-aα}{γ}}\cdot q^{\frac{aβ-bα}{γ}}=p^0\cdot q^1=q}

https://eprint.iacr.org/2015/071.pdf

方法	範例
問題敘述
步驟1：
步驟2：
步驟3：
步驟4：

A Generalized Takagi-Cryptosystem with a Modulus of the Form prqs


\matrix{& \matrix{常數項&一次方&二次方}\cr \matrix{1\cr 2\cr 3　\cr}&\left[\matrix{　1　&　2　&　3　\cr 4&5&6\cr 7&8&9}\right]}


https://math.pro/db/viewthread.php?tid=3498&page=1#pid23067

1997年Howgrave-Graham方法	1999年Boneh,Durfee,Howgrave-Graham方法
q_{u,v}(x)=N^{(h-1-v)}x^u(p(x))^v 以h=3,k=2為例計算det(M) M=\left[\matrix{N^2&&&&&\cr 0&N^2X^1&&&&\cr *&*&NX^2&&&\cr 0&*&*&NX^3&&\cr *&*&*&*&X^4&\cr 0&*&*&*&*&X^5}\right] *代表非零數字	g_{i,k}(x)=N^{m-k}x^i f^k(x)

由費馬小定理可知q^{p-1}\equiv 1\pmod{p}，所以q^{p-2}\equiv q^{-1}\pmod{p}
同理p^{q-2}\equiv p^{-1}\pmod{q}
得m\equiv (m_p\cdot q(q^{p-2}\pmod{p})+m_q (p \cdot p^{p-2}\pmod{q}))\pmod{pq}
利用a(b\pmod{c})=(ab)\pmod{ac}
m\equiv (m_p(q^{p-1}\pmod{n})+m_q (p^{p-1}\pmod{n}))\pmod{pq}


\cases{m\equiv m_p \pmod{p}\cr m\equiv m_q \pmod{q}}
設m=m_q+hq
m\equiv m_q+hq\pmod{p}
m_p \equiv m_q+hq \pmod{p}
h\equiv q^{-1}(m_p-m_q)\pmod{p}
代入m=m_q+hq
得m=m_q+q(q^{-1}(m_p-m_q)\pmod{p})

https://stattrek.com/matrix-algebra/echelon-form
https://rosettacode.org/wiki/Cholesky_decomposition

計算s長度
\Vert\;s\Vert\;=\sqrt{d_{12}^2N^{6\alpha}+d_{13}^2N^{6\alpha}+d_{14}^2N^{6\alpha}+d_{23}^2N^{6\alpha}+d_{24}^2N^{6\alpha}+d_{34}^2N^{6\alpha}+e_{123}^2+e_{124}^2+e_{134}^2+e_{234}^2}

找共同根-subresultant [證明] 設f(x)和g(x)有共同因式h(x) 將f(x)和g(x)分解成兩個式子相乘\matrix{f(x)=h(x)\tilde{f}(x) \cr g(x)=h(x)\tilde{g}(x)} 計算\tilde{g}(x)f(x)=\tilde{g}(x)h(x)\tilde{f}(x)=g(x)\tilde{f}(x) 移項\tilde{g}(x)f(x)-\tilde{f}(x)g(x)=0 (1)當k=0時 若存在s(x)為次方m-1的多項式和t(x)為次方n-1多項式，且滿足s(x)f(x)+t(x)g(x)=0 則f(x)和g(x)至少有一個共同根。 因為f(x)的n個根也會是t(x)g(x)的根，但t(x)至多n-1次方，意指f(x)至少一個根也會是g(x)的根 將 s(x)=s_{m-1}x^{m-1}+s_{m-2}x^{m-2}+\ldots+s_1x+s_0(m-1\ge 0) f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0 t(x)=t_{n-1}x^{n-1}+\ldots+t_1x+t_0(n-1\ge 0) g(x)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_1x+b_0 代入s(x)f(x)+t(x)g(x)=0 得到(s_{m-1}a_n+t_{n-1}b_m)x^{n+m-1} +(s_{m-1}a_{n-1}+s_{m-2}a_n+t_{n-1}b_{m-1}+t_{n-2}b_m)x^{n+m-2}+\ldots \displaystyle +\left(\sum_{j=1}^i s_{m-j}a_{n+j-i}+\sum_{k=1}^i t_{n-k}b_{m+k-i}\right)x^{n+m-i}+\ldots +(s_1a_0+s_0a_1+t_1b_0+t_0b_1)x +(s_0a_0+t_0b_0)=0 每個係數都是0，寫成矩陣形式 \left[0,\ldots,0\right]=\left[s_{m-1},\ldots,s_0,t_{n-1},\ldots,t_0\right] \left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr 0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&a_n&a_{n-1}&\ldots&a_0\cr b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr 0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&b_m&b_{m-1}&\ldots&b_0}\right] 其中\left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr 0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&a_n&a_{n-1}&\ldots&a_0\cr b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr 0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&b_m&b_{m-1}&\ldots&b_0}\right]為f(x)和g(x)的Sylvester矩陣 若\left[s_{m-1},\ldots,s_0,t_{n-1},\ldots,t_0\right]有非0解，則Sylvester矩陣的行列式值為0 Syl(f,g)=0 (2)當k=1時 若存在s(x)為次方m-2的多項式和t(x)為次方n-2多項式，且滿足s(x)f(x)+t(x)g(x)=0 則f(x)和g(x)至少有二個共同根。 因為f(x)的n個根也會是t(x)g(x)的根，但t(x)至多n-2次方，意指f(x)至少二個根也會是g(x)的根 將 s(x)=s_{m-2}x^{m-2}+s_{m-3}x^{m-3}+\ldots+s_1x+s_0(m-1\ge 0) f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0 t(x)=t_{n-2}x^{n-2}+t_{n-3}x^{n-3}+\ldots+t_1x+t_0(n-1\ge 0) g(x)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_1x+b_0 代入s(x)f(x)+t(x)g(x)=0 得到(s_{m-2}a_n+t_{n-2}b_m)x^{n+m-1} +(s_{m-2}a_{n-1}+s_{m-3}a_n+t_{n-2}b_{m-2}+t_{n-3}b_m)x^{n+m-2}+\ldots \displaystyle +\left(\sum_{j=1}^i s_{m-1-j}a_{n-1+j-i}+\sum_{k=1}^i t_{n-1-k}b_{m-1+k-i}\right)x^{n+m-1-i}+\ldots +(s_1a_0+s_0a_1+t_1b_0+t_0b_1)x +(s_0a_0+t_0b_0)=0 每個係數都是0，寫成矩陣形式 \left[0,\ldots,0\right]=\left[s_{m-2},\ldots,s_0,t_{n-2},\ldots,t_0\right] \left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr 0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&a_n&a_{n-1}&\ldots&a_0\cr b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr 0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr 0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr 0&0&0&b_m&b_{m-1}&\ldots&b_0}\right]	f(x)=x^4+x^3+x^2-x-2=(x^2-1)(x^2+x+2) g(x)=x^5+x^4-2x^2-x+1=(x^2-1)(x^3+x^2+x-1) (1)當k=0時 設s(x)=s_4x^4+s_3x^3+s_2x^2+s_1x+s_0 t(x)=t_3x^3+t_2x^2+t_1x^1+t_0 代入s(x)f(x)+t(x)g(x)=0 得到(s_4+t_3)x^8+ (s_4+s_3+t_3+t_2)x^7+ (s_4+s_3+s_2+t_2+t_1)x^6+ (-s_4+s_3+s_2+s_1-2t_3+t_1+t_0)x^5+ (-2s_4-s_3+s_2+s_1+s_0-t_3-2t_2+t_0)x^4+ (-2s_3-s_2+s_1+s_0+t_3-t_2-2t_1)x^3+ (-2s_2-s_1+s_0+t_2-t_1-2t_0)x^2+ (-2s_1-s_0+t_1-t_0)x+ (-2s_0+t_0)=0 每個係數都是0，寫成矩陣形式 \left[0,\ldots,0\right]=\left[\matrix{s_4,s_3,s_2,s_1,s_0,t_3,t_2,t_1,t_0}\right]\left[ \matrix{1&1&1&-1&-2&0&0&0&0\cr 0&1&1&1&-1&-2&0&0&0\cr 0&0&1&1&1&-1&-2&0&0\cr 0&0&0&1&1&1&-1&-2&0\cr 0&0&0&0&1&1&1&-1&-2\cr 1&1&0&-2&-1&1&0&0&0\cr 0&1&1&0&-2&-1&1&0&0\cr 0&0&1&1&0&-2&-1&1&0\cr 0&0&0&1&1&0&-2&-1&1}\right] \displaystyle \left[s_4,s_3,s_2,s_1,s_0,t_3,t_2,t_1,t_0\right]有無限多組解 \left[\frac{t_0-2t_1}{4},-\frac{t_0+2t_1}{4},-\frac{3t_0-2t_1}{4},\frac{t_0}{2},-\frac{t_0-2t_1}{4},\frac{t_0+2t_1}{4},t_1,t_0 \right] 例如取t_1=4,t_0=4，\left[s_4,s_3,s_2,s_1,s_0,t_3,t_2,t_1,t_0\right]=\left[-1,-3,-3,-1,2,1,3,4,4 \right] 符合(-x^4-3x^3-3x^2-x+2)f(x)+(x^3+3x^2+4x+4)g(x)=0 (2)當k=1時 設s(x)=s_3x^3+s_2x^2+s_1x+s_0 t(x)=t_2x^2+t_1x+t_0 代入s(x)f(x)+t(x)g(x)=0 得到(s_3+t_2)x^7+ (s_3+s_2+t_2+t_1)x^6+ (s_3+s_2+s_1+t_1+t_0)x^5+ (-s_3+s_2+s_1+s_0-2t_2+t_0)x^4+ (-2s_3-s_2+s_1+s_0-t_2-2t_1)x^3+ (-2s_2-s_1+s_0+t_2-t_1-2t_0)x^2+ (-2s_1-s_0+t_1-t_0)x+ (t_0-2s_0)=0 每個係數都是0，寫成矩陣形式 \left[0,\ldots,0\right]=\left[s_3,s_2,s_1,s_0,t_2,t_1,t_0\right]\left[ \matrix{1&1&1&-1&-2&0&0\cr 0&1&1&1&-1&-2&0\cr 0&0&1&1&1&-1&-2\cr 0&0&0&1&1&1&-1\cr 1&1&0&-2&-1&1&0\cr 0&1&1&0&-2&-1&1\cr 0&0&1&1&0&-2&-1}\right] \displaystyle \left[s_3,s_2,s_1,s_0,t_2,t_1,t_0\right]有無限多組解 \displaystyle \left[-\frac{t_0}{2},-\frac{t_0}{2},-\frac{t_0}{2},\frac{t_0}{2},\frac{t_0}{2},\frac{t_0}{2},t_0\right] 例如取t_0=2，\left[s_3,s_2,s_1,s_0,t_2,t_1,t_0\right]=\left[-1,-1,-1,1,1,1,2\right] 符合(-x^3-x^2-x+1)f(x)+(x^2+x+2)g(x)=0 (3)當k=2時 設s(x)=s_2x^2+s_1x+s_0 t(x)=t_1x+t_0 代入s(x)f(x)+t(x)g(x)=0 得到 (s_2+t_1)x^6+ (s_2+s_1+t_1+t_0)x^5+ (s_2+s_1+s_0+t_0)x^4+ (-s_2+s_1+s_0-2t_1)x^3+ (-2s_2-s_1+s_0-t_1-2t_0)x^2+ (-2s_1-s_0+t_1-t_0)x+ (-2s_0+t_0)=0 每個係數都是0，寫成矩陣形式 \left[0,\ldots,0\right]=\left[s_2,s_1,s_0,t_1,t_0\right]\left[\matrix{1&1&1&-1&-2\cr 0&1&1&1&-1\cr 0&0&1&1&1\cr 1&1&0&-2&-1\cr 0&1&1&0&-2} \right] \left[s_2,s_1,s_0,t_1,t_0\right]只有0解\left[0,0,0,0,0\right]

\left[\matrix{1&2 \cr 3 &4}\right]

https://en.wikipedia.org/wiki/Resultant
https://reference.wolfram.com/language/ref/Resultant.html
https://reference.wolfram.com/language/ref/Subresultants.html

假如m_1和m_2滿足隱含的多項式關係p(m_1,m_2)=0\pmod{N}
在這個範例我們有兩個未知數的三個同餘N多項式
P_1=p(m_1,m_2)=0\pmod{N}
P_2=m_1^e-c_1=0\pmod{N}
P_3=m_2^e-c_2=0\pmod{N}
使用resultant消除兩個多變數方程式的共同變數

resultant和gcd的運算，可以組合成Groebner basis


jsmath範例
http://web.archive.org/web/20200 ... amples/welcome.html

Howgrave-Graham	Durfee
q_{u,v}(x)=N^{h-1-v}x^up(x)^v	\displaystyle g_{i,k}(x)=x^i \left(\frac{p(x)}{N}\right)^k
以h=3,k=2為例計算det(M) M=\left[\matrix{N^2&&&&&\cr 0&N^2X^1&&&&\cr *&*&NX^2&&&\cr 0&*&*&NX^3&&\cr *&*&*&*&X^4&\cr 0&*&*&*&*&X^5}\right] *代表非零數字	以h=3,k=2為例計算det(M) M=\left[\matrix{\displaystyle 1&&&&&\cr 0&X^1&&&&\cr *&*&\frac{X^2}{N}&&&\cr 0&*&*&\frac{X^3}{N}&&\cr *&*&*&*&\frac{X^4}{N^2}&\cr 0&*&*&*&*&\frac{X^5}{N^2}}\right] *代表非零數字

解 ax \equiv b \pmod n
(1)若 gcd(a,n)=1
有唯一解
(2)若 gcd(a,n)=d>1
若d能整除b則有多組解
若d不能整除b則無解

例 12x \equiv 21 \pmod{39}
12和39的最大公因數為3且3能整除21，有多組解
先同除3， 4x \equiv 7 \pmod{13}
x \equiv 7 \times 4^{-1} \equiv 7 \times 10 \equiv 70 \equiv 5 \pmod{13}
∵ 4 \times 10\equiv 1 \pmod{13} ，∴ 4^{-1} \equiv 10 \pmod{13}
解為 \displaystyle x \equiv 5,5+1\times \frac{39}{3},5+2\times \frac{39}{3} \pmod{39}
x \equiv 5,18,31 \pmod{39}
但在maxima無法解出多組解
modulus:39;
solve(12*x=21,x);
只出現[x=18]一組解而已

解 x^2 \equiv n \pmod p 的方法
Cipolla's algorithm
http://en.wikipedia.org/wiki/Cipolla%27s_algorithm
Pocklington's algorithm
http://en.wikipedia.org/wiki/Pocklington%27s_algorithm
Tonelli–Shanks algorithm
http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

選擇e注意事項
1.e不可以太小
選e=3

TP 2:Coppersmith Attacks against RSA
http://www.jscoron.fr/cours/mics3crypto/tpcop.pdf
http://en.wikipedia.org/wiki/Coppersmith's_Attack
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
The Case for Elliptic Curve Cryptography
http://www.nsa.gov/business/programs/elliptic_curve.shtml
有RSA和橢圓曲線所需要的bits數的差異
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
數位簽章技術
http://ec2.ba.ntust.edu.tw/mic/d ... %89%E5%85%A8ch6.doc
Digital Signature Algorithm
http://en.wikipedia.org/wiki/Digital_Signature_Algorithm

RSA盲簽章
http://en.wikipedia.org/wiki/Blind_signature

Schnorr signature
http://en.wikipedia.org/wiki/Schnorr_signature

Elliptic Curve DSA
http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
可驗證的秘密分享(Verifiable Secret Sharing,VSS)

可公開驗證的秘密分享(Publicly Veriable Secret Sharing,PVSS)
VSS參與者只能驗證他自己本身所持有的子秘密是否正確，而無法得知其他參與者是否也收到正確的子秘密
在PVSS方法中，有一個公開驗證演算法可以驗證每位參與者所拿到的子秘密是否正確，
如果驗證時必須與分派者做數回合的互動式溝通，稱為interactive PVSS。
如果不需要和分派者互動的話，則稱為非互動式non-interactive PVSS
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
http://ccclab.csie.ntpu.edu.tw/c ... =title&sort=asc
Weighted Threshold RSA Based on the Chinese Remainder

也是祕密分享方案(待了解)
http://en.wikipedia.org/wiki/Proactive_secret_sharing
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

無需信賴者協助的秘密共享
http://130.203.133.150/viewdoc/summary?doi=10.1.1.14.202
論文下載
http://130.203.133.150/viewdoc/d ... p=rep1&type=pdf

橢圓曲線的書
http://books.google.com.tw/books ... ge&q&f=true

期貨及選擇權數位學習網
http://taifex.learn.hinet.net/elearn/

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