Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Wurzelziehen modulo N

ZahlReich - Mathematik Hausaufgabenhilfe » Universitäts-Niveau » Zahlentheorie » Wurzelziehen modulo N « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Kay_s (Kay_s)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Kay_s

Nummer des Beitrags: 139
Registriert: 01-2001
Veröffentlicht am Montag, den 10. Oktober, 2005 - 18:07:   Beitrag drucken

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)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Christian_s (Christian_s)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Christian_s

Nummer des Beitrags: 1945
Registriert: 02-2002
Veröffentlicht am Dienstag, den 11. Oktober, 2005 - 13:24:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 1448
Registriert: 05-2002
Veröffentlicht am Dienstag, den 11. Oktober, 2005 - 23:02:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Kay_s (Kay_s)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Kay_s

Nummer des Beitrags: 140
Registriert: 01-2001
Veröffentlicht am Dienstag, den 11. Oktober, 2005 - 23:08:   Beitrag drucken

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!
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Kay_s (Kay_s)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Kay_s

Nummer des Beitrags: 141
Registriert: 01-2001
Veröffentlicht am Dienstag, den 11. Oktober, 2005 - 23:23:   Beitrag drucken

@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)

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page