| Autor |
Beitrag |
    
Kay_s (Kay_s)
Erfahrenes Mitglied
Benutzername: Kay_s
Nummer des Beitrags: 139
Registriert: 01-2001
| | Veröffentlicht am Montag, den 10. Oktober, 2005 - 18:07: | 
|
Hallo,
Wie löst man die Gleichung x2 = a (mod N) zu gegebenem a und einer zusammengesetzten Zahl N?
Ist N prim, so gibt es ein Verfahren zur effizienten Bestimmung der Wurzel.
Im anderen Fall soll es auch möglich sein, falls man die Primfaktorzerlegung von N kennt - ich weiß aber nicht wie.
Bsp.:
a = 1, N = 1034 + 9
Finde nichttriviale Wurzel x² = 1 (mod N)
D. h. x <> -1 bzw. x <> 1.
Wer kann helfen?
Danke,
Kay S.
(Beitrag nachträglich am 10., Oktober. 2005 von Kay_S editiert) |
Christian_s (Christian_s)
Senior Mitglied
Benutzername: Christian_s
Nummer des Beitrags: 1945
Registriert: 02-2002
| | Veröffentlicht am Dienstag, den 11. Oktober, 2005 - 13:24: |
|
Hallo Kay
Ich habe leider keine Lösung für deine Aufgabe, aber mich würde interessieren wie man die Wurzeln bestimmt wenn N prim ist.
Kannst du das vielleicht mal kurz beschreiben falls es nicht zu lang ist?
MfG
Christian |
Mainziman (Mainziman)
Senior Mitglied
Benutzername: Mainziman
Nummer des Beitrags: 1448
Registriert: 05-2002
| | Veröffentlicht am Dienstag, den 11. Oktober, 2005 - 23:02: |
|
allgemein würd ich sagen muß gelten:
(x + k1*N)^2 = a + k2*N
mit k1 und k2 aus IN0
allgemein ist mir das ein Rätsel wie das gehen könnte;
x^2 == 3 (mod 7)
3 + 7k ist eine Quadratzahl
1^2 == 1 (mod 7)
2^2 == 4 (mod 7)
3^2 == 2 (mod 7)
4^2 == 2 (mod 7)
5^2 == 4 (mod 7)
6^2 == 1 (mod 7)
7^2 == 0 (mod 7)
es gibt kein k, damit auch keine Wurzel;
und bei deinem Beispiel wäre ein Versuch mal
modul-1;
x^2 == 1 (mod N)
x = +1
x = -1 = N-1
fertig.
Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*
|
Kay_s (Kay_s)
Erfahrenes Mitglied
Benutzername: Kay_s
Nummer des Beitrags: 140
Registriert: 01-2001
| | Veröffentlicht am Dienstag, den 11. Oktober, 2005 - 23:08: |
|
Sei p prim. Gelöst werden soll x² = a (mod p).
Fall 1: p = 3 (mod 4)
Euler-Kriterium => a(p-1)/2 = 1 (mod p) bzw. a(p+1)/2 = a (mod p).
Da p+1 durch 4 teilbar, ist x = a(p+1)/4 (mod p) eine Wurzel, was mit schneller Exponentiation in Polynomialzeit berechenbar ist.
Fall 2: p = 1 (mod 4)
Man sucht ein b mit der Eigenschaft, daß D := b² - a kein Quadrat (mod p) ist (findet man schnell durch Probieren).
Dann berechnet man in der Körpererweiterung Fp[sqrt(D)] die Wurzel x = (b + sqrt(D))(p+1)/2, die auch in Fp liegt.
Das beweist allerdings nicht die polynomielle Laufzeit des Wurzelziehens, da das Erzeugen von b probabilistisch ist! |
Kay_s (Kay_s)
Erfahrenes Mitglied
Benutzername: Kay_s
Nummer des Beitrags: 141
Registriert: 01-2001
| | Veröffentlicht am Dienstag, den 11. Oktober, 2005 - 23:23: |
|
@Mainzi:
Nicht jedes Element besitzt eine Wurzel! Das Euler-Kriterium gilt nur für Quadrate mod p.
Ist p prim, dann sind in Fp genau die Hälfte der Elemente Quadrate (zählt man die 0 nicht mit).
Besitzt N genau k Primteiler, dann gibt es zu jedem Quadrat genau k Wurzelpaare (+w und -w) mod N.
Könnte man umgekehrt diese berechnen, so hätte man eine Faktorisierung von N, so etwa
a = x² = y² (mod N)
==> (x + y)(x - y) = 0 (mod N)
==> ggT(x+y,N) und ggT(x-y,N) sind Teiler von N.
(Beitrag nachträglich am 12., Oktober. 2005 von Kay_S editiert) |
|
