Coppersmith part1-----原理

概述

首先我们假设我们在$modM$下有度为$d$的系数为整数的首一多项式(对于如何将多项式转换为首一多项式，这里不做阐述):$F(x)=x^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0{\pmod{M}}$

我们要求的是$F(x)\equiv0\pmod{M}$的小根$x_0$（即$F(x_0)\equiv 0\pmod{M}$）

我们先假设有这样一个多项式$G(x)$，它每一项的系数很小，且它和$F(x)$有相同的小根$x_0$（即满足$G(x_0)=0$），那我们如果知道了这样一个$G(x)$，我们就可以通过一些求根方法（例如求根公式，牛顿迭代法等）求出$x_0$

Coppersmith的核心即是通过一些变换将$F(x)$规约为$G(x)$，所以我们的问题核心就转变成了如何规约出$G(x)$

转换域的范围

要从$F(x_0)\equiv 0\pmod{M}$变为$G(x_0)=0$，需要将$modM$下转到整数域范围下，如何转换则需要用到下面这条定理：

Howgrave-Graham

设我们有$F(x)=\sum_{i=0}^{d}a_ix_i\pmod{M}$，且对于$F(x)\equiv0\pmod{M}$有小根$x_0$满足$|x_0|\le X$。对于$F(X)$，我们将其用以下向量形式表示：$b_{F}=(a_0,a_1X,a_2X^2,\cdots,a_dX^d)$。若$\Vert{b_F}\Vert<{M\over\sqrt{d+1}}$，则有$F(x_0)=0$

请输入图片描述

这里的证明直接偷Van1sh师傅的（逃

总的来说就是，我们只要确定$x_0$的上界$X$，且对于$X$它满足$\Vert{b_F}\Vert<{M\over\sqrt{d+1}}$这样一个条件，这个$x_0$就必然满足$F(x_0)=0$，这样就从一个$modM$的域转到了整数域的范围。

然后问题就转换成了如何让$\Vert{b_F}\Vert<{M\over\sqrt{d+1}}$这条式子成立。

归约系数

我们来观察一下$\Vert{b_F}\Vert<{M\over\sqrt{d+1}}$这条式子，该式右半部分很明显是确定值无法改变。那为了让该式成立，只能从$\Vert{b_F}\Vert$下手。我们将$\Vert{b_F}\Vert$展开：$\Vert{b_F}\Vert=\sqrt{\sum_{i=0}^{d}a_iX^i}$，可以发现这里面我们只能去想办法减小$a_i$，也就是去通过一些手段去减小多项式的各项系数。

那对于如何减小多项式系数，我们可以想到对一些有相同根的多项式方程进行线性组合即可减小多项式系数。那除了原多项式$F(x)$，我们还可以想到这样一系列多项式$G_i(x)=Mx^i\pmod{M}$（很明显在$modM$下$G_i(x)=0$），它们都满足在$modM$下有$x_0$这个根。所以我们可以令$G(x)=t_dF(x)+\sum_{i=0}^{d-1}t_iG_i(x)$（此处$t$为线性组合所带来的常向量）。这个形式很容易让我们联想到可以使用格基规约的手段来找到一组小系数：我们把每组$G_i(x)$和$F(x)$这样的多项式系数都看做一个$d+1$维的一个向量（很明显它们之间都线性无关，所以能构成该格的一组基，后面同理就不强调了），然后这样$d+1$组向量就构成了一个$d+1$维的一个格，减小系数其实就相当于是在这样的一个$d+1$维的格里找到它的最短向量（最短肯定就系数最小啦）

看上去上面说的好像没什么问题，但是我们得注意一个点我们最终的目的是满足$\Vert{b_F}\Vert<{M\over\sqrt{d+1}}$，进行约简系数后也就是$G(x)$所对应的${b_G}=(t_0M+t_na_0,t_1MX+t_na_1X,\cdots,t_{n-1}M+t_na_{n-1}X^{n-1},t_nX^n)$应当满足$\Vert{b_G}\Vert<{M\over\sqrt{d+1}}$。但是如果按照以上说法进行规约的话，它每一项的系数量级是相当的，并没什么明显的差距，可是乘上$X^i$后很明显差距就特别大了。那我们想让$\Vert{b_G}\Vert$尽可能的小，很明显需要让每项尽可能的小的情况下量级接近（换句话来说，就不能有一块特别大？某项量级太大就会拉高整体）

所以我们在构造格的时候，应当依据$G(x)$对应的${b_G}$进行构造（或者说是以$G(xX)=t_dF(xX)+\sum_{i=0}^{d-1}t_iG_i(xX)$进行构造？具体定义看补充），于是我们就能得到这样一个格：

$$ L=\left(\begin{matrix} M & & && & \\ & MX & && & \\ & & MX^2 && & \\ &&&...\\ & & & &MX^{n-1}& \\ a_0 & a_1X & a_2X^2 && a_{n-1}X^{n-1} & X^n\\ \end{matrix}\right) $$

它满足$tL=b_G$，所以我们对格$L$规约之后，我们就能得到尽可能短的$b_G$向量了。

得到该向量之后，我们只需要将每项的$X^i$除去，就得到了$G(x)$的系数，这样我们就成功的规约出了满足我们需求的$G(x)$。

补充：

$F(xX)=x^dX^d+a_{d-1}x^{d-1}X^{d-1}+\cdots+a_1xX+a_0{\pmod{M}}$
$G_i(xX)=G_i(x)*X^i$

界限

我们进行规约时用的是LLL算法，根据LLL算法的性质：规约出来的首行行向量$b$（也就是我们的$b_G$）满足：$\Vert{b}\Vert\le2^{n-1\over4}det(L)^{1\over n}$（此处$n$为所造格$L$的维度，所以此处$n=d+1$），此处可以进行下计算:$det(L)=M^dX^{d(d+1)\over 2}$，最后算出来即：$\Vert{b}\Vert\le2^{d\over4}M^{d\over{d+1}}X^{d\over2}$

然后还要让$b$满足Howgrave-Graham：$\Vert{b}\Vert<{M\over{\sqrt{d+1}}}$，为了让该条件一定能成立，我们用$2^{d\over4}M^{d\over{d+1}}X^{d\over2}$来替换$\Vert{b}\Vert$，也就是：$2^{d\over4}M^{d\over{d+1}}X^{d\over2}<{M\over{\sqrt{d+1}}}$，移项之后就是：$2^{d\over4}\sqrt{d+1}X^{d\over2}$

至此我们就得到了个大概的范围。

界限提升

先摆出我们上面所求出的界限：$2^{d\over4}\sqrt{d+1}X^{d\over2}<M^{1\over{d+1}}$，换一种形式也可以写成：$det(L)<M^{d+1}$
这里我们一共有两种思路来提升Coppersmith的界限：一种是往格中插入对$det(L)$贡献值小于$M$的行向量增大格$L$的维度（每增加一行，不等式右边相当于乘上一个$M$，所以只要新增的一行中对$det(L)$贡献小于$M$，就能扩大$X$界限）。另一种则是增加$M$的幂次。
那么针对第一种思路，我们可以想到如下多项式：$xF(x),x^2F(x),\cdots,x^kF(x)$，我们称他们为"x-shift"多项式。那么此时$G(x)=t_{d+k}x^kF(x)+\cdots+t_{d+1}xF(x)+t_dF(x)+\sum_{i=0}^{d-1}t_iG_i(x)$，我们可以造出以下这种形式的格：
$$L=\left(\begin{matrix}M & & && & \\ & MX & && & \\ & & MX^2 && & \\&&&...\\ & & & &MX^{n-1}& \\a_0 & a_1X & a_2X^2 && a_{n-1}X^{n-1} & X^n\\&a_0X&a_1X&&&a_{n-1}X^n&X^{n+1}\\&&&\ddots&&&&\ddots\\&&&a_0X^{k}&a_1X^{k+1}&&&&&a_{n-1}X^{n+k-1}&X^{n+k}\end{matrix}\right)$$
再来说对于第二种思路，我们有$F(x)\equiv0\pmod{M}$，我们要增加$M$的幂次，于是我们根据同余的性质可以得到有$F^k(x)\equiv0\pmod{M^k}$。但很明显增大幂次会造成格的维度扩大，所以我们通常会配合第一种方法一起使用。由于此时的模数变为了$M^k$，而我们上边所构造的$G_i(x)$和"x-shift"多项式都是在模数为$M$的情况，所以我们需要让它们在$M^k$下，我们可以让他们都乘上一个$M^{k-1}$。这里不好将通用格表述出来，就直接贴原文给出的例子，大家伙看着理解一下吧：
请输入图片描述
格中依次为$MG_i(x),MF(x),MxF(x),Mx^2F(x)$和$F^2(x)$
至此Coppersmith的原理算是讲完了

N1gh7ma12e的生活日志

Coppersmith part1-----原理

概述

转换域的范围

归约系数

界限

界限提升

参考文章

Comment/ Cancel Comment