mathe 1

Komposition

Funktionen verknüpfen. f(g(x))

Wobei:

f(x) A→B

g(x) C→D

f(x)eC für alle XeA ist.

Ist alles ab Z ein Rinf?

Ja

(Z,Q,R)

2x * 2x ist?

4x²

Ist (Q,•) Invertiv? Wenn ja welche Zahl nicht?

alle Zahlen sind invertierbar außer die 0!

Ist das richtig oder falsch?

x = pa- r

Falsch! R darf NIE negativ sein.

Mengenschreibweise

Mengenname = {Variable E Grundmenge: Eigenschaft}

Was sind Primzahlzwillinge?

Primzahlen die den Abstand 2 haben.

Negativ Dezimalzahl zu Binär

Normal in binär berechnen.

Dann invertieren.

Dann 0001 dazu rechnen.

Injektiv

Jedes Element wird im Ziel höchstens ein mal getroffen.

Surjektiv

Zu jedem Element des Wertebereichs gibt es mindestens ein Urbild

Für jedes b e B gibt es ein a e A mit f(a) = b

Bijektiv

Injektiv und Surjektiv

Z/7Z

[3]+[5]= ?

[1]

Definition Halbgruppe

Eine halbherzige ist ein Paar (M,*) aus:

1. Einer Menge M die nicht leer ist

2. Einer Rechenoperation * Verknüpfung die assoziativ ist.

Assoziativgesetzt

Es ist egal wo du die Klammern hin machst.

Monoid

Halbgruppe + Neutrales Element

Gruppe

Monoid + ALLE Elemente müssen invertierbar sein

Abelsch/ kommutativ

Egal ob a + boder b + a oder a • b oder b • a

Definition Ring

Zwei Verknüpfungen mit den folgenden Eigenschaften:

+ ist eine Albsche Gruppe

• ist mindestens eine halbgruppe

Beides: das distributivgesetz muss bestehen

Distributivgesetz

Plus und mal müssen „verstreut“ werden können.

a•(b+c) = (a•b)+(a•c)

Binär → Dez

1101

2^i

2³ + 2² + 2^1 = Dez

Binär zweierkomponent → Dez

Ist die Zahl ganz links eine 1?

Beispiel bei 8-bit: (1001 1111)

Dann -(2^i) + 2^i

Ist die Zahl ganz links eine 0? Dann normal

Beispiel: 8-bit: (0010 1111)

Hex in Dez

F6

15•16^1 + 6•16^0 =1 Dez

DEZ in Binär

55

Reihe schreiben:

i Zahl

0 1

1 2

2 4

3 8

4 16

5 32

6 64

Welche Zahl passt rein? 32 mit Index 5

also 55-32=23

Index 5 markieren

Welche Zahl passt bei 23 rein?

16 mit Index 4

Also 32-16=16

Index 4 markieren

Usw

-Dez in Binär

Alles wie davor machen und das Ergebnis investieren und + 0001

Dez in Hex

Beispiel 254

Immer geteilt 16 und Rest ist eine Ziffer für Hex

254:16=15 Rest 14 → 14 ist E

15:16= 0 Rest 15 → 15 ist F

Bei 0 ist fertig

Dann von unten nach oben wie bei binär

FE

Welches Bit System bei DEZ

Beispiel:

4K DEZ in Binär

2^12 sind 4095

Also 12-bit somit brauchen wir das 16 System

Wenn Minus bzw. zweierkomplement dann

8+1 nehmen.

Also 13-bit und somit brauchen wir das 16 System

Invers

e ist ein neutrales Element

Multiplikation:

r • s = e

Addition

r + -s = e

Potenzmenge

Ist die Menge aller möglichen Teilmengen.

Die mächtigkeit

2^n

Beschreibt bei endlichen Mengen die Anzahl der Elemente die in einer Menge enthalten sind (python.length)

Tautologie

Ein aussagenlogischer Ausdruck der immer wahr ist

Kontradiktion

Ein aussagenlogischer Ausdruck der immer falsch ist

Fermat Test

Prüfen ob eine Zahl eine Primzahl ist.

Bsp:

a^p-1 mod p

Beispiel:

Ist 7 eine Primzahl? p = z

Zufallszahl a = 3

3^7-1 mod 7 = R:1 also ja

Wenn der Rest gleich 1 dann Primzahl

Achte auf den Taschenrechner!!

Satz von Euklid

Es gibt unendlich viele Primzahlen.

Carmichael-Zahl

Zusammengesetzte Zahlen die in Primzahl Tests „schmuggeln“

Primzahlen

Sind nur durch 1 oder sich selber teilbar.(hat somit zwei teiler)

Die 1 ist keine primzahl!

Fundamentalsatz der Arithmetik

Besagt das sich jede natürliche Zahl größer 1 in eindeutiger Weise als Produkt von Primzahlen schreiben lässt

Teilfremd

Zwei Zahlen sind teilfremd wenn ggT(x,y)= 1

Euklidischen Algo

ggT(x,y)

ggT(52,13)

52 = 4 • 13 + 0

ggT = 13

ggT(15,8)

15 = 1•8+7

8 = 1•7+1

7 = 7•1+0

ggT = 1

Satz von Euklid

Es gibt unendlich viele Primzahlen

Definition ggT

n|a und n|b und jeder andere gemeinsame teiler teilt automatisch n mit m|n

Lemma von Euklid was besagt das Lemma bezüglich einer Primzahl P und einem Produkt a•b ?

Wenn p das Produkt a•b teilt dann gilt p|a oder p|b

Chiffre

Ein algorithmisches Verfahren zur Verschlüsselung von Daten (Klartext in Geheimtext/Chiffrat) mithilfe eines Schlüssels, sodass die Nachricht für Unbefugte unlesbar wird.

Verknüpfung

Verknüpft zwei Elemente mit einem Operator

Verknüpfung → Halbgruppe → Gruppe → abelsche Gruppe

Determistisch

Eindeutig bestimmt

Probabilistisch

Der Wahrscheinlichkeit nach

Wann ist A=>B wahr?

Wenn B wahr oder beide falsch

Wann ist A<=>B wahr?

Wenn beide wahr oder beide falsch

Wie wird in RSA verschlüsselt?

k^e mod M

Was ist die kleinste Carmichael Zahl?

541

Wertebereich von 16-Bit Zahlen

0bis 65535

2^16

Welcher Zahlenwert kann im 16 Bit zweierkomplement abgebildet werden?

Negativ: -2^n-1

Positiv: 2^n-1 -1

Carmichaelzahl test.

Beispiel ist 165 eine Carmichael Zahl?

1. Primfaktor zerlegen: (was teilt restlos 165? Von 2-15 oder so)

2. 165 = 3•5•11

3. Ziehe überall -1 ab und teile 164 jeweils durch die Zahl

4. Wenn eins nicht restlos teilbar ist dann ist es KEINE Carmichael Zahl

ggT von -105 und -133 ?

beide negativ somit kann das Vorzeichen einfach weggelassen werden.

Ist das Kartesische Produkt Kommutativ?

Nein!

Beispiel

A = {1}

B = {2}

AxB = {(1,2)}

BxA = {(2,1)}

Ist was völlig anderes.

ist es egal ob ich ggT(4,8) oder ggT(8,4) rechne?.

Ja weil sich nur die Rechnung zu Beginn ändert aber der ggT trotzdem gleich bleibt

wie viel Bits brauchen wir für -42733?

im zweierkomplement zieht man immer ein Bit an.

2^16 sind 65.536

Dann einfach 16+1 gleich 17

17 Bits.

RSA entschlüsseln

c^d mod M

RSA

1. zwei Primzahlen suchen p und q

2. M berechnen mit pq

3. Psi M berechnen mit (p-1)*(q-1)

4. e raussuchen wobei teilfremd mit psiM

5. Öffentlicher Schlüssel ist (M,e)

6. Dann ggT(psi(M),e)

7. Lenme von Bezou machen

8. Privater Schlüssel raus holen wie öffentlich aber darf nicht negativ sein. Notfalls + psiM

Verschlüsseln: k^e mod M

Entschlüsseln: c^d mod M

Wann ist etwas invertierba?

Wenn s • r = e

Aus Psi(40) p und q

40:1

40:2

40:3

Bis 10 und alle behalten die restlos aufgehen.

Dann einfach alle Ziffern +1 und gucken ob sie Primzahlen sind. Wenn ja haben wir das Ergebnis.

XOR

Wenn

A XOR B

Dann ist es wahr wenn eins wahr und das andere falsch ist.