HÜ-Aufgabe3: ElGamal

SLik_
Neuling
Neuling
Beiträge: 10
Registriert: 30. Nov 2009 15:10

HÜ-Aufgabe3: ElGamal

Beitrag 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

SupeRalF
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 4. Okt 2010 16:48

Re: HÜ-Aufgabe3: ElGamal

Beitrag 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!

Antworten

Zurück zu „Archiv“