近似公约数问题 (ACD)
事实上在第一届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}\).