Faktorisierungsmethode von Fermat

12.10.2019, 22:18

MaPalui

Faktorisierungsmethode von Fermat

Hallo ihr alle smile

ich beschäftige mich mit der oben genannten Methode. Diese verstehe ich auch und bin nun dabei, es zu implementieren. In meiner Quelle finde ich nun folgendes:

Zitat:

Wagstaff - The Joy of Factoring
The integer square root algorithm uses several divisions and would dominate the time for the loop. Fermat, working by hand with decimal numbers, solved this problem by recognizing possible squares by their low-order digits. Every square has last decimal digit 0, 1, 4, 5, 6, or 9. In the example in the table above, r = -43 and 2 cannot be squares because their last digits 1 are not in the list. Only 22 2-digit numbers may occur as the last two decimal digits of a square. A binary computer can test whether r might be a square with the logical operation (r&63) to find (r mod 64), followed by looking up the remainder in a table of the twelve possible squares modulo 64. If r passes this test, then look up (r mod $\begin{eqnarray*} p^e \end{eqnarray*}$ ) in a table of possible squares modulo $\begin{eqnarray*} p^e \end{eqnarray*}$ for a few small odd prime powers $\begin{eqnarray*} p^e \end{eqnarray*}$ .

Es wird geprüft, ob r überhaupt Quadratzahl sein kann, indem es vom PC als r mod 64 betrachtet wird. Ist dieser Rest nicht im Array der möglichen, gehe weiter.
Ok.
Den nun unterstrichenen Teil verstehe ich allerdings nicht.
Sollte also nun eine Tabelle angelegt werden mit den Einträgen $\begin{eqnarray*} p^e \end{eqnarray*}$ für beispielsweise $\begin{eqnarray*} p\in\mathbb P ^{\leq 1000}, e\in\mathbb N^{\leq 10} \end{eqnarray*}$ und für jeden dieser Einträge berechne ich dann $\begin{eqnarray*} r \mod p^e \end{eqnarray*}$ ?

Ich persönlich hätte an folgenden Ablauf gedacht:
(1) Ist (r mod 10) mögliches Quadrat?
Wenn nein, nächste Zahl.
Wenn ja: (2) Ist (r mod 100) mögliches Quadrat?
Wenn nein, nächste Zahl und gehe zu (1)
Wenn ja: (3) Ist (r mod 1000) mögliches Quadrat?
...

Es will mir nicht recht einleuchten. Könnt ihr mir wohl auf die Sprünge helfen? smile

Neue Frage »

Antworten »

Faktorisierungsmethode von Fermat

Verwandte Themen