Forums Neueste Beiträge
 

Faktorisierungsmethode von Fermat - simpel und schnell(?)

09/10/2013 - 21:38 von J | Report spam
Es sei n eine zusammengesetzte Zahl: p · q

Die Faktorisierungsmethode von Fermat làsst sich nach dem Finden einiger
Anfangswerte mit Hilfe der Quadratwurzel aus n, sowie der Quadratwurzel
aus der Differenz zwischen dem nàchsten perfekten Quadrat größer als n
und n selbst finden.

Folgendes Pseudoprogramm wird für die Suche verwendet:

b = sqrt(n)
b = b + 1
bsquare = b^2
bstep = 2·b+1
delta = bsquare - n
a = sqrt(delta)
asquare = a^2
astep = 2·a+1
search = asquare + n

while search != bsquare
if search < bsquare
search = search + astep
astep = astep + 2
else
bsquare = bsquare + bstep
bstep = bstep + 2
end-while

a = (astep - 1) / 2
b = (bstep - 1) / 2
p = b - a
q = b + a

Dieses Programm findet in jedem Fall die Faktoren p und q, die
miteinander multipliziert n ergeben. Sollte n eine Primzahl sein, wàre
einer der Faktoren 1. Sollte n mehr als zwei Primfaktoren haben, wàren p
oder q selbst weiter zerlegbar.

Beim Beobachten der Ablàufe bei einiger Suchen mit zusammengesetzten
Zahlen fàllt auf, dass die Anzahl der wiederholten Additionen zur linken
Seite (search) im Verhàltnis zu den Additionen zur rechten Seite
(bsquare) in offenbar systematischer Weise abnimmt.

Ein Beispiel der abnehmenden Anzahl von Additionen auf der linken Seite
bei der Faktorisierung der Zahl 152587055059730237 findet sich hier:

http://pastebin.com/v3f70hhh

Die Werte der ersten Spalte geben die Schrittzahl des Algorithmus an,
die Werte der zweiten Spalte die Anzahl der notwendigen Additionen zu
"search".

Das Zahlenmaterial làsst sich z.B. mit gnuplot als logarithmische
2D-Grafik darstellen. Eine mit obigen Zahlen erstellte SVG-Datei findet
sich hier:
http://pastebin.com/0CHXimeP

Die Grafik zeigt einen offenabr logarithmischen
(reziprok-exponentiellen?) Zusammenhang zwischen der Schrittzahl
(horizontal) und der Anzahl der notwendigen Additionen auf der linken
Seite (vertikal).

Die Suche nach den Faktoren von 152587055059730237 endet mit dem
Ergebnis:
Schrittzahl 543047659
Faktoren p3423357 q“3691841 (a85134242 bT8557599)

Làsst sich aus der Tatsache der logarithmischen Abnahme der Anzahl der
notwendigen Additionen im Verhàltnis links zu rechts eine Beschleunigung
des Algorithmus bewirken?

Kann man die notwendigen Schritte bis zum Auffinden der Lösung irgendwie
interpolieren und sich so die langwierige Suche über mehrere hundert
Millionen (Zwischen-)Schritte ersparen?

Nach meiner Meinung sollte das möglich sein, jedoch fehlt mir noch ein
konkreter Ansatz für die Berechnung eines "Warp" für die Werte bsquare
und search bzw. asquare. Dieser "Warp" sollte zum Beispiel die ersten
540 Millionen Schritte einfach überspringen und die Suche erst sehr nahe
bei der tatsàchlichen Lösung (nach 543047659 Schritten) beginnen lassen.

Wer hilft weiter oder hat eine Idee hierzu?

Jürgen
 

Lesen sie die antworten

#1 Sam Sung
09/10/2013 - 22:16 | Warnen spam
Jürgen Buchmüller schrieb:

...
Dieses Programm findet in jedem Fall die Faktoren p und q, die
miteinander multipliziert n ergeben. Sollte n eine Primzahl sein, wàre
einer der Faktoren 1. Sollte n mehr als zwei Primfaktoren haben, wàren p
oder q selbst weiter zerlegbar.

Beim Beobachten der Ablàufe bei einiger Suchen mit zusammengesetzten
Zahlen fàllt auf, dass die Anzahl der wiederholten Additionen zur linken
Seite (search) im Verhàltnis zu den Additionen zur rechten Seite
(bsquare) in offenbar systematischer Weise abnimmt.

Ein Beispiel der abnehmenden Anzahl von Additionen auf der linken Seite
bei der Faktorisierung der Zahl 152587055059730237 findet sich hier:

http://pastebin.com/v3f70hhh

Die Werte der ersten Spalte geben die Schrittzahl des Algorithmus an,
die Werte der zweiten Spalte die Anzahl der notwendigen Additionen zu
"search".

Das Zahlenmaterial làsst sich z.B. mit gnuplot als logarithmische
2D-Grafik darstellen. Eine mit obigen Zahlen erstellte SVG-Datei findet
sich hier:
http://pastebin.com/0CHXimeP

Die Grafik zeigt einen offenabr logarithmischen
(reziprok-exponentiellen?) Zusammenhang zwischen der Schrittzahl
(horizontal) und der Anzahl der notwendigen Additionen auf der linken
Seite (vertikal).

Die Suche nach den Faktoren von 152587055059730237 endet mit dem
Ergebnis:
Schrittzahl 543047659
Faktoren p3423357 q“3691841 (a85134242 bT8557599)

Làsst sich aus der Tatsache der logarithmischen Abnahme der Anzahl der
notwendigen Additionen im Verhàltnis links zu rechts eine Beschleunigung
des Algorithmus bewirken?

Kann man die notwendigen Schritte bis zum Auffinden der Lösung irgendwie
interpolieren und sich so die langwierige Suche über mehrere hundert
Millionen (Zwischen-)Schritte ersparen?

Nach meiner Meinung sollte das möglich sein, jedoch fehlt mir noch ein
konkreter Ansatz für die Berechnung eines "Warp" für die Werte bsquare
und search bzw. asquare. Dieser "Warp" sollte zum Beispiel die ersten
540 Millionen Schritte einfach überspringen und die Suche erst sehr nahe
bei der tatsàchlichen Lösung (nach 543047659 Schritten) beginnen lassen.

Wer hilft weiter oder hat eine Idee hierzu?



Ohne viel zu überlegen frage ich mich, ob deine Tabelle soweit statistisch
signifikant für alle (mindestens "grösseren") Zahlen ist, dass sich darin
der nàchste "educated guess" ablesen in der Grössenordnung ablesen làsst;
alternativ könnte man einfach checken, wann die Schrittzahl zu gross wird,
und dann einen Schritt überspringen.

Ähnliche fragen