Faktorisierungsalgorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:47 Mi 19.03.2014 | | Autor: | Ellie123 |
Hallo zusammen,
ich habe im Zusammenhang mit Faktorisierungsalgorithmen folgendes gelesen:
Angenommen es soll eine Zahl n faktorisiert werden, dann wäre das Ziel ein Zahlenpaar a, b zu finden, so dass folgende Gleichung erfüllt ist:
(a+b)(a-b)= n*k mit k [mm] \in \IZ
[/mm]
Und wenn jetzt weder(a+b) noch (a-b) ein Vielfaches von n ist, dann hätte man einen Faktor von n gefunden.
Ich sehe aber nicht ganz warum das so sein soll bzw. welches dann der Faktor von n wäre?! Kann mir da jemand einen Tipp zu geben?
Viele Grüße
Ellie
|
|
| |
|
Hi,
> Angenommen es soll eine Zahl n faktorisiert werden, dann
> wäre das Ziel ein Zahlenpaar a, b zu finden, so dass
> folgende Gleichung erfüllt ist:
> (a+b)(a-b)= n*k mit k [mm]\in \IZ[/mm]
> Und wenn jetzt weder(a+b)
> noch (a-b) ein Vielfaches von n ist, dann hätte man einen
> Faktor von n gefunden.
Nicht wirklich. Man braucht noch eine Zutat: Glück. Aber die Chancen stehen eben gut einen Faktor zu finden.
> Ich sehe aber nicht ganz warum das so sein soll bzw.
> welches dann der Faktor von n wäre?! Kann mir da jemand
> einen Tipp zu geben?
Kurzinfo:
Mal angenommen wir habe eine zu faktorisierende Zahl [mm]n[/mm] und finden ein [mm]b[/mm] mit [mm]n+b^2=a^2[/mm], so kennen wir [mm]n=(a-b)(a+b)[/mm] eine Faktorisierung.
Nun kann man dumm und dämlich raten um ein solches $b$ zu finden. Die Aussage ist nun, dass die Chancen höher stehen , wenn wir ein $b$ suchen, sodass [mm] $kn+b^2=a^2$ [/mm] eine Quadratzahl ist.
Nun muss es nicht zwangsläufig ein Faktor sein. Aber man kann effektiv einen gemeinsamen Faktor von $n$ und $a+b$ bzw. $n$ und $a-b$ berechnen.
|
|
|
|
