Way to CopperSmith

整体思路

利用构造多项式技巧，构造出多项式，形成一个格，然后进行规约，得到较小范数的多项式，然后通过结式求解（有时也有其他办方，比如直接系数gcd，多项式gcd或是Gröbner basis等，May’s origin attack on CRT-RSA就出现了好几种方法）小范数多项式，即可得到原多项式在一定范围下的所有根。本质思想其实就是把有限域上的方程转化到整数域，而转化的界限就是由柯西-施瓦茨不等式给出的。

理论基础

Howgrave-Graham’s Lemma

此定理的意义在于，如果找到了符合约束的多项式\(h\)，则\(h\)在模\(N\)上的所有小根也即是\(h\)在整数域上的所有小根，也就是说，我们可以将有限域上的多项式转化为整数域上的多项式。

LLL

即是格基约化，这里的作用即是通过对构造出的特定的格的约化而产生符合约束的多项式\(h\)，然后通过结式将多元方程转化成一元方程式，之后解整数域上的一元方程即可。

通过以上事实，可以看到LLL至少可以找到两组满足约束的向量，也就保证了在规定条件下结式有解的可能性。

构造多项式

Jochemsz-May Strategy

Modular

Basic Strategy

先算出m及\(f_N^m\)，然后使\(k\)遍历\([0, m]\)，计算\(M_k\)，指定\(l\) 并根据以下公式，计算多个多项式，构成格基。

例子如下

这样的构造是为了保证，最终构造的多项式里的每个单项式都是\(f_N^m\)中的单项式。

要注意的是，并不是说构造出来的多项式需要严格是以上形式，这只是提供了一种总体构造思想。

Extended Strategy

针对某个变量的extended strategy，是为了得到更好的界，有时也可以通过一些关式构造出新的变量用来shift。

相关知识学习

Gröbner basis

仿射簇与理想

可以看到仿射簇是一组多项式公共根的集合。

理想与子空间类似，不同的是子空间我们使用标量相乘的线性组合，而理想使用多项式相乘的线性组合。

可以根据一个仿射簇的所有根来定义理想，其内所有多项式的根均包含仿射簇中所有根。

可以根据仿射簇定义理想，同样可以根据理想定义仿射簇，但通过这样的嵌套的结果不一定总是相等。

多项式间gcd性质与整数基本一致

序与单项式理想

由于通过总结多项式除法和高斯消元法，意识到‘序’的意义，故这里定义多元单项式的一种比较的序。

同时我们知道定义一个序是好的，当且仅当它不存在无穷递减序列。

这里通过比较向量差的首个非零向量来作为一个序（此即lex order，类似于字符串的字典序比较法）

考虑到纯字典序有不妥，这里将向量的范数也引入，优先以范数比较，再其次以字典序比较

也可以定义反向字典序（即从最右边变量开始比较，且最右边小的在前面）

对于一个多项式，定义诸多概念如上

于是有朴素的定理如上。

这里定义了多元变量的多项式除法，主要点在于除的对象是一组多项式，具体操作与单元多项式除法类似，通过leading term判断是否结束除法，依次除各个多项式即可。若\(f\) 对于\(f_1, f_2, \dots,f_s\)做除法余数为0，则\(f \in <f_1,\dots,f_s>\)，即\(f\)属于由这组多项式生成的理想。于是考虑想找一种好的basis，使得任意多项式除此basis的余数唯一确定。