Mathematik
Mathematik
Mathematik
Kartei Details
| Karten | 29 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 28.03.2018 / 30.03.2018 |
| Weblink |
https://card2brain.ch/box/20180328_mathematik
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20180328_mathematik/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
rläutern Sie die typischen Rechenoperationen bei asymmetrischen Verschlüsselungsverfahren. Orientieren Sie sich hierbei an dem RSA-Verfahren.
Addition und Multiplikation von endlichen Körpern
Addition: XOR
Multiplikation: arithmetische Multiplikation
Was wird bei der Modulo-Arithmetik als Modul bezeichnet? (Der Begriff ist in der Mathematik doppelt belegt)
Teiler einer Restwertberechnung
m (möge die Zahl hinter mod sein)
Was wird bei algebraischen Strukturen als neutrales und was als inverses Element bezeichnet? Nennen Sie jeweils ein Beispiel für die Addition und Multiplikation.
- a-1 oder -a wird inverses Element bzgl. der Addition genannt.
- 0 ist das neutrale Element bzgl. der Addition, da a+0 immer a ist.
Sie wollen entsprechend der Modulo-Arithmetik zwei Zahlen dividieren. Unter welcher Bedingung ist dies möglich?
Die Zahlen müssen Ganzzahlen sein und ungleich 0.
Was lässt sich durch den einfachen Euklid‘schen Algorithmus berechnen?
der größte gemeinsame Teiler (ggT) zweier Zahlen
Was wird in dieser Veranstaltung unter einer Linearkombination verstanden? Geben Sie dazu drei Beispiele an.
- Linearkombination einer Zahl z ist die Summe zweier Produkte, deren Teilfaktoren vorgegeben sind:
z = u*a + v*b, wobei a und b vorgeben sind.
Beispiel mit a=2 und b=7
0 = 7*2 – 2*7
1 = -3*2 + 1*7
2 = 8*2 - 2*7
3 = -9*2 + 3*7
4 = -5*2 + 2*7
Wodurch unterscheidet sich der erweiterte Euklid’sche Algorithmus vom einfachen?
Erweitere Euklid nutzt Linearkombination: Es lässt sich der ggT(a,b) als Linearkombination von a und b darstellen:
ggT(a,b)= u*a+v*b.
Der erw. Euklid benutzt die Differenzen, nur zusätzlich als Linearkombination.
Für welchen Zweck wird der erweiterte Euklid’sche Algorithmus meistens in der Kryptographie benutzt?
Schnelles(!) Bestimmen des inversen Elements in der Modulo Arithmetik
An element a Z has a multiplicative inverse a −1 if and only if gcd(∈ a, m) = 1, where gcd is the greatest common divisor
Wie können Sie testen, ob zwei positive ungleiche Zahlen teilerfremd sind? Geben Sie dazu zwei Verfahren an.
Es muss der Satz von Euler gelten
Skizzieren Sie die Idee der schnellen Exponentiation. In welchen kryptographischen Verfahren wird dieses Potenzieren z.B. benötigt?
Potenzieren (Exponentiation) wird auf mehrfaches Multiplizieren zurückgeführt.
Beispiel: 34 ≡ ? (mod 5) ⇒ 3*3*3*3 ≡ 1 (mod 5)
RSA, Diffie Hellman (AES)
Geben Sie ein Rechenverfahren an, mit dem Sie die Anzahl der Multiplikationen bei der schnellen Exponentiation bestimmen können.
n-1 Quadrierungen, wobei n die Anzahl der Ziffern des Exponenten in Binärdarstellung ist Dazu wird addiert:
• (Für jede 1 im Binärwert eine weitere Multiplikation) - 1
Unter welcher Bedingung existiert bzgl. der Multiplikation ein inverses Element bei der Modulo-Arithmetik?
wenn a und m teilerfremd --> insbesondere wenn es eine Primzahl ist
Wie können Sie ein existierendes inverses Element bzgl. der Multiplikation berechnen? Geben Sie mindestens zwei Verfahren dazu an
Euklid + Linearkombination (erweiterter Euklid)
u*a+v*m ≡ 1 (mod m)
Wie können Sie testen, ob zwei positive ungleiche ganze Zahlen rö- ßer als 1 teilerfremd sind? Geben Sie dazu zwei Verfahren an.
Euklid
Definieren Sie die Teilbarkeit am Beispiel a teilt b. Falls a b teilt und a auch c teilt, teilt dann a auch 2*b-3*c? Begründen Sie Ihre Antwort.
Für alle Zahlen a, b, k aus ℕ mit a>b gilt:
Wenn k beide Zahlen a und b teilt, dann teilt auch k die Differenz a-b.
Definieren Sie die Eigenschaften der algebraischen Struktur Gruppe. Erfüllt eine Gruppe immer das Kommutative Gesetz?
- Abgeschlossenheit
- Assoziativgesetz
- Neutrales Element
- Inverses Element
- Kommutativgesetz
.Auf welche zwei prinzipiellen Arten können Sie eine Operation (Operator) definieren? Wann ist welche Art angemessen?
- Bei endlichen Mengen kann eine 2-dimensionale Verknüpfungstabelle zur Definition der Operatoren benutzt werden.
- Bei unendlichen Mengen wird das Ergebnis der Operatoren mit einem Algorithmus definiert.
Was wird unter der algebraischen Struktur Ring verstanden? Worin unterscheidet sich ein Ring von einem Körper?
- (G,⊕) eine abelsche Gruppe ist
- (G,⊙) eine Halbgruppe ist
- das Distributivgesetz gilt
- --> mit Körper gehen alle 4 Grundrechenarten
Was wird unter der algebraischen Struktur kommutativer Ring mit 1 verstanden?
- Ring mit neutralem Element bezügl. der Multiplikation
Was wird unter einem Galois Field (GF) verstanden? Was bedeutet das n in GF(n)?
- Endlicher Körper = finite field = Galois Field = Körper mit einer Grundmenge aus endlich vielen Elementen
- wobei n die Anzahl der Elemente ist
.Es gibt einen Satz, der sagt, für welche n ein GF(n) existiert. Wie lautet dieser?
Es gibt zu den Primzahlenpotenzen pm (mit m>0) endliche Körper mit pm Elementen.
Was ist ein Polynom? Geben Sie das Verfahren an, nach dem zwei Polynome addiert oder subtrahiert werden.
arithmetischer Ausdruck:
p(x) = anxn+an-1xn-1+an-2xn-2+ … +a1x1+a0x0
man addiert die Koeffizienten: p(x)+q(x)
man subtrahiert die Koeffizienten: p(x)-q(x)
Wann wird ein Polynom irreduzibel genannt?
wenn es nur triviale Teiler besitzt oder wenn es sich nicht als Produkt aus Polynomen mit niedrigerem Grad schreiben lässt.
Was ist unter folgendem Satz zu verstehen: Für jeden Körper K ist K[x] ein kommutativer Ring mit 1?
- Kommutativgesetzt gilt (Vertauschungsgesetz)
- Es gibt ein neutrales Element
Nennen Sie bei Polynomen bzgl. der Addition und der Multiplikation das neutrale Element. Sind diese Elemente Polynome?
Addition: 0
Multiplikation: 1
Nein
Woran können Sie an der Angabe K[x]m(x) (und den dazu gehörenden Formeln) erkennen, ob es sich um einen Polynomrestring oder um einen Polynomrestkörper handelt?
Der Polynom-Restring [x]m(x) wird dann zum Körper, wenn m(x) irreduzibel ist.
Was ist ein Polynomrestring? Erläutern Sie dazu die Schreibweise K[x]m(x).
Menge der Reste bei der Division
K(Polynom) Modulo(Polynom)
Warum ist die Angabe des Moduls m(x) bei der Addition in einem Polynomrestring nicht notwendig?
Die Addition in [x]m(x) ist abgeschlossen.
Die Subtraktion in [x]m(x) ist abgeschlossen.
Existiert bei Polynomrestringen immer ein inverses Element bzgl. der Multiplikation? Welche Bedingung muss erfüllt sein, damit dies existiert?
Der Polynom-Restring [x]m(x) wird dann zum Körper, wenn m(x) irreduzibel(teilerfremd) ist.
