Doppelpost! Faktorisierungsalgorithmus nach Hart

06.03.2020, 14:47	MaPalui	Auf diesen Beitrag antworten »
Faktorisierungsalgorithmus nach Hart Hallo ihr Lieben ich beiße mir nun schon einige Zeit die Zähne am oben genannten Faktorisierungsverfahren aus. Es hängt dabei an meinem Verständnis und hoffe, jemand kann mir den Kopf zurechtrücken. Die Quelle dazu findet sich hier. Darin lautet der Algorithmus folgendermaßen: [attach]50729[/attach] Ich kenne das Grundprinzip von Lehman's Algorithmus und Fermats Algorithmus kenne ich gut. Mein Verständnisproblem beginnt in Zeile 3. Es wird $\begin{eqnarray} s^2 \pmod n = \lceil\sqrt{N}\rceil^2\pmod n \end{eqnarray}$ gebildet. Dies ist in jedem Fall $\begin{eqnarray} >Ni \end{eqnarray}$ . Schreiben wir $\begin{eqnarray} s^2 = Ni + m \end{eqnarray}$ . Nach Reduktion mod $ $\begin{eqnarray} n \end{eqnarray}$ bleibt also $\begin{eqnarray} m \end{eqnarray}$ übrig. Nun wird geprüft, ob eine Quadraztahl vorliegt. Schreiben wir also $\begin{eqnarray} m = t^2 \end{eqnarray}$ . So, und ab dieser Stelle komme ich nicht weiter. Ich verstehe nicht den Zusammenhang zum letztgenannten Satz. Kann mir jemand dort auf die Sprünge helfen? Viele Grüße Eure Maren
16.06.2020, 11:58	Steffen Bühler	Auf diesen Beitrag antworten »
RE: Faktorisierungsalgorithmus nach Hart Frage wurde hier neu gestellt, dieser Thread wird geschlossen.

Verwandte Themen