RSA \(n=p^rq\) | RSA \(n=p^rq^s\) |
產生公鑰和私鑰 | |
| 產生兩個隨機質數\(p,q\) 計算\(n=p^r q\) 計算\(L=LCM(p-1.q-1)\) 找\(e,d\)符合\(ed \equiv 1\pmod{L}\)和\(GCD(e,p)=1\) \(e,n\)是公鑰，\(d,p,q\)是私鑰 | 產生兩個隨機質數\(p,q\) 計算\(n=p^rq^s\) 計算\(L=LCM(p-1,q-1)\) 找\(e,d\)符合\(ed\equiv 1\pmod{L}\)和\(GCD(e,L)=GCD(e,n)=1\) \(e,n\)是公鑰，\(d,p,q\)是私鑰 |
加密 | |
| \(c\equiv m^e \pmod{n}\) \(m\)為明文，\(c\)為密文 | 相同 |
解密 | |
| \(m\equiv c^d \pmod{n}\) | 無法使用\(m\equiv c^d \pmod{n}\)來回復明文 |
利用中國餘數定理快速解密 | |
| \(m_q\equiv c^d\pmod{q}\) 設\(d_q\equiv d\pmod{q-1}\)，\(m_q\equiv c^{d_q}\pmod{q}\) 利用中國餘數定理 \(m\equiv (m_p\cdot q(q^{-1}\pmod{p^r})+m_q\cdot p^r(p^{-r}\pmod{q}))\pmod{n}\) \(m_p\equiv m\pmod{p^r}\)的\(m_p\)無法用\(m_p\equiv c^d\pmod{p^r}\)直接計算 改用以下的方法計算\(m_p\) | 利用中國餘數定理 \(m\equiv (m_p\cdot q^s(q^{-s}\pmod{p^r})+m_q\cdot p^r(p^{-r}\pmod{q^s}))\pmod{n}\) \(m_p\equiv m\pmod{p^r}\)的\(m_p\)無法用\(m_p\equiv c^d\pmod{p^r}\)直接計算 \(m_q\equiv m\pmod{q^s}\)的\(m_q\)無法用\(m_q\equiv c^d\pmod{q^s}\)直接計算 改用以下的方法計算\(m_p,m_q\) |
問題敘述 令\(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)\) | 當\(a\)和\(b\)都同時\(\le 0(Case2)\) |
| \(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}\) | |
方法 | 範例 |
問題敘述 | |
步驟1： | |
步驟2： | |
步驟3： | |
步驟4： | |
| 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)\) |
| 找共同根-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]\) |
| 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]\) *代表非零數字 |
| 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個元素。 |
void main()
{
for(i=0;i<5;i++)
{printf(i);
}
}| 離散對數問題 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 |
| \(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\)化簡結束 |
| \(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\)化簡結束 |
| \(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\)化簡結束 |
| \( \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} \) |
| 歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) | 論壇程式使用 Discuz! 6.1.0 |