前面我们先是介绍了格理论基础，然后是格中难题与格基规约，又是 LLL 算法，铺垫了这么久，终于要引出格在公钥密码学中（尤其是 RSA 中）的一个重要应用了——Coppersmith’s Method。

不过这部分内容其实很久之前我在博客中就有写过了，这里就是稍加整理，然后修改了一些错误。

Coppersmith’s Method

首先我们直接挑明 Coppersmith’s Method 的作用。设存在一个模多项式，比如 ，如果该模多项式的根 ，即 ，“足够小”。那么就可以用 Coppersmith’s Method 去找到这个小根 。

如果说能将模数 分解，其实这个问题解出 是容易的，只需要分别在素因子的子群下解模多项式，然后用一个中国剩余定理即可。另外，如果我们能够找到一个解满足 并且这个 不等于 ，那么我们就可以通过欧几里得算法（GCD）将模数 进行分解。因此，我们并不希冀于有一个有效的算法对于所有这样的同余式都能找到解，否则也就意味着大数分解问题的破解了。

既然不能对所有的模多项式都能找到解，那能找到解的条件是啥呢？这里先给出的结论：对于度（degree）为 的多项式 ，如果 满足 并且，那么这个解 就能在多项式时间内被找到。

First Steps to Coppersmith’s Method

首先设我们有在模 下的度为 的并且系数为整数的首一多项式（）：【如果 ，我们可以对所有系数乘上一个 ，如果 在模 没有逆元，那么就意味着我们找到了 的一个因子，这条同余式就可以拆成同余式组，但这并不是这篇文章讨论的重点】假设我们知道存在一个整数 满足 并且 ，我们的任务就是找到这样的 。我们想，如果有这样一条多项式，他的解也是 。但是他的系数很小，满足【注意这里是等号，不是同余号】，那么我们就可以通过求根公式，或者牛顿迭代法等方式解方程从而计算出 了。而 Coppersmith’s Method 核心思路就是通过一些变换去将这个 规约为 。

第一颗🌰：

假设，,我们想找到一个小根 满足【这里的，但是在整数域下， 】

我们可以找到一个多项式 满足 ，这个解可以直接用求根公式得到。

好了，到这里你就已经掌握了 Coppersmith’s Method 的核心思想了。

接下来主要是对这个 的界的一些讨论以及如何尽量的提高这个界的一些手法。

我们定义为这个 取值的上界，

然后我们将 用向量的形式进行表示：

定理一：Howgrave-Graham

设我们有模多项式 ， 的上界为 ，模数 , 的向量形式 ，满足

那么，当，则有

证明

根据柯西不等式有  , 当 ，柯西不等式变形为

首先我们将 表示为 ，那么我们能够有如下不等式

我们将 的上界 带入，有

根据前面我们变形后的柯西不等式，和 的定义，我们有

因此，当，则有

于是有 ，又因为 ,  所以

PS: 这个定理对于估计 的界 很重要。

之前我们找到的 是直接给出的，现在介绍一下这个 该怎么去找，首先我们考虑度为 的多项式，再加一个 ，显然，这里一共 条式子，他们均有解 ，因此我们对其进行线性组合后得到的式子也仍然有解 ，例如 仍然是式子  的解。既然说到了线性组合，就不难想到矩阵了。

我们将这些式子的系数向量组合写为一个矩阵

其中 为 的取值上界。

矩阵进行变换，也就意味着这 条式子之间进行对应的线性组合。

这个矩阵是下三角矩阵，所以行列式为：

然后我们利用前面介绍过的 LLL 算法做一个格基规约，然后设规约后的矩阵的第一行行向量为 ，根据 LLL 算法的一个性质就是， 满足  ，所以

为了满足定理一，使得规约后的向量（也就是式子的系数）“足够小”，小到能够让我们直接解出方程的根，故要求 ，移项一下可得

如果 ，那么 ,如果 ，那么。

至此，我们大致有了一个 的取值范围，但这还并未达到 的程度，格子还需要进一步优化。。。

第二颗🌰：

设 ，多项式 ，【这里其实我们已经提前知道 ，所以满足】

这里我们设 的上界 ，所以我们构造格

利用 LLL 规约后我们得到第一行的行向量为 ，消去 后我们得到系数向量 ，对应多项式 ，然后再来个牛顿迭代法求根即可得到 。

The Full Coppersmith Method

这里回顾一下例子 2 ，即使以 来计算边界也应该是 4.3 左右，那为什么我们设 最终也可以得到正确的结果呢？其次，如果不取这个约来的边界,而是直接将 带入 来计算这个 的边界，其实边界值应该是 左右。嗯？那为啥我们可以得到正确结果呢？因为其实这个边界值也并不是很严格，在推导得出这个值的时候本身就用了很多次不等式，再者，我们利用的LLL中的那个性质，，我们取的是 LLL 算法规约出来的最坏的情况，而大多数情况得到的结果要比这值小许多。

回到这一章的主题，在上一章中我们对 的取值有不等式：，稍微还原一下是 ，所以想要增加 就有两个思路，一个增加格的维度 ，第二个就是增大 了。

针对第一种方案，我们称这种往格里插入的，增加了格的维度而不增加 的多项式为：“x-shift” polynomial，它们是，显然这些多项式在 下的解也为。

针对第二种方案，我们可以利用 的幂次来增加 ，因为 ，则有

我们沿用例子 2 ，之前我们用到的格的维度 ，所以将 带入不等式我们可以得到 ，带入 可得 ，现在我们往格中添加两个多项式，得到

现在我们格的维度为 ，并且行列式为 ，带入不等式可得，现在算出来 ，可以看到通过添加 “x-shift” polynomial，我们确实增大了 。

这里有一个现成的结论就是通过添加 “x-shift” polynomial：，我们可以使得，所以当，通过 “x-shift” polynomial，我们将  提升为。那么如果在此基础上再使用第二种方法增加 呢？

定理 2 Coppersmith

设 ， 是度为 的首一多项式，如果其在域 下有一个或多个根 满足，那么我们就可以在与 相关的多项式时间内找到它，

证明

设，以多项式：,  构造格 ，注意到 ，那么格 的维度就是 ，其行列式

此时我们运用 LLL 算法进行规约，我们得到第一行的行向量 ，其满足

由于这里的模数 已经提升为，这里我们再用上定理 1，从而有,

变形一下为：

这里我们换元一下，设，那么我们有

注意到，我们设 ，那么有 ,并且 ，所以，当 趋向于0时， 趋向于，

因为之前我们有 ，带入 就是 ，又因为满足 ，那么我们需要 即 。这里我们再次换元，设 ，那么 ,所以我们要求 ，因为，所以 ，解得 ，

结合上面提到的：，由于，并且，所以当时，,当，

运行 LLL 算法用时肯定是跟格的维度，格里面数值大小有关的，又由 ,所以格   的维度 ，所以时间复杂度与 有关。一个现成的结论：Coppersmith‘s Method 的大致时间复杂度为 ，

第三颗🌰：

设

并且我们事先知道 ，所以我们设 ，注意到 。这里我们构造格

注意到，我们这里并没有像证明中的那样，加上所有的 ，这里我们只添加量两条 “x-shift” polynomial，额外添加了一条，第四行为 。理论上我们还可以针对 再添加两条“x-shift” polynomial，但这里并没有这么做，是综合考虑了到 的上界 ，和LLL算法运行的时间复杂度。所以这里格的维度是 ，行列式。

这里运行LLL算法，并将第一行的行向量的相应 值去除得到系数向量，可得

运算求根算法可得

这些就是单元 Coppersmith’s Method 理论部分的内容了，下一篇文章我们将结合 RSA ，介绍一些适用 Coppersmith’s Method 的攻击场景。