Page 3
1. Einführung in Kettenbrüche
1-1-Darstellung eines Kettenbruches
Die häugste Darstellung einer reellen Zahl ist die Dezimalbruchentwicklung (1,234). Für die Zahlentheorie ist die Kettenbruch - Entwicklung, in der werden alle Zahlen durch endliche Kettenbrüche dargestellt, interessanter. Im Allgemeinen wird eine Kettenbruch - Entwicklung wie folgt dargestellt :
dabei sind a i , b i ∈ R mit i = {0, . . . , n}, allerdings müssen sie so beschaen sein, daÿ die entsprechenden Nenner nicht 0 werden. Von nun an betrachten wir den Spezialfall b i = 1.
dafür schreiben wir folgende Abkürzung, wobei cfrac für continued fraction (Kettenbruch) steht.
x = cfrac(a 0 , a 1 , . . . , a n ).
Ein solcher Kettenbruch heiÿt regulär, wenn a i ∈ N für i = {0, . . . , n} gilt.
Page 17
2. Faktorisierung mit Kettenbrüchen
2-1-Grundlagen
Die Grundidee dieses Vefahrens geht auf Legendre zurück und beruht darauf, daÿ bei der Kettenbruch - Entwicklung viele quadratische Reste mod N erzeugt werden. Von Marrison / Brillhardt wurde dazu ein Computer - gerechter Algorithmus entworfen. Die Quadratwurzel von a mod p (a ∈ Z und p ∈ Prim) ist bis auf das Vorzeichen eindeutig bestimmt, da in F p das Polynom X 2 − a höchstens 2 Nullstellen hat. Dies gilt allerdings nicht, falls N eine zusammengesetzte Zahl ist.
Sei N = pq (p, q ∈ Prim), dann ist Z/NZ zum Produkt F p × F q isomorph. Dabei entspricht a mod N dem Paar (a 1 , a 2 ) mit a 1 ∈ F p und a 2 ∈ F q . Existieren b 1 ∈ F p und b 2 ∈ F q mit b 2 i = a i dann sind (±b 1 , ±b 2 ) Quadratwurzeln von (a 1 , a 2 ) (vgl. A.2 auf der Seite 21). Man kann eine Zerlegung von N dadurch konstruieren, daÿ z.B. zwei Zahlen x, y bekannt sind mit x 2 ≡ y 2 ≡ a mod N und x ≡ ±y mod N . Es folgt daraus bekanntlich x 2 ≡ y 2 mit (x + y)(x − y) ≡ 0 mod N . Da N nach Voraussetzung keinen Faktor teilt, erhält man mit ggT(x + y, N ) einen nicht trivialen Teiler von N . (vgl. A.2 auf Seite 21)
Um Quadratwurzeln modulo einer zusammengesetzten Zahl N zu ziehen, braucht man die Faktorzerlegung von N . Es ist allerdings nicht nötig die Quadratwurzel zu ziehen, sondern es reicht wenn man sich ein geeignetes a wählt für das man zwei Quadratwurzeln x ≡ y mod N kennt. Wir kommt man nun zu a ?
1. Lösung : Nach Fermat, wenn N = p · q, wobei p, q annähernd gleich sind. √ Man startet mit x 0 ≥ N und bildet für x = x 0 , x 0 + 1, x 0 + 2, . . . die Dierenzen x 2 − N bis eine Quadratzahl entsteht. Aus x 2 − N = y 2 ⇒ N = x 2 − y 2 =
(x + y)(x − y).
2. Lösung : Man hat u 2 i ≡ q i mod N . Kann man einige q i so wählen, so daÿ deren
Produkt eine Quadratzahl (y 2 := q 1 ·q 2 ·. . .·q n ) ist, dann hat man mit x := u 1 ·. . .·u n , eine Kongruenz x 2 ≡ y 2 mod N gefunden.
Problem : Wie ndet man q i , so daÿ deren Produkt eine Quadratzahl ist ?
Lösung : Wenn Primfaktor - Zerlegung bekannt ist, darauf achten, daÿ das Produkt der Exponenten gerade ist.
Page 21
A. Weitere Erläuterungen
A-1-Fibonacchi - Zahlen Definition A.1.1
Die Fibonacchi - Zahlen F 1 , F 2 , . . . werden deniert durch F 0 = 0 und F 1 = 1 und
F i = F i−1 + F i−2
für i ≥ 2.
Wir sehen ausserdem, daÿ die Zahlen
√ √ 1 − 1 + 5 5 φ 1 = , φ 2 = 2 2
die Gleichung φ 2 = φ + 1 und φ i = φ = φ i−1 + φ i−2 erfüllen
A-2-Quadratische Reste Satz A.2.1
Sei p > 2 ∈ Prim. Dann besitzt die Gleichung x 2 ≡ a mod p für einen quadratischen Rest genau 2 verschiedene Lösungen und es gibt insgesamt p−1 2 quadratische Reste.
Beweis A.2.1
Sei a = b 2 quadratischer Rest. Dann folgt aus x 2 ≡ a bzw. (x − b)(x + b) = 0
p | (x − b)(x + b),
d.h. es gilt entweder x ≡ b mod p oder x ≡ −b mod p. Es gibt daher höchstens zwei Lösungen. Da b + b = 2 · b = 0 für p > 2 sind die beiden Lösungen b und −b verschieden. Die Restklassen 1 2 , 2 2 , . . . , p − 1 2 sind also paarweise gleich, und man erhält p−1 quadratische Reste. 2
Und es gilt zudem noch folgender
Satz A.2.2
Seien p,q > 2 zwei verschiedene Primzahlen und m = pq. Dann hat jeder quadratische Rest modulo m genau vier Wurzeln.
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.