Rabin-Test

Hildegardis · Newbie Anmeldungsdatum: 27.10.2011 Beiträge: 35

Hallo !

Also ich hänge mal wieder bei einer Aufgabe, die wir in Elem. Zahlenth. bekommen haben:

"Für eine ungerade natürliche Zahl N>=3 sei (N-1)=(2^(t))*n mit ungeradem n geschrieben Dann setze
A(N)= (x € (Z/ZN)^x ; x erfüllt den Rabin-Test).
Dabei erfüllt x den Rabin-Test, wenn x^n kongruent 1 mod N gilt oder ein
s € (0, .... , t-1) mit x^((2^s)*n) kongruent -1 mod N existiert.

Berechnen Sie die Menge A(N) für N=2701= 37*73. "

Hier mal mein Ansatz:

N-1 = 2700
2^2 = 4 und 4 teilt 2700
-> t = 2 denn 2^4 ist die größte Potenz die N-1 teilt

n= (N-1)/(2^t) = 675

=> s € (0, 1)

Und nun gibt es doch 2 Möglichkeiten:
1) ist N ungerade und x teilerfremd zu N, dann muss gelten:
x^n kongruent 1 mod N
oder
2) s € (0,1) mit x^((2^s)*n) kongruent -1 mod N

Wenn nun 1) oder 2) gilt, ist N doch eine Primzahl, oder ????

Allerdings weiß ich hier dann nicht mehr weiter. Ich hätte für 1) ja dann stehen:

x^675 kongruent 1 mod 2701

Aber wie bestimme ich jetzt dieses x ????
Darf ich mir da einfach eines wählen, wenn ja, wie wähle ich es denn am besten?
Und wenn ich dann ein x gewählt habe, woher weiß ich dann ob die Gleichung stimmt. Weil eine Zahl hoch 675 kann man ja schlecht im Kopf rechnen und mein Taschenrechner versagt auch bei so etwas.

Nehme ich dann an, ich hätte das ausgerechnet und wüsste, dass
x^675 nicht kongruent 1 mod 2701 ist.
Dann müsste ich doch Fall 2) überprüfen.
Wenn da dann auch wieder rauskommt, dass
x^((2^s)*675) nicht kongruent -1 mod N ist,
wüsste ich dann endgültig, dass N keine Primzahl ist ?

Aber durch das, dass N=2701=37*73, N also eine Primfaktorzerlegung besitzt, kann N in diesem Fall doch überhaupt keine Primzahl sein.
D.h. der Test müsste doch auch als Ergebnis liefern, dass N keine Primzahl ist ?
Woraus ich dann wieder schließen würde, dass A(N) kein Element enthalten kann ?????

Über Hilfe und Ratschläge würde ich mich riesig freuen !!!! Very Happy

LG Hildegardis

P.S: Das € soll übrigens "Element von" bedeuten.