Fermats Faktorisierungsmethode: Quelle unverständlich

Neue Frage »

Malcang Auf diesen Beitrag antworten »
Fermats Faktorisierungsmethode: Quelle unverständlich
Hallo ihr lieben,

ich habe im Buch "History of the theory of numbers" von L.E. Dickson folgenden Abschnitt über Fermats Faktorisierungsverfahren gefunden (nicht Erschrecken von der Menge an Text, es geht nicht um das Verfahren selbst):

[attach]53757[/attach]

Im Wiki-Artikel, der übrigens auch diese Quelle referenziert, steht:
Zitat:
Pierre de Fermat beschrieb diese heute nach ihm benannte Faktorisierungsmethode 1643 in einem Brief, der vermutlich an Mersenne oder Frénicle de Bessy adressiert war. In diesem Brief demonstrierte er das Verfahren, indem er die Primfaktorzerlegung von 2.027.651.281 berechnete.


Nun steht aber ja im Buch
Zitat:
Fermat's factorization of the number 100895508169 proposed to him by Mersenne in 1643.

und in den Fußnoten
Zitat:
At the time of his letter to Mersenne [...] he had no such method.


Vielleicht verstehe ich es falsch, aber mir scheint, dieser abgedruckte Brief ging nicht an Mersenne und es steht dort auch nicht, dass es 1643 war. Vielmehr verstehe ich es so, dass Fermat diese Methode in 1643 eben nicht hatte.

Was sagt ihr dazu?
HAL 9000 Auf diesen Beitrag antworten »

Von den historischen Vorgängen da habe ich keine Ahnung, aber fakt ist, dass diese Fermat-Methode gut geeignet ist bei Zahlen , die einen Teiler (muss nicht mal ein Primteiler sein) knapp unterhalb haben. Das ist bei mit auch der Fall.

Bei kann davon jedoch keine Rede sein: Der erste gefundene Teiler, wenn man sich von nach unten tastet ist - da scheint es weit effizienter zu sein, wenn von unten nach oben nach Primteilern sucht (also Standardmethode), zumal man auf diese Weise eh schon auf die 67 trifft.
Malcang Auf diesen Beitrag antworten »

Das ist korrekt, HAL.
Bei Zahlen der Form für prime braucht diese Methode am längsten, nämlich genau Iterationen.
Im Beispiel von Fermat macht dass 11 Iterationen. Die Probedivision wäre nach 11 Schritten ja gerade mal bei Überprüfung, ob 37 ein Teiler ist, angekommen.
Dein zweitgenanntes Beispiel braucht hier alleine Iterationen, und das nur bis zu der von dir genannten Faktorisierung. Die Probedivision hat dann schon alle Teiler gefunden.
Huggy Auf diesen Beitrag antworten »
RE: Fermats Faktorisierungsmethode: Quelle unverständlich
Zitat:
Original von ichwarneu
Nun steht aber ja im Buch
Zitat:
Fermat's factorization of the number 100895508169 proposed to him by Mersenne in 1643.

und in den Fußnoten
Zitat:
At the time of his letter to Mersenne [...] he had no such method.


Vielleicht verstehe ich es falsch, aber mir scheint, dieser abgedruckte Brief ging nicht an Mersenne und es steht dort auch nicht, dass es 1643 war. Vielmehr verstehe ich es so, dass Fermat diese Methode in 1643 eben nicht hatte.

In der Fußnote werden zwei Briefe von Fermat erwähnt. In dem von 1643 erläutert er seine Methode. Zur Zeit seines Briefes von 1638 soll er seine Methode noch nicht gehabt haben.
willyengland Auf diesen Beitrag antworten »

Die Fußnote verstehe ich so, dass Fermat die Methode 1638 noch nicht hatte, wohl aber 1643.
Malcang Auf diesen Beitrag antworten »

Ah, ist das vielleicht so zu verstehen, dass beide Briefe (1638 und 1643) an Mersenne gingen?
 
 
willyengland Auf diesen Beitrag antworten »

So verstehe ich das, ja.
Malcang Auf diesen Beitrag antworten »

Ok das könnte es sein.

Danke für eure Hilfe!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »