Informatik Security
Topic 2 Modular Arithmetic and Group Theory
Topic 2 Modular Arithmetic and Group Theory
Eigenschaften einer Primzahl (p)?
Poisitive und teilerfremde Zahl ausser mit 1 und mit sich selbst.
Was besagt das "Euclid's Theorem"?
Es gibt eine unendliche Menge an Primzahles
Was sagt die "Prime counting function" aus?
Die Anzahl an Primzahlen welche bis n existieren
Was besagt das "prime number theorem"?
Das Prime Number Theorem beschreibt, dass die Dichte der Primzahlenverteilung bis n.
Je höher n, umso höher tiefer ist die Dichte
Was besagt das "Fundamental Theorem of Arithemtic"?
Jede Zahl grösser als 1 ist entweder eine Primzahl oder ein Produkt von Primzahlen
z.B:
Was ist der GCD (grösster gemeinsamer Teiler) ?
Der GCD ist die höchstmöglichste Zahl welche zwei Zahlen teilt
Wann sind zwei Zahlen "relatively Prime"?
wenn der gcd(a,b) =1 ergeben
Beutet auch, dass sie keine gemeinsamen Primfaktoren haben
Hint: wenn p=prim und gcd(a,p)=1, dann gilt das für jedes a€{1,...p-1}
Was besagt die "Euler's Totient Function"?
Diese Funktion gibt Auskunft über die Menge an teilerfremden Zahlen von n
Siehe auch Speziellfall wenn n=prim ist
Wann sind zwei Zahlen "congruent modulo n"?
Wenn a mod n = b mod n
Was besagt der "kleine" Satz von Fermat wenn man die beiden Zahlen p=prime und a=€{1,...p-1} nimmt?
Siehe Bild
Was besagt das "Euler Theorem"?
Wenn gcd(a,n) =1, dann gilt a^°(n) = 1 mod n -> siehe auch Bild
°(n) = Euler function (Anzahl Teilerfremde Zahlen von n)
Wann ist eine Zahl g "primitive root modulo n"?
Wenn mit einer Zahl g^k mod n, alle Teilerfremden Zahlen von n erzeugt werden können.
n>1, g>0, a grösser 1 und kleiner n und teilerfremd zu n
es existieren root modulo n Zahlen für n=2, n=4, n=p^k und n=2p^k
Was ist die Bedingung für das "Multiplikative Inverse von a Modulo n"?
n>1 und 1<= a < n
a* a^-1 = 1 mod n
Das multiplikative inverse existiert nur wenn gcd(a,n) = 1
1^-1 mod 11 = 1 1*1 mod 11 = 1
2^-1 mod 11 = 6 2*6 mod 11 = 1
4^-1 mod 11 = 3 4*3 mod 11 = 1
Was ist die order (ord(G)) einer Gruppe (G)?
Ist die Anzahl an Elementen (|G|) in der Gruppe
Geben Sie den Inhalte der additiven Gruppe Z11
Z11= {0,1,2,3,4,5,6,7,8,9,10}
Regel: siehe Bild
Geben Sie den Inhalte der multiplikative Gruppe Z4 und Z11 an
Z4 = {1,3}
Z11 = {1,2,3,4,5,6,7,8,9,10}
Wie ist die Ordnung eines Elementes definiert und erklären Sie dies mit der multiplikativen Gruppe Z*15 an.
x^k modulo Gruppe muss 1 ergeben -> das ist die Bedingung
Also muss das Element x aus einer Gruppe g, hoch eine Zahl k modulo g eins ergeben.
Hier en Beispiel mit der Z*15
Erklären Sie was ein Generator einer Gruppe ist
Ein Generator ist ein Element der Gruppe der alle Zahlen in der Gruppe generieren kann indem man die Zahl potenziert von 1 ans potenziert.
P.S. ein Generator ist immer ein "primitive root modulo n"
Wann ist eine Gruppe zyklisch?
Wenn mindestens ein Element der Gruppe ein Generator für alle Zahlen in der Gruppe ist.
Was ist eine Subgruppe einer Gruppe?
Wenn die Elemente in einer Subgruppe auch in einer Gruppe vorkommen.
Ausserdem muss das neutrale ELement, Funktion und inverse Funktion auch indentisch sein
Wann ist eine Primzahl eine "safe prime"?
wenn q = (p-1)/2 auch wiederum eine Primzahl gibt
Wieviele Subgruppen hat eine Multiplikative "safe prime" Gruppe?
Eine Subgruppe einer safe prime hat immer 4 Untergruppen
Wie werden Subgruppen einer Gruppe generiert?
Supgruppen werden generiert indem man jedes Element in der Gruppe faktoriert.
Elemente welche die selben Zahlen generieren, sind in der selben Gruppe
Spezielfall safe prime Zahlen: Jeder Generator von Z*p ist entweder ein Generator von Gq oder Z*p
Geben Sie für die Variablen in der Zeichnung eine Elementeigenschaft in einer Multiplikativen Gruppe an
- g
- a, b
- A = g^a , B = g^b
- k = g^a*^b
siehe Bild
Geben Sie für die Variablen in der Zeichnung eine Elementeigenschaft in einer Gruppe an
- g
- a, b
- A = g^a , B = g^b
- k = g^a*^b
siehe Bild
-
- 1 / 25
-
Cartes-fiches
Eigenschaften einer Primzahl (p)?
Poisitive und teilerfremde Zahl ausser mit 1 und mit sich selbst.
Was besagt das "Euclid's Theorem"?
Es gibt eine unendliche Menge an Primzahles
Was sagt die "Prime counting function" aus?
Die Anzahl an Primzahlen welche bis n existieren
Was besagt das "prime number theorem"?
Das Prime Number Theorem beschreibt, dass die Dichte der Primzahlenverteilung bis n.
Je höher n, umso höher tiefer ist die Dichte
Was besagt das "Fundamental Theorem of Arithemtic"?
Jede Zahl grösser als 1 ist entweder eine Primzahl oder ein Produkt von Primzahlen
z.B:
Was ist der GCD (grösster gemeinsamer Teiler) ?
Der GCD ist die höchstmöglichste Zahl welche zwei Zahlen teilt
Wann sind zwei Zahlen "relatively Prime"?
wenn der gcd(a,b) =1 ergeben
Beutet auch, dass sie keine gemeinsamen Primfaktoren haben
Hint: wenn p=prim und gcd(a,p)=1, dann gilt das für jedes a€{1,...p-1}
Was besagt die "Euler's Totient Function"?
Diese Funktion gibt Auskunft über die Menge an teilerfremden Zahlen von n
Siehe auch Speziellfall wenn n=prim ist
Wann sind zwei Zahlen "congruent modulo n"?
Wenn a mod n = b mod n
Was besagt der "kleine" Satz von Fermat wenn man die beiden Zahlen p=prime und a=€{1,...p-1} nimmt?
Siehe Bild
Was besagt das "Euler Theorem"?
Wenn gcd(a,n) =1, dann gilt a^°(n) = 1 mod n -> siehe auch Bild
°(n) = Euler function (Anzahl Teilerfremde Zahlen von n)
Wann ist eine Zahl g "primitive root modulo n"?
Wenn mit einer Zahl g^k mod n, alle Teilerfremden Zahlen von n erzeugt werden können.
n>1, g>0, a grösser 1 und kleiner n und teilerfremd zu n
es existieren root modulo n Zahlen für n=2, n=4, n=p^k und n=2p^k
Was ist die Bedingung für das "Multiplikative Inverse von a Modulo n"?
n>1 und 1<= a < n
a* a^-1 = 1 mod n
Das multiplikative inverse existiert nur wenn gcd(a,n) = 1
1^-1 mod 11 = 1 1*1 mod 11 = 1
2^-1 mod 11 = 6 2*6 mod 11 = 1
4^-1 mod 11 = 3 4*3 mod 11 = 1
Was ist die order (ord(G)) einer Gruppe (G)?
Ist die Anzahl an Elementen (|G|) in der Gruppe
Geben Sie den Inhalte der additiven Gruppe Z11
Z11= {0,1,2,3,4,5,6,7,8,9,10}
Regel: siehe Bild
Geben Sie den Inhalte der multiplikative Gruppe Z4 und Z11 an
Z4 = {1,3}
Z11 = {1,2,3,4,5,6,7,8,9,10}
Wie ist die Ordnung eines Elementes definiert und erklären Sie dies mit der multiplikativen Gruppe Z*15 an.
x^k modulo Gruppe muss 1 ergeben -> das ist die Bedingung
Also muss das Element x aus einer Gruppe g, hoch eine Zahl k modulo g eins ergeben.
Hier en Beispiel mit der Z*15
Erklären Sie was ein Generator einer Gruppe ist
Ein Generator ist ein Element der Gruppe der alle Zahlen in der Gruppe generieren kann indem man die Zahl potenziert von 1 ans potenziert.
P.S. ein Generator ist immer ein "primitive root modulo n"
Wann ist eine Gruppe zyklisch?
Wenn mindestens ein Element der Gruppe ein Generator für alle Zahlen in der Gruppe ist.
Was ist eine Subgruppe einer Gruppe?
Wenn die Elemente in einer Subgruppe auch in einer Gruppe vorkommen.
Ausserdem muss das neutrale ELement, Funktion und inverse Funktion auch indentisch sein
Wann ist eine Primzahl eine "safe prime"?
wenn q = (p-1)/2 auch wiederum eine Primzahl gibt
Wieviele Subgruppen hat eine Multiplikative "safe prime" Gruppe?
Eine Subgruppe einer safe prime hat immer 4 Untergruppen
Wie werden Subgruppen einer Gruppe generiert?
Supgruppen werden generiert indem man jedes Element in der Gruppe faktoriert.
Elemente welche die selben Zahlen generieren, sind in der selben Gruppe
Spezielfall safe prime Zahlen: Jeder Generator von Z*p ist entweder ein Generator von Gq oder Z*p
Geben Sie für die Variablen in der Zeichnung eine Elementeigenschaft in einer Multiplikativen Gruppe an
- g
- a, b
- A = g^a , B = g^b
- k = g^a*^b
siehe Bild
Geben Sie für die Variablen in der Zeichnung eine Elementeigenschaft in einer Gruppe an
- g
- a, b
- A = g^a , B = g^b
- k = g^a*^b
siehe Bild
