Fermat Faktorisierung < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
hab ein paar Fragen zu Faktorisierungsverfahren.
Bei der Fermat-Faktorisierung
wird ja nach Zahlen x und y gesucht, so dass N+x²=y² gilt (N=p*q mit p und q prim).
wenn ich dann aber entsprechende x und y gefunden habe muss ich noch den
ggT(x+-y, N) anwenden. Ich sehe allerdings nicht wieso und auch nicht wieso mir da nur in ca 50% der Fälle eine Faktorisierung gelingt und sonst 1 und N als ggT rauskommt.
Meine zweite Frage hat denk ich auch etwas damit zu tun. Es geht wieder um die Faktorisierung von N.
N=p*q mit p und q prim. Wenn ich ein Element x² [mm] \equiv [/mm] 0 mod N erhalte, was kann ich dann daraus ableiten?
Ich steh grad auf dem Schlauch xD
Danke an Alle :)
|
|
| |
|
Hallo Norbert,
> Hallo,
> hab ein paar Fragen zu Faktorisierungsverfahren.
> Bei der Fermat-Faktorisierung
> wird ja nach Zahlen x und y gesucht, so dass N+x²=y² gilt
> (N=p*q mit p und q prim).#
Gemeinhin betrachtet man x²-N=y².
Da sind die Zahlen kleiner.
> wenn ich dann aber entsprechende x und y gefunden habe
> muss ich noch den
> ggT(x+-y, N) anwenden. Ich sehe allerdings nicht wieso
da [mm] $N+x^2=y^2 \Leftrightarrow N=y^2-x^2$
[/mm]
> und auch nicht wieso mir da nur in ca 50% der Fälle eine
wie kommst du auf diesen prozentualen Anteil?
Welche Fälle werden betrachtet?
> Faktorisierung gelingt und sonst 1 und N als ggT
> rauskommt.
>
> Meine zweite Frage hat denk ich auch etwas damit zu tun. Es
> geht wieder um die Faktorisierung von N.
> N=p*q mit p und q prim. Wenn ich ein Element x² [mm]\equiv[/mm] 0
> mod N erhalte, was kann ich dann daraus ableiten?
Dass [mm] $x\equiv [/mm] 0 [mm] \mod [/mm] N$.
Elementarer Beweis, nutze: [mm] $p|N^2 \Rightarrow [/mm] p|N$
> Ich steh grad auf dem Schlauch xD
>
> Danke an Alle :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:42 Sa 01.06.2013 | | Autor: | felixf |
Moin,
> > hab ein paar Fragen zu Faktorisierungsverfahren.
> > Bei der Fermat-Faktorisierung
> > wird ja nach Zahlen x und y gesucht, so dass N+x²=y² gilt
> > (N=p*q mit p und q prim).#
> Gemeinhin betrachtet man x²-N=y².
> Da sind die Zahlen kleiner.
> > wenn ich dann aber entsprechende x und y gefunden habe
> > muss ich noch den
> > ggT(x+-y, N) anwenden. Ich sehe allerdings nicht wieso
> da [mm]N+x^2=y^2 \Leftrightarrow N=y^2-x^2[/mm]
> > und auch nicht
>
> wieso mir da nur in ca 50% der Fälle eine
> wie kommst du auf diesen prozentualen Anteil?
> Welche Fälle werden betrachtet?
Wenn $N$ keine Primzahlpotenz ist (und insb. nicht prim), und wenn $x$ und $y$ zufaellig (gleichverteilt in dem Intervall $[0, N) [mm] \cap \IZ$) [/mm] gewaehlt sind mit [mm] $x^2 \equiv y^2 \pmod{N}$, [/mm] dann ist $ggT(x - y, N)$ mit Wahrscheinlichkeit von mindestens 50% ein echter Teiler von $N$.
(Wenn $N$ das Produkt zwier verschiedener Primzahlen ist, dann ist die Wahrscheinlichkeit genau 50%.)
LG Felix
|
|
|
|
