为什么遗传算法不能解决 RSA 分解等问题？

Question

前段时间我对 GA 非常感兴趣，并且对它们进行了很多研究。我使用 C++ GAlib 编写了一些程序，我对它们在几秒钟内解决其他难以计算的问题的能力感到非常惊讶。它们似乎是一种很棒的暴力破解技术，非常聪明且适应性强。

我正在读 Michalewitz 的一本书，如果我没记错书名的话，它似乎都是基于麻省理工学院证明的图式定理。

我还听说它不能真正用于解决诸如分解 RSA 私钥之类的问题。

有人可以解释为什么会出现这种情况吗？

Answer 1

遗传算法根本不聪明，它们是非常贪婪的优化算法。他们都围绕同一个想法工作。您有一组点（“一群个体”），然后使用随机运算符将该组转换为另一个点，并偏向最佳改进的方向（“突变+交叉+选择”）。重复直到它收敛或者你厌倦了它，那里没有什么聪明的地方。

为了使遗传算法发挥作用，新的点群的性能应接近之前的点群。小小的扰动应该不会产生什么变化。如果在对一个点进行小扰动之后，您获得了一个代表性能完全不同的解决方案的点，那么该算法并不比随机搜索更好，而随机搜索通常是一种不好的优化算法。在 RSA 的情况下，如果你的点直接是数字，那么它要么是，要么不是，只需翻转一下......因此，如果你代表 RSA 问题而不需要太多思考，那么使用遗传算法并不比随机搜索更好“让我们代码搜索点作为数字的位"

Answer 2

我会这么说，因为键的因式分解不是优化问题，而是精确问题。这种区分不是很准确，这里详细说明。
遗传算法非常适合解决最小值（局部/全局）的问题，但在因式分解问题中没有最小值。遗传算法如 DCA 或模拟退火需要衡量“我与解决方案的接近程度”，但你不能对我们的问题这么说。

举个遗传学良好的问题的例子，有爬山问题。

Answer 3

遗传算法基于候选解决方案的适应性评估。

基本上，您有一个适应度函数，它将候选解决方案作为输入，并返回一个标量，告诉您该候选解决方案有多好。然后，您继续允许给定一代中最好的个体以比其他个体更高的概率进行交配，以便后代（希望）整体上更加“适应”，等等。

在 RSA 分解场景中，无法评估适应性（候选解决方案与其他解决方案相比有多好），因此您不能使用它们。

Answer 4

遗传算法不是暴力破解，它们只是一种搜索算法。每个 GA 本质上都是这样的：

candidates = seed_value;
while (!good_enough(best_of(candidates))) {
    candidates = compute_next_generation(candidates);
}

其中 good_enough 和 best_of 是根据适应度函数定义的。适应度函数表示给定候选人解决​​问题的能力。这似乎是这里的核心问题：如何编写因式分解的适应度函数？例如 20 = 2*10 或 4*5。元组 (2,10) 和 (4,5) 显然是赢家，但是其他元组呢？ (1,9) 或 (3,4) 的“拟合度”如何？

Answer 5

间接地，您可以使用遗传算法对整数 N 进行因式分解。Dixon 的整数因式分解方法使用涉及前 k 个素数的幂（以 N 为模）的方程。这些幂的乘积小素数被称为“平滑”。如果我们使用前k=4素数 - {2,3,5,7} - 42=2x3x7 是平滑的，而 11 则不是（由于缺乏更好的术语，11 是“粗糙”） ）。 Dixon 方法需要一个由定义这些平滑数的指数组成的可逆 k x k 矩阵。有关 Dixon 方法的更多信息，请参阅 https://en.wikipedia.org/wiki/Dixon%27s_factorization_method< /a>.

现在，回到最初的问题：有一种遗传算法可以为迪克森方法找到方程。

1. 令 r 为平滑数 mod N 的倒数 - 因此 r 为粗略数
2. 令 s 为平滑数
3. 生成 rx = sy 的随机解mod N。这些解 [x,y] 是遗传算法的总体。每个 x、y 都有一个平滑分量和一个粗糙分量。例如，假设 x = 369 = 9 x 41。然后（假设 41 不够小，不足以算作平滑），x 的粗糙部分为 41，平滑部分为 9。
4. 选择解对 - “父项” - 进行组合与更小的粗糙零件进行线性组合。
5. 当找到具有粗略部分 [1,1]、[1,-1]、[-1,1] 或 [-1,-1] 的一对 [x,y] 时，算法终止。这产生了 Dixon 方法的方程，因为 rx=sy mod N 和 r 是剩下的唯一粗略数字：x 和 y 很顺利，s一开始也很顺利。但即使 1/r mod N 也是平滑的，所以一切都很平滑！

每次组合两对时 - 比如说 [v,w] 和 [x,y] - 四个数字的平滑部分都会被消除，除了 v 和 x 的平滑部分共享的因子以及 的平滑部分的因子之外w 和 y 共享。所以我们选择最大程度共享光滑部分的父母。为了使这个精确，写

g = gcd(v 的平滑部分，x 的平滑部分)

h = gcd(w 的平滑部分，y 的平滑部分)

[v,w], [x,y] = [gv/g ，hw/h]，[gx/g，hy/h]。

来之不易的平滑因子 g 和 h 将保留到下一代中，但 v/g、w/h、x/g 和 y/h 的平滑部分将被牺牲，以便将 [v,w] 和[x，y]。因此，我们选择 v/g、w/h、x/g 和 y/h 具有最小平滑部分的父级。通过这种方式，我们确实将 rx = sy mod N 解决方案的粗糙部分从一代推向下一代。

Answer 6

进一步思考，获得网格 ax = by mod N 中的平滑系数 x, y 的最佳方法是回归，而不是遗传算法。

执行两个回归，一个回归由来自随机选择的 ax = by mod N 解的 x 值组成的响应向量 R0 组成；另一个具有由相同解的 y 值组成的响应向量 R1。两个回归都使用相同的解释矩阵 X。X 中的列由 x 值模平滑除数的余数组成，其他列由 y 值模其他平滑除数的余数组成。

平滑除数的最佳选择是使每次回归的误差最小化的除数：

E0 = R0 - X ((X-转置)(X)) (X-转置) (R0)

E1 = R1 - X ((X-转置)(X) 的逆(X-转置)(X)) (X-转置) (R1)

接下来是消除 X 的行运算。然后将这些行运算的结果 z 应用于原始解中的 x 和 y 值由其形成X。

z R0 = z R0 - 0
     = z R0 - zX (inverse of (X-transpose)(X)) (X-transpose) (R0)
     = z E0 

类似地，z R1 = z E1

z R0 和 z R1 现在组合了三个属性：

• 它们是大平滑数的倍数，因为 z 消除了模平滑数的余数。
• 它们相对较小，因为 E0 和 E1 较小。
• 与 ax = by mod N 解的任何线性组合一样，z R0 和 z R1 本身就是该方程的解。

大平滑数的相对较小的倍数可能就是平滑数本身。通过 mod N 平滑求解 ax = 会产生 Dixon 方法的输入。

两项优化使其速度特别快：

• 无需立即猜测 X 的所有平滑数字和列。您可以连续运行回归，一次向 X 添加一列，选择减少 E0 和 E1 最多的列。任何时候都不会选择任何两个具有公因数的平滑数。
• 您还可以从 zx = by mod N 的许多随机解开始，并删除 X 的新列选择之间误差最大的解。