事实上在第一届OpenHarmony CTF专题赛（线上选拔赛）Crypto Write UP | Triode Field的时候就已经做到过ACD问题了，但是当时是现学现做的，并没有做系统性的学习和分析，趁着暑假来补习一下（笑）
近似公约数问题（ACD Problem）
对于给定的\(\gamma,\eta,\rho\in\mathbb{N}\)，对于一个\(\eta\)-bit的奇数\(p\)，定义如下高效采样分布\(\mathcal{D}_{\gamma,\rho}(p)\)：
$$
\mathcal{D}_{\gamma,\rho}(p)=\left\{pq+r|q\in\mathbb{Z}\cap\left[0,\frac{2^{\gamma}}{p}\right),r\in\mathbb{Z}\cap\left(2^{-\rho},2^{\rho}\right)\right\}
$$
对于该采样分布，有\(\rho\ll\eta\)，所以任取\(x\in\mathcal{D}_{\gamma,\rho}(p)\)，都有极大概率满足\(x<2^{\gamma}\)，那么对于一个充分大的整数\(t\)，从\(\mathcal{D}_{\gamma,\rho}(p)\)中取\(t\)个样本\(x_1,x_2,\cdots,x_{t}\)，那么所谓近似公约数问题（Approximate Common Divisor Problem, ACD）即为从给定的\(t\)个样本\({x_1,x_2,\cdots,x_{t}}\)中恢复出\(p\).
部分近似公约数问题（PACD Problem）
所谓部分近似公约数问题（Partial Approximate Common Divisor Problem, PACD），即为在ACD问题的样本基础上加上了一个特殊样本\(x_0=pq_0\)（其中\(q_0\)与\(\mathcal{D}_{\gamma,\rho}(p)\)中\(q\)的取值范围一致），从给定的\(t+1\)个样本\({x_0,x_1,x_2,\cdots,x_{t}}\)中恢复出\(p\).
近似公约数问题的求解方法
求解ACD主流的方法有三种：SDA(Simultaneous Diophantine approximation approach), OL(Orthogonal based approach)以及MP(Multivariate polynomial approach)，在此仅介绍SDA.
同步丢番图逼近方法（SDA）
这是求解ACD的方法中最简单的一种，大致思想就是对于从\(\mathcal{D}_{\gamma,\rho}(p)\)采样出的\({x_0,x_1,\cdots,x_t}\)（此处\(x_0\)为一般样本），当\(\rho\)很小的时候（也就是\(r_0,r_1,\cdots,r_t\)都很小的时候），对于\(1\le i\le t\)，总有：
$$
\frac{x_i}{x_0}=\frac{pq_i+r_i}{pq_0+r_0}\approx\frac{q_i}{q_0}
$$
很显然，\(q_i/q_0\)是\(x_i/x_0\)的同步丢番图近似（simultaneous Diophantine approximation），事实上有：
$$
q_ix_0-q_0x_i=q_i(pq_0+r_0)-q_0(pq_i+r_i)=pq_0q_i+q_ir_0-pq_0q_i-q_0r_i=q_ir_0-q_0r_i
$$
所以必然有\(|q_ix_0-q_0x_i|\approx2^{\rho+\gamma-\eta+1}\)，那么可以通过这个关系构造格基：
$$
\pmb{B}=\left(\begin{matrix}
2^{\rho+1}&x_1&x_2&\cdots&x_t\\
&-x_0&&&\\
&&-x_0&&\\
&&&\ddots&\\
&&&&-x_0
\end{matrix}\right)
$$
对于这个格有如下关系：
$$
\begin{aligned}
(q_0,q_1,\cdots,q_t)\pmb{B}&=(2^{\rho+1}p_0,q_0x_1-q_1x_0,\cdots,q_0x_t-q_tx_0)\\
&=(2^{\rho+1}p_0,q_0r_1-q_1r_0,\cdots,q_0r_t-q_tr_0)
\end{aligned}
$$
显然对目标向量\((2^{\rho+1}p_0,q_0r_1-q_1r_0,\cdots,q_0r_t-q_tr_0)\)有：
$$
||(2^{\rho+1}p_0,q_0r_1-q_1r_0,\cdots,q_0r_t-q_tr_0)||\approx2^{\rho+\gamma-\eta+1}\sqrt{t+1}
$$
又对于格基矩阵，有：
$$
|\det(\pmb{B})|=2^{\rho+1}x_0^t\approx2^{\rho+\gamma t+1}
$$
那么由高斯启发式可知当
$$
2^{\rho+\gamma-\eta+1}\sqrt{t+1}\le\sqrt{\frac{t+1}{2\pi e}}\cdot|\det(\pmb{B})|^{1/(t+1)}\approx2^{(\rho+\gamma t+1)/(t+1)}\sqrt{t+1}
$$
成立，即：
$$
\begin{aligned}
&\rho+\gamma-\eta+1\le \frac{\rho+\gamma t+1}{t+1}\\
\Rightarrow&\rho-\eta+1\le\frac{\rho+\gamma t+1-\gamma t-\gamma}{t+1}=\frac{\rho-\gamma+1}{t+1}\\
\Rightarrow&t+1\le\frac{\gamma-\rho-1}{\eta-\rho-1}<\frac{\gamma-\rho}{\eta-\rho}\\
\Rightarrow&t+1<\frac{\gamma-\rho}{\eta-\rho}
\end{aligned}
$$
的时候，可以从这个格中规约出目标向量\((2^{\rho+1}p_0,q_0r_1-q_1r_0,\cdots,q_0r_t-q_tr_0)\)，此时我们可以从目标向量中获得\(q_0\)，因为\(r_0\)很小，所以有\(x_0\equiv pq_0+r_0\equiv r_0\pmod{q_0}\)，那么我们可以得到\(r_0=x_0\mod{q_0}\)，从而计算出\(p=\frac{x_0-r_0}{q_0}\).