Seite 1 von 1

HÜ-Aufgabe3: ElGamal

Verfasst: 23. Dez 2011 19:03
von SLik_
Hallo zusammen,

ich scheine die genannte Rechenregel für das Legendre-Symbol (Hausübung A3) nicht zu verstehen.
Kann mir da jemand erklären, wie diese gemeint ist?
Ist der Punkt zwischen den beiden ersten Operatoren evtl. keine Multiplikation?

Mein Verständnis:
- Haben a und k mod p beide einen Quadratischen Rest oder beide einen quadratischen Nichtrest mod p, so hat ihr Produkt einen quadratischen Rest mod p.
- Hat einer der beiden Werte einen Quadratischen Rest und der andere einen quadratischen Nichtrest, so hat ihr Produkt einen quadratischen NICHT-Rest
- Ist der Rest von einem der beiden 0, ist das Produkt der beiden auch 0 mod p

Das letzte leuchtet ein, aber die ersten beiden Fälle funktionieren so nicht.
Beispiel:
p=11, a=20, k=26
a mod p = 9 => (a/p) =1
k mod p = 4 => (k/p) =1
a*k mod p = 3 => (a*k/p) =-1 != 1 = (a/p)*(k/p)
was einen Widerspruch zur Rechenregel darstellt.

Wie ist die Regel sonst gemeint?!

Vielen Dank für die Hilfe und ein fröhliches Weihnachtsfest!
Gruß
Slik

Re: HÜ-Aufgabe3: ElGamal

Verfasst: 24. Dez 2011 01:53
von SupeRalF
3 ist in deinem beispiel ein Quadratischer Rest, also
(3/p) = 1
Denn es existiert ein x, so dass gilt:
x^2 = 3 (mod p)
Dies gilt zb für x=5

Damit eine Zahl a ein quadratischer Rest ist, muss es ein x geben, so dass x^2 = a (mod p).
Am besten du schaust noch einmal auf die Definition des Legendre Symbols!