格相关的AGCD问题
- 已知给定的 n 组 xi 满足：
x_i=pq_i+r_i
其中 xi 已知，并且 p 的位数 α 远大大于 ri 的位数 ρ ，以此满足近似的 GCD 关系，我们就可以构造以下矩阵：
S=
\begin{bmatrix}
2^{ρ} & x_{1} & \cdots & x_{n} \\
0 & -x_{0} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots\ & -x_{0} \\
\end{bmatrix}
可以规约出以下向量：
（q_02^ρ,q_0r_1-q_1r_0,......,q_0r_n-q_nr_0）
将向量的第一位出去系数即可得到 q0 ，进一步得到 p（xi/q0）；
Comments NOTHING