Warum funktionieren genetische Algorithmen nicht bei Problemen wie der Faktorisierung von RSA?
https://stackoverflow.com/questions/5456483
-
12-11-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Vor einiger Zeit interessierte ich mich sehr für GAs und habe mich viel darüber informiert.Ich habe C++ GAlib verwendet, um einige Programme zu schreiben, und ich war ziemlich erstaunt über ihre Fähigkeit, ansonsten schwierig zu berechnende Probleme in Sekundenschnelle zu lösen.Sie schienen eine großartige Brute-Forcing-Technik zu sein, die wirklich sehr, sehr intelligent funktioniert und sich anpasst.
Ich habe ein Buch von Michalewitz gelesen, wenn ich mich an den Namen erinnere, und alles schien auf dem Schema-Theorem zu basieren, das vom MIT bewiesen wurde.
Ich habe auch gehört, dass es nicht wirklich zur Lösung von Problemen wie der Faktorisierung privater RSA-Schlüssel verwendet werden kann.
Könnte jemand erklären, warum das so ist?
Lösung
genetischer Algorithmus sind nicht intelligent überhaupt , sie sind sehr gierige Optimiereralgorithmen. Sie arbeiten alle um dieselbe Idee. Sie haben eine Gruppe von Punkten ('eine Bevölkerung von Einzelpersonen), und Sie transformieren diese Gruppe in einen anderen mit stochastischen Bediener mit einer Vorspannung in Richtung der besten Verbesserung ("Mutation + Crossover + Selection"). Wiederholen Sie sich, bis es konvergiert, oder Sie sind es müde, nichts klug da.
Für einen genetischen Algorithmus zur Arbeit sollte eine neue Population von Punkten in der Nähe der vorherigen Population der Punkte auftreten. Die kleine Störung sollte wenig Veränderungen erstellen. Wenn Sie nach einer geringen Störung eines Punktes einen Punkt erhalten, der eine Lösung mit völlig unterschiedlicher Leistung darstellt, ist der Algorithmus nichts Besseres als zufällige Suche, einem normalerweise nicht guter Optimierungsalgorithmus. Wenn in dem RSA-Fall, wenn Ihre Punkte direkt die Zahlen sind, ist es entweder Ja oder Nein, nur indem ein Bit umgedreht ... somit ein genetischer Algorithmus ist nicht besser als eine zufällige Suche, wenn Sie das RSA-Problem ohne viel denken, ohne "Let's" Code-Suchpunkte als Bits der Zahlen "
Andere Tipps
Ich würde sagen, weil die Faktorisierung von Schlüsseln kein Optimierungsproblem ist, sondern ein genaues Problem.Diese Unterscheidung ist nicht sehr genau, also hier Details. Genetische Algorithmen eignen sich hervorragend, Probleme zu lösen, bei denen die Mindesteinheit (lokal / global) sind, aber es gibt keine im Factorise-Problem.Der genetische Algorithmus als DCA oder Simuliertes Glühen benötigt ein Maß für "Wie nahe bin ich zur Lösung", aber Sie können dies nicht für unser Problem sagen.
Für ein Beispiel für die Problemgenetik sind gut, es gibt das Hill-Kletterproblem.
-Gas basieren auf der Fitnessbewertung von Kandidatenlösungen.
Sie haben im Wesentlichen eine Fitness-Funktion, die eine Kandidatenlösung als Input anzieht und Ihnen einen Skalar zurückgibt, wenn Sie sagen, wie gut dieser Kandidat ist.Sie gehen dann weiter und lassen die besten Individuen einer bestimmten Generation, um mit einer höheren Wahrscheinlichkeit zu paaren als den Rest, so dass der Nachkommen (hoffentlich) "fit" insgesamt ist, und so auf .
Es gibt keine Möglichkeit, die Fitness auszuwerten (wie gut ist eine Kandidatenlösung im Vergleich zum Rest) im RSA-Faktorisierungsszenario, deshalb können Sie sie nicht verwenden.
GAs sind kein Brute-Forcing, sie sind lediglich ein Suchalgorithmus.Jeder GA sieht im Wesentlichen so aus:
candidates = seed_value;
while (!good_enough(best_of(candidates))) {
candidates = compute_next_generation(candidates);
}
Wo good_enough Und best_of sind definiert als a Fitnessfunktion.Eine Fitnessfunktion sagt wie gut ein bestimmter Kandidat das Problem löst.Das scheint hier das Kernproblem zu sein:Wie würden Sie eine Fitnessfunktion für die Faktorisierung schreiben?Zum Beispiel 20 = 2*10 oder 4*5.Die Tupel (2,10) und (4,5) sind eindeutig Gewinner, aber was ist mit den anderen?Wie „fit“ ist (1,9) oder (3,4)?
indirekt, Sie können einen genetischen Algorithmus verwenden, um einen genetischen Algorithmus zu verwenden, um eine Ganzzahl n. Dixons Integer-Faktorisierungsmethode zu fördern, die Gleichungen mit Befugnissen der ersten K -Prime, MODULO N verwenden. Diese Produkte von Kräften von kleinen Primaten werden als "glatt" bezeichnet. Wenn wir die ersten k= 4 -Prime verwenden - {2,3,5,7} - 42= 2x3x7 ist glatt und 11 ist nicht (für den Fehlen eines besseren Begriffs ist 11 "rau" ). Das Verfahren von Dixon erfordert ein invertierbares k x k -Matrix, das aus den Exponenten besteht, die diese reibungslosen Zahlen definieren. Weitere Informationen zu Dixons-Methode finden Sie in https://en.wikipedia.org/wiki/dixon%27s_Factorization_method .
weiter dachte der beste Weg, um sich den besten Weg in Richtung glatter Koeffizienten x, y in der Gitter-Axt= von Mod N mit Regression, nicht mit einem genetischen Algorithmus.
zwei Regressionen werden durchgeführt, einer mit Antwortvektor R0, der aus X-Werten aus zufällig gewählten Lösungen von AX= von mod n besteht; und der andere mit dem Antwortvektor R1, der aus y-Werten aus denselben Lösungen besteht. Beide Regressionen verwenden die gleiche erläuternde Matrix X. In X sind Säulen, bestehend aus den Resten der X-Werte modulo glatten Divisoren, und andere Säulen, die aus den Resten der Y-Werte Modulo anderen glatten Divisoren bestehen.
Die beste Wahl der glatten Divisors ist derjenige, der die Fehler von jeder Regression minimiert:
e0= R0 - x (inverse (x-transpicht) (x)) (x-transpicht) (R0)
e1= R1 - X (inverse (x-transpicht) (x)) (x-transpicht) (R1)
was folgt, ist Zeilenoperationen zum Annihilat X., dann ein Ergebnis Z dieser Zeilenoperationen auf die X- und Y-Werte aus den ursprünglichen Lösungen auftragen, von denen X gebildet wurde. generasacodicetagpre.
in ähnlicher Weise Z R1= Z E1
Drei Eigenschaften werden jetzt in Z R0 und Z R1 kombiniert:
- .
- Sie sind Vielfache großer glatter Zahlen, denn z Vernichtungen bleiben modulo reibungslose Nummern.
- sie sind relativ klein, da E0 und E1 klein sind.
- wie jede lineare Kombination von Lösungen zu AX= von mod n, z r0 und z r1 sind selbst Lösungen für diese Gleichung.
Ein relativ kleines Vielfaches einer großen glatten Anzahl könnte nur die glatte Zahl selbst sein. Eine reibungslose Lösung von AX= von MOD n ergibt eine Eingabe in die Methode von Dixon.
Zwei Optimierungen machen das besonders schnell:
- .
- Es ist nicht erforderlich, alle glatten Zahlen und Säulen von X gleichzeitig zu erraten. Sie können Regressionen kontinuierlich ausführen, um eine Spalte zu X zu einem Zeitpunkt hinzufügen, indem Sie Spalten auswählen, die E0 und E1 am meisten reduzieren. Zu keiner Zeit werden zwei reibungslose Zahlen mit einem gemeinsamen Faktor ausgewählt.
- Sie können auch mit vielen zufälligen Lösungen von ZX= von Mod N beginnen und die mit den größten Fehlern zwischen den Selektionen neuer Spalten für X entfernen.
