Faktorisierung mit Kettenbruch < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:33 Sa 12.04.2014 | | Autor: | Leon89 |
| Aufgabe | Faktorisieren der Zahl n = 9073.
Es sei
i 0
a 95
b 95
[mm] b^2 [/mm] mod n -48
Zerlegung [mm] -1*2^4*3 [/mm]
in Primfaktoren
Vektoren (1,4,1,0)
i 1
a 3
b 286
[mm] b^2 [/mm] mod n 139
Zerlegung
in Primfatoren
Vektor
i 2
a 1
b 381
[mm] b^2 [/mm] mod n -7
Zerlegung -1*7
Vektor (1,0,0,1)
i 3
a 26
b 1119
[mm] b^2 [/mm] mod n 87
Zerlegung 3*29
Vektor
i 4
a 2
b 2619
[mm] b^2 [/mm] mod n -27
Zerlegung [mm] -1*3^3
[/mm]
Vektor (1,0,3,0)
Primzahlenmenge {-1,2,3,7}
Die ensprechenden Vektoren sind (1,4,1,0) , (1,0,0,1) und (1,0,3,0)
Die Summe von dem ersten und dem dritten Vektor sind Null modulo 2. |
Meine Frage ist wieso ist die Summe von dem ersten Vektor und dem dritten Vektor Null modulo 2 ist ? und warum der zweite nicht ? Wie berechne ich das ?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:45 Sa 12.04.2014 | | Autor: | leduart |
Hallo
was du da machst ist mir schleierhaft, da ich nicht wiess was es bedeutet mittels Kettenbruch zu faktorisieren
aber dass die Summe der 2 Vektoren also (2,4,4,0)=(0,0,0,0) mod 2 ist kann man einfach sehen,
und der dritte als Summe mit jedem der anderen halt nicht.
Gruß leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:16 So 13.04.2014 | | Autor: | felixf |
> Faktorisieren der Zahl n = 9073.
>
> Es sei
>
> i 0
> a 95
> b 95
> [mm]b^2[/mm] mod n -48
> Zerlegung [mm]-1*2^4*3[/mm]
> in Primfaktoren
> Vektoren (1,4,1,0)
>
> i 1
> a 3
> b 286
> [mm]b^2[/mm] mod n 139
> Zerlegung
> in Primfatoren
> Vektor
>
> i 2
> a 1
> b 381
> [mm]b^2[/mm] mod n -7
> Zerlegung -1*7
> Vektor (1,0,0,1)
>
> i 3
> a 26
> b 1119
> [mm]b^2[/mm] mod n 87
> Zerlegung 3*29
> Vektor
>
>
> i 4
> a 2
> b 2619
> [mm]b^2[/mm] mod n -27
> Zerlegung [mm]-1*3^3[/mm]
> Vektor (1,0,3,0)
>
> Primzahlenmenge {-1,2,3,7}
> Die ensprechenden Vektoren sind (1,4,1,0) , (1,0,0,1) und
> (1,0,3,0)
> Die Summe von dem ersten und dem dritten Vektor sind Null
> modulo 2.
>
> Meine Frage ist wieso ist die Summe von dem ersten Vektor
> und dem dritten Vektor Null modulo 2 ist ? und warum der
> zweite nicht ?
Nun, weil das in diesem Beispiel nunmal so ist. Das ist natuerlich nicht immer so.
> Wie berechne ich das ?
Du schreibst die Vektoren als Spalten in eine Matrix und berechnest modulo 2 den Kern. Jedes nicht-triviale Element des Kerns liefert eine Linearkombination (mit Koeffizienten 0 und 1) der Vektoren, die modulo 2 gerade 0 ergibt.
Jede solche Linearkombination fuehrt zu einer Gleichung [mm] $x^2 \equiv y^2 \pmod{n}$, [/mm] die mit etwas Glueck mit $ggT(x - y, n)$ oder $ggT(x + y, n)$ einen nicht-trivialen Faktor von $n$ liefert.
LG Felix
|
|
|
|
