7

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

我正在读 Michalewitz 的一本书，如果我没记错名字的话，它似乎都是基于 MIT 证明的模式定理。

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

谁能解释为什么会这样？

4

6 回答 6

12

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

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

于 2011-03-28T08:54:26.330 回答
4

我会说因为键的分解不是一个优化问题，而是一个确切的问题。这种区分不是很准确，所以这里有细节。遗传算法非常适合解决最小值（局部/全局）的问题，但分解问题中没有。作为 DCA 或模拟退火的遗传算法需要衡量“我与解决方案的距离”，但对于我们的问题，您不能这么说。

例如，问题遗传学很好，有爬山问题。

于 2011-03-28T08:52:27.390 回答
2

遗传算法基于候选解的适应度评估。

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

在 RSA 分解场景中，无法评估适合度（候选解决方案与其他解决方案相比有多好），这就是您不能使用它们的原因。

于 2011-03-28T12:47:21.483 回答
1

GA 不是暴力破解，它们只是一种搜索算法。每个 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) 有多“合适”？

于 2011-03-28T08:54:22.543 回答
1

间接地，您可以使用遗传算法来分解整数 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。

现在，回到最初的问题：有一个遗传算法可以找到 Dixon 方法的方程。

  1. 令r为平滑数 mod N 的倒数 - 所以r是一个粗略数
  2. 让我们顺利
  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,w] 和[x,y]。因此，我们选择 v/g、w/h、x/g 和 y/h 具有最小平滑部分的父项。通过这种方式，我们确实将我们解决方案的粗糙部分从一代推到了下一代。

于 2017-05-17T01:50:03.930 回答
0

进一步思考，通过 mod N 在格子 ax = 中平滑系数 x、y 的最佳方法是回归，而不是遗传算法。

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

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

E0 = R0 - X（（X-转置）（X）的倒数）（X-转置）（R0）

E1 = R1 - X（（X-转置）（X）的倒数）（X-转置）（R1）

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

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 = 通过 mod N 的解的任何线性组合一样，z R0 和 z R1 本身就是该方程的解。

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

两个优化使这个速度特别快：

  • 无需一次猜出 X 的所有平滑数和列。您可以连续运行回归，一次向 X 添加一列，选择减少 E0 和 E1 最多的列。任何时候都不会选择任何两个具有公因数的平滑数。
  • 您还可以从 zx = by mod N 的大量随机解开始，并删除在 X 的新列选择之间误差最大的解。
于 2017-08-31T13:10:09.663 回答