2 - Modulo rechnen

Question 1

kongruent modulo

Answer 1

Zwei Zahlen heißen kongruent modulo, wenn sie bei Division durch n denselben Rest haben

Question 2

Teiler

Answer 2

Eine Zahl a heißt Teiler, wenn bei der Division a/n der Rest gleich Null ist.

Schreibweise n|a

Question 3

erweiterter euklidischer Algo

Answer 3

ggT(a,b) = alphaa + betab

Question 4

Einheit

Answer 4

Eine Zahl heißt “Einheit modulo n”, wenn die zugehörige Restklasse [a]n ein Inverses bzgl. der Multiplikation in Zn hat, d.h. wenn es ein [b]n gibt, sodass [a]n*[b]n=1

a ist Einheit, wenn ggT(a,n)=1
Anzahl der Einheiten: phi(n)
Bei p=Primzahl: alle a {1,..,n-1} sind Einheiten

Question 5

endlicher Körper

Answer 5

Bei p=Primzahl: alle a {1,..,n-1} sind Einheiten und Zp somit ein (endlicher) Körper

Question 6

Inverse in Zn berechnen

Answer 6

1. wenn ggT(a,n)=1 -> a ist invertierbar
2. erw. Euklid ergibt alphaa + betab
3. Das Inverse von a ist a’ = alpha mod n

Question 7

Potenzieren in Zn

Answer 7

1. Berechne Binärdarstellung des Exponenten
2. berechne x¹=b0, x²=b1, x^n=bn mod n wo Exponent = 1
3. Berechne das Produkt bi mod n

Question 8

Satz von Euler

Answer 8

Sei a Einheit in Zn, d.h. ggT(a,n)=1

Dann gilt: a^phi(n) kongruent 1 mod n

Question 9

kleiner Satz von Fermat

Answer 9

Sei ggT(a,p)=1 wobei p: Primzahl

Dann gilt: a^(p-1) kongruent 1 mod p

Question 10

RSA keys

Answer 10

private key: p,q,d

public key: n,e

Question 11

RSA decryption/encryption

Answer 11

encrypt: y = x^e mod n
decrypt: x = y^d mod n

Question 12

RSA phi(n)
Eulerfunktion
d e

Answer 12

(p-1)(q-1)
d*e kongruent 1 mod phi(n)

d= ggT(phi(n),e)
e= ggT(phi(n),d)

Question 13

Primitivwurzel

Answer 13

Wenn ggT(a.n)=1

Wenn a^m kongruent 1 mod n genau eine Lösung hat (m=phi(n), dann heißt a “Primitivwurzel von n”.

Question 14

Ordnung

Answer 14

Wenn ggT(a.n)=1
a^m kongruent 1 mod n

die kleinste Zahl m der Lösung m=phi(n) heißt “Ordnung von a” -> ord(a).

Question 15

diskreter Logarithmus

Answer 15

Wenn a Primitivwurzel (=Generator) von p ist, dann erzeugen die Potenzen von a alle Zahlen 1 bis p-1 genau einmal. D.h. für jedes b hat die Gleichung eine eindeutige Lösung i. Die Zahl i ist der diskrete Logarithmus von b zur Basis a modulo p.

i=ind a,p (b)

Dazu gibt es keinen Algorithmus

Question 16

Polynomring

Answer 16

Die Polynome über Zp bilden einen Ring

Question 17

irreduzible Polynome

Answer 17

Entsprechen den Primzahlen in Z
-> Primpolynome in Zp

Ein Polynom f(x) über einem Körper K heißt irreduzibel, wenn es nicht als Produkt zweier Polynome über K dargestellt werden kann, die beide einen niedrigeren Grad als f(x) haben.

Question 18

Körper GF(2^n)

Answer 18

Addition entspricht bitweisem XOR

Multiplikation entspricht mod eines irreduziblen Polynoms vom Grad n

Question 19

effektives modulieren in GF

Answer 19

1. schreibe f(x) in binär
2. verschiebe um eine Stelle nach links. Wenn f(x) aus S fällt: mod m(x)
3. XOR der Binärwerte, je nach Aufbau von g(x)