Faktorisierung mit Kettenbrüchen

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 ² − 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 ² 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 ² ≡ y ² ≡ a mod N und x ≡ ±y mod N . Es folgt daraus bekanntlich x ² ≡ y ² 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 ² − N bis eine Quadratzahl entsteht. Aus x ² − N = y ² ⇒ N = x ² − y ² =

(x + y)(x − y).

2. Lösung : Man hat u ² i ≡ q i mod N . Kann man einige q i so wählen, so daÿ deren

Produkt eine Quadratzahl (y ² := q 1 ·q 2 ·. . .·q n ) ist, dann hat man mit x := u 1 ·. . .·u n , eine Kongruenz x ² ≡ y ² 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 φ ² = φ + 1 und φ ⁱ = φ = φ ⁱ⁻¹ + φ ⁱ⁻² erfüllen

A-2-Quadratische Reste Satz A.2.1

Sei p > 2 ∈ Prim. Dann besitzt die Gleichung x ² ≡ 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 ² quadratischer Rest. Dann folgt aus x ² ≡ 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 ² , . . . , p − 1 ² 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.