少し前に私はGAにかなり興味があり、GAについてかなり勉強しました。私はC++GAlibを使用していくつかのプログラムを作成しましたが、計算が難しい問題を数秒で解決できることに非常に驚いていました。彼らは本当に本当にスマートに機能し、適応する素晴らしいブルートフォーシングテクニックのように見えました。
名前を正しく覚えていて、それがすべてMITによって証明されたスキーマ定理に基づいているように思えた場合、私はMichalewitzの本を読んでいました。
また、RSA秘密鍵の因数分解などの問題に実際に使用することはできないと聞きました。
なぜこれが当てはまるのか誰かが説明できますか？
遺伝的アルゴリズムはまったく賢くはなく、非常に貪欲なオプティマイザーアルゴリズムです。それらはすべて同じアイデアを回避します。ポイントのグループ（「個人の母集団」）があり、そのグループを確率的演算子を使用して別のグループに変換し、最良の改善の方向にバイアスをかけます（「突然変異+クロスオーバー+選択」）。それが収束するか、あなたがそれに飽きるまで繰り返します、そこには何も賢いものはありません。
遺伝的アルゴリズムが機能するには、新しいポイントの母集団が以前のポイントの母集団に近いパフォーマンスを発揮する必要があります。少しの摂動はほとんど変化を生み出さないはずです。ポイントの小さな摂動の後で、完全に異なるパフォーマンスのソリューションを表すポイントを取得した場合、アルゴリズムはランダム検索に勝るものはなく、通常は適切な最適化アルゴリズムではありません。RSAの場合、ポイントが直接数字である場合は、少し反転するだけで、YESまたはNOのいずれかになります...したがって、遺伝的アルゴリズムを使用することは、RSAの問題をあまり考えずに表現する場合、ランダム検索に勝るものはありません。数字のビットとして検索ポイントをコード化する」
キーの因数分解は最適化問題ではなく、正確な問題だからです。この区別はあまり正確ではないので、ここに詳細を示します。遺伝的アルゴリズムは、が最小（ローカル/グローバル）である問題を解決するのに最適ですが、因数分解の問題には何もありません。DCAまたはシミュレーテッドアニーリングとしての遺伝的アルゴリズムには、「ソリューションにどれだけ近いか」の測定が必要ですが、私たちの問題についてはこれを言うことはできません。
問題の遺伝学が良い例として、山登り法の問題があります。
GAは、候補ソリューションの適合性評価に基づいています。
基本的に、候補解を入力として受け取り、その候補がどれだけ優れているかを示すスカラーを返す適応度関数があります。次に、続けて、特定の世代の最高の個体が他の世代よりも高い確率で交尾できるようにします。これにより、子孫は（願わくば）全体としてより「適合」します。
RSA因数分解シナリオでは、適合性（候補解が他の解と比較してどれだけ優れているか）を評価する方法がないため、それらを使用できません。
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）はどの程度「適合」しますか？
間接的に、遺伝的アルゴリズムを使用して整数Nを因数分解できます。Dixonの素因数分解法は、Nを法とする最初のk個の素数の累乗を含む方程式を使用します。これらの小さい素数の累乗の積は「スムーズ」と呼ばれます。最初のk=4素数を使用している場合-{2,3,5,7}-42=2x3x7は滑らかで、11はそうではありません（より適切な用語がないため、11は「ラフ」です）。ディクソンの方法では、これらの滑らかな数を定義する指数で構成される可逆kxk行列が必要です。ディクソンの方法の詳細については、https：//en.wikipedia.org/wiki/Dixon%27s_factorization_methodを参照してください。
さて、元の質問に戻りましょう。ディクソンの方法の方程式を見つけるための遺伝的アルゴリズムがあります。
[v、w]と[x、y]のように2つのペアを組み合わせるたびに、vとxの滑らかな部分が共有する要素と、の滑らかな部分の要素を除いて、4つの数値の滑らかな部分が消去されます。 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]とy / hを組み合わせるために、v / g、w / h、x / g、y/hの滑らかな部分が犠牲になります。 [x、y]。したがって、v / g、w / h、x / g、およびy/hの滑らかな部分が最も小さい親を選択します。このようにして、ある世代から次の世代へと、ソリューションの大まかな部分をrx = symodNにドライブダウンします。
さらに考えてみると、格子ax = by mod Nの滑らかな係数x、yに向かう最善の方法は、遺伝的アルゴリズムではなく回帰を使用することです。
2つの回帰が実行されます。1つは、ランダムに選択されたax = bymodNの解からのx値で構成される応答ベクトルR0を使用します。もう1つは、同じ解からのy値で構成される応答ベクトルR1を使用します。両方の回帰は同じ説明行列Xを使用します。Xには、滑らかな除数を法とするx値の剰余からなる列と、他の滑らかな除数を法とするy値の剰余からなる他の列があります。
滑らかな除数の最良の選択は、各回帰からのエラーを最小化するものです。
E0 = R0-X（（X-transpose）（X）の逆）（X-transpose）（R0）
E1 = R1-X（（X-transpose）（X）の逆）（X-transpose）（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
3つのプロパティがzR0とzR1で結合されました。
大きな滑らかな数の比較的小さな倍数は、滑らかな数そのものである可能性があります。ax = by mod Nの滑らかな解を得ると、Dixonの方法への入力が得られます。
2つの最適化により、これが特に高速になります。