[数据结构与算法] 近似公因数问题（Approximate Common Divisor Problem，ACDP）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 近似公因数问题（Approximate Common Divisor Problem，ACDP） -> 正文阅读

[数据结构与算法]近似公因数问题（Approximate Common Divisor Problem，ACDP）

前言

给定两个整数 $a$ 和 $b$ ，存在整数 $d$ ，使得 $d ∣ a$ 并且 $d ∣ b$ 。即 $d$ 同时整除 $a$ 和 $b$ ，我们把 $d$ 叫做 $a$ 和 $b$ 的公因数，满足条件的 $d$ 的最大值，叫做 $a$ 和 $b$ 的最大公因数（GCD）。
通过辗转相除法或者错位相减法，可以在多项式时间内求出 $a$ 和 $b$ 的最大公因数。
现在，我们考虑， $a$ 和 $b$ 在传输的过程中出现了一些小错误。得到 $a^\prime=a+e_1$ 和 $b^\prime=b+e_2$ ，那么是否可以在多项式时间内求出 $d$ 。这就是站在解码的角度的近似公因数问题。

定义

论文：《Approximate Integer Common Divisors》中仔细讨论了这个问题。
更加正式的描述如下：
给定两个整数 $a_0$ 和 $b_0$ ，参数 $X, Y, M$ 。近似公因数问题是寻找这样一个或者所有的 $d > M$ ，使得 $d|(a_0+x_0)$ 和 $d|b_0+y_0$ ，其中 $|x_0| \neq X$ ， $|y_0| \neq Y$ 。
不妨设 $\geq Y$ ，如果 $Y = 0$ ，那么问题叫做部分近似公因数问题（Partially Approximate Common Divisor Problem，PACDP）；如果 $Y > 0$ 那么叫做一般的近似公因数问题（General Approximate Common Divisor Problem，GACDP）。