Fermats Faktorisierungsverfahren, Differenz zweier Quadrate

15.07.2021, 21:55

Malcang

Fermats Faktorisierungsverfahren, Differenz zweier Quadrate

Hallo zusammen,

ich schaue mir gerade Fermats Verfahren zur Faktorisierung an. Dazu hier der Ausschnitt aus der Quelle die ich nutze:
[attach]53336[/attach]

Mir ist auch klar, wie das ganze funktioniert. Aber eine Sache erschließt sich mir nicht:
Warum spuckt der Algorithmus "FALSE", also "prim" aus, wenn $\begin{eqnarray*} x+y = \frac{N+1}{2} \end{eqnarray*}$ vorliegt?
Das ich bei einer Primzahl nur diese Faktorisierung erhalte, ist klar.
Aber auch jede andere Zahl $\begin{eqnarray*} z = ab = 1\cdot ab \end{eqnarray*}$ lässt sich doch mit $\begin{eqnarray*} (\frac{1+ab}{2})^2 - (\frac{1-ab}{2})^2 \end{eqnarray*}$ trivial faktorisieren.
Warum ist im Algorithmus ausgeschlossen, dass eine Nichtprimzahl diese Faktorisierung liefert? verwirrt

Viele Grüße
ichwarneu

18.08.2021, 16:02

Malcang

Auf diesen Beitrag antworten »

Hallo nochmal,

ich scheitere leider immernoch hieran und bin kein Stück weitergekommen.
Kann mir jemand vielleicht einen Ansatz für einen Beweis nennen?
Oder die Vorgehensweise?

Ich frage mich, warum sichergestellt ist, dass der Algorithmus mir immer einen Teiler bringt und keinen "überspringt"?
Ich hatte es versucht mit einem indirekten Beweis.
Aber da weiß ich alleine den Ansatz nicht,

18.08.2021, 16:58

IfindU

Auf diesen Beitrag antworten »

Ich habe es mal aus Spaß mit der Primzahl $\begin{eqnarray*} N =13 \end{eqnarray*}$ versucht.

Ich bekomme im Anfang $\begin{eqnarray*} x = 3, \; t = 7, \; r = -4 \end{eqnarray*}$ . Nach ein paar Iterationen bekomme ich $\begin{eqnarray*} r = 36, \; t = 15 \end{eqnarray*}$ und damit $\begin{eqnarray*} x = 7 \end{eqnarray*}$ und $\begin{eqnarray*} y =6 \end{eqnarray*}$ . Zwar gilt dann offensichtlich $\begin{eqnarray*} (x+y)(x-y) = 13 \cdot 1 = N \end{eqnarray*}$ , aber $\begin{eqnarray*} \frac { N + 1} 2 = 7 \neq x + y \end{eqnarray*}$ .

Irgendwas ist da krumm mit der Aussage. Wäre in dem Fall $\begin{eqnarray*} x + y = 7 \end{eqnarray*}$ , dann würde folgen, dass $\begin{eqnarray*} x-y = \frac {13}7 \end{eqnarray*}$ ist, was es ja nicht sein kann. Ich würde daher vermuten es ist prim, wenn $\begin{eqnarray*} x + y = N \end{eqnarray*}$ ist. Damit ist dann mit $\begin{eqnarray*} x- y =1 \end{eqnarray*}$ eine triviale Zerlegung gefunden. Dann könnte man mit Monotonie versuchen zu argumentieren, dass man vor dieser trivialen Zerlegung, sofern existent, immer eine andere findet.

18.08.2021, 16:59

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
Warum spuckt der Algorithmus "FALSE", also "prim" aus, wenn $\begin{eqnarray*} x+y = \frac{N+1}{2} \end{eqnarray*}$ vorliegt?

Bist du dir sicher, dich hier nicht verschrieben zu haben (x+y statt x)? $\begin{eqnarray*} N \end{eqnarray*}$ prim bedeutet nämlich, es gibt nur die Faktorisierung $\begin{eqnarray*} x-y=1,x+y=N \end{eqnarray*}$ , was aufgelöst

$\begin{eqnarray*} x = \frac{N+1}{2} \end{eqnarray*}$ und $\begin{eqnarray*} y = \frac{N-1}{2} \end{eqnarray*}$

ergibt.

Übrigens: Wenn ich mal den "Effizienzblick" auf den Algorithmus werfe, dann stutze ich bei Zeile 4:

Die Entscheidung "r ist kein ganzzahliges Quadrat" ist m.E. von der Komplexität her ein gewaltiger Brocken, gegen den der Rest hinsichtlich Aufwand nahezu verblasst. Augenzwinkern

18.08.2021, 17:19

Malcang

Auf diesen Beitrag antworten »

Hallo ihr zwei,

ich danke euch vielmals für eure Zeit. Ich bin gerade im Zug unterwegs, aber werde gleich nochmal auf den Algorithmus schauen. Wenn euch das aber aufgefallen ist, werde ich mich da sicherlich verschrieben haben. Das korrigiere ich natürlich gleich.

Edit: Ihr habt natürlich Recht, es muss $\begin{eqnarray*} x+y = N \end{eqnarray*}$ heißen.

@HAL 9000:
Danke für den Hinweis mit Zeile 4.
Fermat hat es ja so gemacht, dass er die letzten beiden Ziffern betrachtete und damit potentielle Nichtkandidaten (sagt man das so?) von vornherein ausschließen konnte.
Heuristisch macht das etwa 80% aller auftretenden Reste aus.

18.08.2021, 17:26

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
Fermat hat es ja so gemacht, dass er die letzten beiden Ziffern betrachtete und damit potentielle Nichtkandidaten (sagt man das so?) von vornherein ausschließen konnte.
Heuristisch macht das etwa 80% aller auftretenden Reste aus.

Ok, auf die heutige Binärarchitektur "übersetzt" kann man das vielleicht so adaptieren:

Man betrachtet (durch AND-Maskierung) die letzten $\begin{eqnarray*} m \end{eqnarray*}$ Binärstellen der Zahl $\begin{eqnarray*} r \end{eqnarray*}$ und entscheidet anhand einer LUT (look-up table) für die quadratischen Reste modulo $\begin{eqnarray*} 2^m \end{eqnarray*}$ ), ob es ggfs. ein Quadrat ist. In diesen Fällen muss man dann doch weiter untersuchen, in den anderen nicht. Wie groß man $\begin{eqnarray*} m \end{eqnarray*}$ wählt wird dann im wesentlichen davon bestimmt, wieviel Platz man der LUT spendieren will bzw. kann. Augenzwinkern

18.08.2021, 17:29

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Dann könnte man mit Monotonie versuchen zu argumentieren, dass man vor dieser trivialen Zerlegung, sofern existent, immer eine andere findet.

So war auch schon meine Überlegung.
Behauptung: Fermats Algorithmus findet zuerst eine nichttriviale Faktorisierung von N, falls es diese gibt. Gibt es keine, wird auf jeden Fall die triviale Faktorisierung ausgegeben.

Sei N prim. Dann gibt es nur die triviale Zerlegung $\begin{eqnarray*} N = N\cdot 1 \end{eqnarray*}$ .
Wendet man nun Fermats Algorithmus an...

Ja, und hier scheitere ich nun leider unglücklich

Ich habe es auch an einigen Beispielen gerechnet aber mit ist formal nicht klar, warum ich nicht in eine Endlosschleife geraten könnte verwirrt

Zitat:

Original von HAL 9000
Ok, auf die heutige Binärarchitektur "übersetzt" kann man das vielleicht so adaptieren:

Man betrachtet (durch AND-Maskierung) die letzten $\begin{eqnarray*} m \end{eqnarray*}$ Binärstellen der Zahl $\begin{eqnarray*} r \end{eqnarray*}$ und entscheidet anhand einer LUT (look-up table) für die quadratischen Reste modulo $\begin{eqnarray*} 2^m \end{eqnarray*}$ ), ob es ggfs. ein Quadrat ist. In diesen Fällen muss man dann doch weiter untersuchen, in den anderen nicht. Wie groß man $\begin{eqnarray*} m \end{eqnarray*}$ wählt wird dann im wesentlichen davon bestimmt, wieviel Platz man der LUT spendieren will bzw. kann. Augenzwinkern

Ich habe noch nie von LUT gehört, aber ich denke ich weiß, was dahintersteckt.
Mit festem $\begin{eqnarray*} m = 2 \end{eqnarray*}$ habe ich es auch implementiert, um Fermats Vorgehen verdeutlichen zu können.

18.08.2021, 17:48

IfindU

Auf diesen Beitrag antworten »

RE: Fermats Faktorisierungsverfahren, Differenz zweier Quadrate
Die ganze Idee ist, dass jedes berechnete Paar (t,r) eine Lösung (x,y) liefern mit $\begin{eqnarray*} (x-y)(x+y) = N \end{eqnarray*}$ . Es ist sogar $\begin{eqnarray*} x \in \mathbb N \end{eqnarray*}$ , aber leider mit $\begin{eqnarray*} y \in \mathbb C \end{eqnarray*}$ i.A.; man nimmt nun das aller erste $\begin{eqnarray*} y \in \mathbb N \end{eqnarray*}$ . Nun wachsen $\begin{eqnarray*} x,y \end{eqnarray*}$ mit jedem Schritt und es gilt immer $\begin{eqnarray*} x \geq y \end{eqnarray*}$ . D.h. die größte Lösung ist der Trivialfall, und jede Lösung davor ist eine mögliche Faktorisierung.

Dass es alles durchläuft, sieht man daran, dass $\begin{eqnarray*} t \end{eqnarray*}$ alle "relevanten" ungeraden Zahlen durchläuft. Du könntest auch unabhängig von $\begin{eqnarray*} N \end{eqnarray*}$ immer mit $\begin{eqnarray*} t = 3 \end{eqnarray*}$ und $\begin{eqnarray*} r=1-N \end{eqnarray*}$ starten. Allerdings wird kein $\begin{eqnarray*} t < 2 \lfloor N \rfloor+1 \end{eqnarray*}$ ein positives $\begin{eqnarray*} r \end{eqnarray*}$ liefern, geschweige quadratisch.

Der größere Sprung in $\begin{eqnarray*} r \end{eqnarray*}$ ist die Anpassung, damit man die Eigenschaft $\begin{eqnarray*} (x-y)(x+y) = N \end{eqnarray*}$ beibehält.

18.08.2021, 20:39

Malcang

Auf diesen Beitrag antworten »

Danke für diese Erklärung. Ich werde das später oder morgen nochmal aufschreiben und würde mich freuen, wenn ihr nochmal reinschauen könntet.
Danke euch und schönen abend smile

18.08.2021, 21:14

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
Aber auch jede andere Zahl $\begin{eqnarray*} z = ab = 1\cdot ab \end{eqnarray*}$ lässt sich doch mit $\begin{eqnarray*} (\frac{1+ab}{2})^2 - (\frac{1-ab}{2})^2 \end{eqnarray*}$ trivial faktorisieren.

Um die Gedanken von IfindU anhand dieses Beispiels konkret zu vertiefen: Jede ungerade zusammengesetzte Zahl $\begin{eqnarray*} z=ab \end{eqnarray*}$ mit dann ebenfalls ungeraden Faktoren $\begin{eqnarray*} 1<a\leq b \end{eqnarray*}$ erfüllt ja eben auch

$\begin{eqnarray*} z = \left(\frac{a+b}{2}\right)^2 - \left(\frac{b-a}{2}\right)^2 \end{eqnarray*}$ ,

und es ist $\begin{eqnarray*} \frac{a+b}{2} < \frac{1+ab}{2} \end{eqnarray*}$ (folgt durch Umstellung aus $\begin{eqnarray*} \frac{(a-1)(b-1)}{2} > 0 \end{eqnarray*}$ ), d.h., jenes $\begin{eqnarray*} x=\frac{a+b}{2} \end{eqnarray*}$ wird im Algorithmus EHER erreicht.

18.08.2021, 21:27

Malcang

Auf diesen Beitrag antworten »

Hallo HAL 9000,

danke für diesen weiteren Hinweis.
Ich muss mir das nochmal auf Papier genau aufschreiben, das werde ich morgen machen.
Meine Befürchtung ist dass ich dann die Frage stelle warum es sichergestellt ist, dass der von dir genannte Faktor $\begin{eqnarray*} x = \frac{a+b}{2} \end{eqnarray*}$ auch erreicht wird.

18.08.2021, 21:37

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
warum es sichergestellt ist, dass der von dir genannte Faktor $\begin{eqnarray*} x = \frac{a+b}{2} \end{eqnarray*}$ auch erreicht wird.

Weil in jedem Schleifenschritt (von $\begin{eqnarray*} x=\left\lfloor \sqrt{N}\right\rfloor \end{eqnarray*}$ beginnend) der Wert $\begin{eqnarray*} x \end{eqnarray*}$ nur um 1 inkrementiert wird:

Denn auch wenn $\begin{eqnarray*} x \end{eqnarray*}$ in der Schleife gar nicht mehr explizit vorkommt, so kann man es sich doch implizit hinzudenken über dieses zu jedem Schleifenzeitpunkt geltende $\begin{eqnarray*} t=2x+1 \end{eqnarray*}$ : Die Inkrementierung von $\begin{eqnarray*} t \end{eqnarray*}$ jeweils um 2 entspricht dieser (impliziten) Inkrementierung von $\begin{eqnarray*} x \end{eqnarray*}$ um 1. Ausführlicher ist Schritt

$\begin{eqnarray*} t\leftarrow t+2 \end{eqnarray*}$

genau genommen die Kurzvariante (weil weniger rechenaufwändig) von

$\begin{eqnarray*} x\leftarrow x+1 \end{eqnarray*}$
$\begin{eqnarray*} t\leftarrow 2x+1 \end{eqnarray*}$

Und wenn $\begin{eqnarray*} x \end{eqnarray*}$ immer nur um 1 inkrementiert wird, kann man den Wert $\begin{eqnarray*} \frac{a+b}{2} \end{eqnarray*}$ auch nicht "verpassen". Bleibt nur die Frage zu klären, warum auf jeden Fall $\begin{eqnarray*} \frac{a+b}{2}\geq \left\lfloor \sqrt{N}\right\rfloor \end{eqnarray*}$ ist, d.h., mindestens so groß wie der Startwert des Verfahrens - das kannst du dir mal noch überlegen.

18.08.2021, 21:41

Malcang

Auf diesen Beitrag antworten »

Ja, die Inkrementation verstehe ich. Es wird sukzessive
$\begin{eqnarray*} x^2 - N = r_0 \end{eqnarray*}$ ,
$\begin{eqnarray*} (x+1)^2 - N = r_1 \end{eqnarray*}$
$\begin{eqnarray*} \dots \end{eqnarray*}$
gebildet, bis ein auftrendes $\begin{eqnarray*} r_j \end{eqnarray*}$ ein Quadrat ist.
Dann liegt die Faktorisierung nach dritter binomischer Formel vor.

Aber bevor ich jetzt weiter aushole, schreibe ich mir das lieber morgen nochmal auf. Sonst frage ich jetzt nur Sachen, die ihr schon beantwortet habt und das wäre mir nicht recht.

Danke dass ihr so spät hier noch reinschaut smile

22.08.2021, 16:11

Malcang

Auf diesen Beitrag antworten »

Hallo zusammen,

bitte entschuldigt meine Verspätung. Es kam leider doch etwas dazwischen.
Ich werde mich nun aber nochmal mit dem Problem befassen und würde mich noch heute hier zurückmelden.
Würde mich freuen wenn ihr nochmal reinschauen könntet, natürlich nur wie ihr Zeit habt.

Nochmals Sorry dass die Antwort jetzt nicht gewünscht einen Tag später kam.

22.08.2021, 23:20

Malcang

Auf diesen Beitrag antworten »

So, nun aber mein Ansatz bisher:

Sei $\begin{eqnarray*} N\in\mathbb N \end{eqnarray*}$ eine feste, ungerade natürliche Zahl. Bilde dann $\begin{eqnarray*} x = \lfloor \sqrt{N}\rfloor \end{eqnarray*}$ .
Für alle $\begin{eqnarray*} i\in\mathbb N_0 \end{eqnarray*}$ bilde $\begin{eqnarray*} (x+i)^2 - N = r_i \end{eqnarray*}$ . Dann bildet jedes Paar $\begin{eqnarray*} (i, \sqrt{r_i}) \end{eqnarray*}$ eine Lösung der Form $\begin{eqnarray*} (x+i+\sqrt{r_i})(x+i-\sqrt{r_i}) = N. \end{eqnarray*}$ .
Die $\begin{eqnarray*} r_i \end{eqnarray*}$ lassen sich gemäß der Vorgabe für $\begin{eqnarray*} t \end{eqnarray*}$ explizit berechnen.
Nach $\begin{eqnarray*} i = \frac{N+1}{2} - \lfloor\sqrt{x}\rfloor \end{eqnarray*}$ Schritten liegt die triviale Faktorisierung vor, denn $\begin{eqnarray*} (x+ \frac{N+1}{2}-\lfloor\sqrt{N}\rfloor)^2 - N = (\frac{N+1}{2})^2 - N = (\frac{N-1}{2})^2 \end{eqnarray*}$ .
Da $\begin{eqnarray*} \frac{N+1}{2} - \lfloor\sqrt{N}\rfloor \in\mathbb N_0 \end{eqnarray*}$ , terminiert der Algorithmus in jedem Fall, spätestens mit der trivialen Faktorisierung.

Es bleibt nun zu zeigen, dass eine mögliche Faktorisierung vorher erwischt wird. Dazu habt ihr mir ja bereits einige Hinweise gegeben, die ich aber noch nicht sauber aufschreiben konnte. Das würde ich aber noch machen.

Ist dieser Ansatz bisher ok?

23.08.2021, 09:45

IfindU

Auf diesen Beitrag antworten »

Für $\begin{eqnarray*} i =0 \end{eqnarray*}$ ist $\begin{eqnarray*} r < 0 \end{eqnarray*}$ und damit $\begin{eqnarray*} \sqrt r \end{eqnarray*}$ nur im komplexen Sinne definiert. Das würde ich separat betrachten bzw. weg argumentieren.

Ansonsten passt es aus meiner Sicht bis auf klein Tippfehler ( $\begin{eqnarray*} \sqrt x \end{eqnarray*}$ statt korrekterweise $\begin{eqnarray*} x \end{eqnarray*}$ ) Freude

23.08.2021, 15:37

Malcang

Auf diesen Beitrag antworten »

Ich danke dir. Die Einwände verstehe ich voll und ganz.
Gut, damit konnte ich nun zeigen dass schlimmstenfalls die triviale Faktorisierung Auftritt.

Falls es eine weitere gibt, wird sie vorher gefunden. Am sauberen Beweis arbeite ich gerade.

23.08.2021, 16:55

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Und wenn $\begin{eqnarray*} x \end{eqnarray*}$ immer nur um 1 inkrementiert wird, kann man den Wert $\begin{eqnarray*} \frac{a+b}{2} \end{eqnarray*}$ auch nicht "verpassen". Bleibt nur die Frage zu klären, warum auf jeden Fall $\begin{eqnarray*} \frac{a+b}{2}\geq \left\lfloor \sqrt{N}\right\rfloor \end{eqnarray*}$ ist, d.h., mindestens so groß wie der Startwert des Verfahrens - das kannst du dir mal noch überlegen.

Guten Tag,
Ich bin auf einer langen Zugfahrt nur mit Smartphone. Daher kann ich aktuell keine sauberen Latex Formeln einfügen.
Die von dir genannte Ungleichung konnte ich zeigen mit dem Ansatz
(1/4)*(a-b)^2 >= 0

Ich habe auch gerade einen Verdacht was du mit "man kann den Wert nicht verpassen" meinst. Aber das muss ich mir erst aufschreiben.
Mir fällt das Thema nicht leicht, aber ich bin dank eurer Hilfe viel weiter und bleibe dran!

23.08.2021, 17:27

Malcang

Auf diesen Beitrag antworten »

Ah, ich glaube ich habe es.
Sei n=ab.
Nach genau
(1+ab)/2 - x
Schritten erhalte ich die triviale Faktorisierung.
Gibt es eine nicht triviale Faktorisierung, so erhalte ich diese nach
(a+b)/2 - x
Schritten. Mit der von HAL 9000 angesprochenen Ungleichung kann ich nun schliessen, dass diese Faktorisierung EHER Auftritt, da (a+b)/2 - x eine natürliche Zahl ist und insbesondere kleiner als (ab+1)/2 -x.

Ist das die Richtung in die ihr mich stupsen wolltet?

P.S. bitte entschuldigt die vielen Antworten hintereinander. Ich habe auch überlegt, immer meine letzte Antwort zu editieren. Aber das bekommt man als Helfer im Nachhinein nicht mit, oder?

24.08.2021, 09:30

IfindU

Auf diesen Beitrag antworten »

Von meiner Seite passt es Freude

24.08.2021, 14:04

Malcang

Auf diesen Beitrag antworten »

Guten Tag zusammen,

ich habe das mal mit einem Skript überprüft und es passt genau.

Ihr habt mir wirklich sehr geholfen und ich habe wirklich was gelernt.
Ich danke euch vielmals! smile

10.10.2021, 22:40

Malcang

Auf diesen Beitrag antworten »

Da bin ich nochmal. Ich hoffe es ist ok, wenn ich diesen Thread nochmal nach oben hole.

Das Verfahren ist mir Dank eurer Hilfe nun wirklich klar geworden. Eine Frage habe ich nun allerdings noch.
Es ist ja so, dass Fermats Algorithmus den Teiler findet, der am nächsten zur Wurzel der Eingabe liegt. Nun würde ich das gerne formalisieren, stoße dabei aber auf eine Unklarheit.

Seien $\begin{eqnarray*} a,b,c \in\mathbb N \end{eqnarray*}$ und alle ungerade. Weiterhin gelte $\begin{eqnarray*} a\leq b\leq c \end{eqnarray*}$ . Bilde $\begin{eqnarray*} n = a\cdot b\cdot c \end{eqnarray*}$ und $\begin{eqnarray*} x = \lfloor \sqrt{n}\rfloor \end{eqnarray*}$
Nun haben wir herausgefunden dass Fermats Verfahren nach $\begin{eqnarray*} i = \frac{ab+c}{2}-x \end{eqnarray*}$ Schritten die Faktoren $\begin{eqnarray*} ab \end{eqnarray*}$ und $\begin{eqnarray*} c \end{eqnarray*}$ findet.
Einfache Nachrechnung ergibt $\begin{eqnarray*} ab+c \leq ac+b \leq bc+a \end{eqnarray*}$ , also werden diese beiden Faktoren als erstes aufgefunden.

Nun meine Frage:
Ich weiß doch nicht, ob nun der Faktor $\begin{eqnarray*} ab \end{eqnarray*}$ oder $\begin{eqnarray*} c \end{eqnarray*}$ am nächsten zur Wurzel der Eingabe liegt, oder?
Ich weiß ja nur, dass diese Faktoren zuerst aufgefunden werden.
Sagen wir, ich finde zuerst die Faktoren $\begin{eqnarray*} ab \end{eqnarray*}$ und $\begin{eqnarray*} c \end{eqnarray*}$ .
Wenn ich nun weitergehe, finde ich $\begin{eqnarray*} ac \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ .
Jetzt könnte es doch sein, dass $\begin{eqnarray*} c \end{eqnarray*}$ (erster Fund) am nächsten zur Wurzel liegt, trotzdem aber einer der Faktoren des zweiten Fundes näher zur Wurzel liegt als $\begin{eqnarray*} ab \end{eqnarray*}$ (erster Fund).

Oder übersehe ich was? verwirrt

13.10.2021, 13:09

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
Wenn ich nun weitergehe, finde ich $\begin{eqnarray*} ac \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ .

Wieso gehst du überhaupt weiter? Mit den Finden der beiden Faktoren $\begin{eqnarray*} ab \end{eqnarray*}$ und $\begin{eqnarray*} c \end{eqnarray*}$ (von denen wir zu dem Zeitpunkt noch nicht wissen, ob sie prim oder doch noch weiter zerlegbar sind) íst doch die Fermat-Faktorisierung von $\begin{eqnarray*} n \end{eqnarray*}$ beendet!

Falls du damit die komplette Primfaktorzerlegung deiner Zahl ermitteln willst, dann musst du mit dem erhaltenen Ergebnis verzweigen in die beiden neuen Faktorisierungen von $\begin{eqnarray*} ab \end{eqnarray*}$ sowie $\begin{eqnarray*} c \end{eqnarray*}$ - so würde ich zumindest "Primfaktorzerlegung per Fermat-Faktorisierung" verstehen! verwirrt

13.10.2021, 14:33

Malcang

Auf diesen Beitrag antworten »

Hallo HAL, danke für deine Zeit.
Sorry, die Frage ist wirklich ungünstig formuliert.
Ich komme nach $\begin{eqnarray*} \frac{ab+c}{2} \end{eqnarray*}$ Schritten zur Faktorisierung $\begin{eqnarray*} n=ab\cdot c \end{eqnarray*}$ .
Aber was weiss ich nun?
Weiss ich, dass einer der Faktoren $\begin{eqnarray*} ab \end{eqnarray*}$ oder $\begin{eqnarray*} c \end{eqnarray*}$ näher zur Wurzel der Eingabe liegt als Alle anderen möglichen Faktoren?

13.10.2021, 14:58

HAL 9000

Auf diesen Beitrag antworten »

Hmm, ich dachte ich hätte mich klar geäußert, nochmal von vorn: Du hast $\begin{eqnarray*} n = a\cdot b\cdot c \end{eqnarray*}$ mit (wie ich annehme) Primzahlen $\begin{eqnarray*} a,b,c \end{eqnarray*}$ mit $\begin{eqnarray*} a\leq b\leq c \end{eqnarray*}$ .

Die Fermat-Faktorisierung stoppt nun bei $\begin{eqnarray*} n = f_1\cdot f_2 \end{eqnarray*}$ mit $\begin{eqnarray*} f_1<f_2 \end{eqnarray*}$ , aber wir wissen zu diesem Zeitpunkt NICHT, ob wir Situation $\begin{eqnarray*} f_1=ab,f_2=c \end{eqnarray*}$ oder aber $\begin{eqnarray*} f_1=c,f_2=ab \end{eqnarray*}$ vorliegen haben. Das offenbart erst eine weitere Analyse der beiden Faktoren $\begin{eqnarray*} f_1,f_2 \end{eqnarray*}$ : Ist $\begin{eqnarray*} f_1 \end{eqnarray*}$ prim, dann war es letztere Situation, sonst hingegen erstere.

Zitat:

Original von ichwarneu
Weiss ich, dass einer der Faktoren $\begin{eqnarray*} ab \end{eqnarray*}$ oder $\begin{eqnarray*} c \end{eqnarray*}$ näher zur Wurzel der Eingabe liegt als Alle anderen möglichen Faktoren?

Na das auf jeden Fall: Es gilt stets $\begin{eqnarray*} a\leq b\leq c \end{eqnarray*}$ und $\begin{eqnarray*} ab\leq ac\leq bc \end{eqnarray*}$ , und was die Verzahnung der beiden Ungleichungsketten betrifft, so geht allenfalls

$\begin{eqnarray*} a\leq b\leq c<\sqrt{n}<ab\leq ac\leq bc \end{eqnarray*}$

oder

$\begin{eqnarray*} a\leq b < ab < \sqrt{n} < c < ac\leq bc \end{eqnarray*}$

denn es gilt ja $\begin{eqnarray*} a\geq 2 \end{eqnarray*}$ für alle Primzahlen $\begin{eqnarray*} a \end{eqnarray*}$ . Mehr Fälle gibt es nicht.

13.10.2021, 15:28

Malcang

Auf diesen Beitrag antworten »

Ich glaube die letzten beiden Ungleichungen sind das, was ich brauchte.
In Ruhe werde ich das nochmal aufschreiben und mich in jedem Fal zurückmelden. Vielen Dank für die Hilfe! Wink

13.10.2021, 17:10

Malcang

Auf diesen Beitrag antworten »

Ok, da bin ich nochmal.
Also deine Aussage nach meinem Zitat war genau das, was ich wissen wollte. Vielen Dank dafür an dieser Stelle.

Nun habe ich mich allerdings gefragt, ob ich das nicht doch etwas zu kompliziert aufgezogen habe.
Hätte ich mit $\begin{eqnarray*} n = a\cdot b \end{eqnarray*}$ gearbeitet, wobei a und b natürliche Zahlen sind (nicht notwendigerweise prim) und $\begin{eqnarray*} a\leq b \end{eqnarray*}$ gelte, dann hätte ich eine Faktorisierung nach $\begin{eqnarray*} \frac{a+b}{2} \end{eqnarray*}$ Schritten erhalten.
Aber nun weiß ich ja an dieser Stelle noch nicht, ob $\begin{eqnarray*} a \end{eqnarray*}$ oder $\begin{eqnarray*} b \end{eqnarray*}$ näher an der Wurzel liegt.

Ich versuche gerade ein Argument zu finden, warum dieses Verfahren als ersten diejenige Faktorisierung findet, bei der einer der beiden Teiler derjenige ist, der am nächsten zur Wurzel liegt.
Wahrscheinlich ist es einfacher, über Monotonie zur argumentieren, denn ich bewege mich ja sukzessive vom Startwert $\begin{eqnarray*} \lfloor \sqrt{n}\rfloor \end{eqnarray*}$ weg. Jede andere Faktorisierung kann also nur Faktoren haben, die weiter weg liegen.
Sorry wenn ich mich etwas umständlich ausdrücke.

Edit: Vielleicht formuliere ich meine "Bedenken" mal so:
Fermats Verfahren findet nach $\begin{eqnarray*} \frac{a+b}{2} \end{eqnarray*}$ Schritten eine Faktorisierung. Aber damit ist mir der Abstand von $\begin{eqnarray*} a \end{eqnarray*}$ beziehungsweise $\begin{eqnarray*} b \end{eqnarray*}$ zur Wurzel der Eingabe noch nicht bekannt.

Neue Frage »

Antworten »

Fermats Faktorisierungsverfahren, Differenz zweier Quadrate

Verwandte Themen