<jupyter_start><jupyter_text>This sage worksheet is part of the course  Cryptography  that I taught jointly with <NAME> contributing to the summer school Faszination Mathematik 2018. The course contained a theoretical part and a programming part, where the students programmed an RSA cryptosystem from scratch. This worksheet contains more basics in Python and some computational experiments with prime numbers.  8: ListenListen sind Datentypen, die mehrere Objekte geordnet zusammenfassen. Das n-te Element einer Liste L erhält man mit L[n], wobei Python bei 0 zu zählen beginnt. Mit dem Befehl append kann man eine Liste vergrößern, mit pop(n) kann das n-te Element aus einer Liste entfernen. Außerdem kann man auch Listen addieren und mit Zahlen multiplizieren.  Was passiert bei der Addition von zwei Listen und bei einer Multiplikation von einer Zahl mit einer Liste?<jupyter_code>L = [1,2,3,4]
print(L)
L.append(5)
print(L)
L.pop(2); L.pop(1);
print(L)
K = ['Listen', 1,'koennen', 2,'verschiedene', 3,'Datentypen', 4,'enthalten', 5]
print(K+L)
len(L)<jupyter_output><empty_output><jupyter_text>9: ListenkomprehensionIn Python gibt es nützliche Funktionen um Listen zu erstellen. Eine der mächtigsten ist die Listenkomprehension. Mit der kann man, ähnlich wie in der Mathematik, Listen von Elementen, die bestimmte Bedingungen erfüllen erstellen.<jupyter_code>QuadratZahlen = [a**2 for a in range(1,100)] #Die Liste der Quadratzahlen von 1 bis 99^2
print (QuadratZahlen)
print (UngeradeZahlen)
UngeradeZahlen = [a for a in range(1,100) if a%2 == 1] #Die Liste der ungeraden Zahlen von 1 bis 100<jupyter_output><empty_output><jupyter_text>Definiere mit Listenkomprehension die Liste der Zahlen zwischen 1 und 1000, die 1 modulo 7 sind und die Liste der Zahlen zwischen 1 und 100, die relativ prim zu 5 sind.<jupyter_code>def mehrstufigerzufallsversuch(a,b):
    if a<=b:
        tmp = b
        b = a
        a = tmp
    r = a%b
    while r > 0:
        a = b
        b = r
        q = a//b
        r = a - q*b
    return b
koprim_zu_5_MZV = [a for a in range(1,101) if mehrstufigerzufallsversuch(a,5)==1]
print (koprim_zu_5_MZV)
def GGT_KP(a,b):
    if a<=b:
        tmp = b
        b = a
        a = tmp
    r = a%b
    while r > 0:
        a = b
        b = r
        q = a//b
        r = a - q*b
for a in range(1,100):
    if GGT_KP(a,5) == 1:
    return a
Modulo_7_KP = [a for a in range(1,1000) if a % 7 == 1]
Modulo7 = [i for i in range(2,1000) if i % 7 == 1]
print(Modulo7)
def BinomischerRadius(a,b):
    if a>b:
        g = a
        k = b
    else:
        g = b
        k = a
        
    r = g % k
    q = g // k
    
    #print(str(g)+" = "+str(k)+" * "+str(q)+" + "+str(r))
    gleichungen = []
    gleichungen.append([g,k,q,r])
    
    while r != 0:
        g = k
        k = r
        r = g % k
        q = g // k
        #print(str(g)+" = "+str(k)+" * "+str(q)+" + "+str(r))
        gleichungen.append([g,k,q,r])
        
    #print("Der ggT ist "+str(k)+"!")    
    
    #for i in range (len(gleichungen)):
        #s = ""
        #for j in range (4):
            #s += str(gleichungen[i][j])+" "
        #print(s)
    
    
    
    return k
Koprim5 = [a for a in range(1,100) if BinomischerRadius(a,5) == 1]
print(Koprim5)
koprim_5_M = [a for a in range(1,100) if a%5 != 0]<jupyter_output><empty_output><jupyter_text>10: Primzahlen  Wir wollen nun einen Algorithmus programmieren, der bei Input n die Liste aller Primzahlen unter n ausgibt.<jupyter_code>def prim_zahlen(n):
    if n<=2:
        return [] #Das ist die leere Liste
    if n==2:
        return [2]
    L = []
    for i in range(2,n):
        ist_prim = True
        for j in range(2,i):
            if i%j == 0:
                ist_prim = False
                break
        if ist_prim:
            L.append(i)
    return L
prim_zahlen(100)
test = primzahlen(50000)<jupyter_output><empty_output><jupyter_text>def isPrime(a):    b = True    if a > 2:        for i in range(2,a//2 +1):            if a % i == 0:                b = False                break    return b def givePrimes(q):    if q > 0:        Primes = [a for a in range(2,q) if isPrime(a)]    else:        Primes = ["Zahl soll größer als 0 sein!"]    return Primes<jupyter_code>Primes = givePrimes(50000)
print(Primes)
def primenumbers(n):
    L = []
    for a in range(2,n):
        is_prime = True
        for i in range(2,(a//2)+1):
            if a%i == 0:
                is_prime = False
                break
        if is_prime:
            L.append(a)
    return L
P = primenumbers(50000)
def prime_KP(n):
    L = []
    for a in range(2, n):
        ist_prim = True
        for b in range(2, a):
            if a % b == 0:
                ist_prim = False
                break
        if ist_prim:
            L.append(a)
    return L
prime_KP(102)
Q = prime_KP(100)
test == Q<jupyter_output><empty_output><jupyter_text>11: <NAME>Ein Schritt im RSA-Algorithmus basiert auf der Berechnung von $a^b\mod n$, wobei $a,b,n$ alle sehr große Zahlen sein können. Es ist sehr ineffizient zuerst $a^b$ zu berechnen und danach die Zahl modulo n zu nehmen. Stattdessen kann man so vorgehen.Der Algorithmus unterscheidet zwei Fälle:- *Fall 1*: Wenn der Exponent $b$ ungerade ist schreibe $a^b = a^{b-1}\cdot a$. Wir versuchen $a^{b-1}\mod n$ schnell zu berechnen und dann multiplizieren wir das Ergebnis mit $a$.- *Fall 2*: Wenn der Exponent $b$ gerade ist benutzen wir $a^b = (a^2)^{b/2}$. Wir berechnen nun $a' = a^2\mod n$ und müssen nun $(a')^{b/2}\mod n$ berechnen.Nun wird diese Fallunterscheidung immer wieder gemacht. Nach jedem Schritt wird der Exponent entweder um 1 kleiner, oder sogar halbiert. Sobald der Exponent bei 1 oder 2 ankommt, geben wir das Ergebnis aus. Wir demonstrieren die Vorgehensweise mit $a^{25} \mod n$.In *Schritt 1* schreiben wir \[a^{25} = a^{24}\cdot a.\]Nun wollen wir $a^{24}$ ausrechnen. In *Schritt 2* benutzen wir\[a^{24} = (a^{2})^{12}.\]*Schritt 3*:\[(a^2)^{12} = ((a^2)^2)^6.\]*Schritt 4*:\[((a^2)^2)^6 = (((a^2)^2)^2)^3.\]*Schritt 5*:(((a^2)^2)^2)^3 = (((a^2)^2)^2)^2\cdot (((a^2)^2)^2).Zusammenfassend haben wir\[a^{25} = (((a^2)^2)^2)^2\cdot (((a^2)^2)^2)\cdot a.\]Somit können wir die 25-te Potenz von $a$ nur durch mehrmaliges Quadrieren berechnen.  Schreibe einen Algorithmus fürs schnelle Potenzieren   12: PlottenOft hilft es sich Mengen zu veranschaulichen, indem man sie graphisch darstellt. Um zu sehen wie die Anzahl der Primzahlen wächst könnte man zum Beispiel die Funktion $\pi(x)$ plotten, die die Anzahl der Primzahlen unter $x$ angibt. Dafür lernen wir zuerst wie man in Python plottet.  Plotte die Funktion $\pi(x)$<jupyter_code>import matplotlib.pyplot as plt #matplotlib ist eine Bibliothek zum plotten. Die muss man zuerst importieren, um sie benutzen zu können
plt.plot([1,2,3,4])
plt.ylabel('some numbers')
plt.show()
plt.plot([1,2,3,4], [1,4,9,16]) #Plottet eine Funktion die f(1) = 1, f(2)=4, f(3)=9, f(4)=16 erfüllt und verbindet die Datenpunkte mit Linien<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12396576319543509, 'fraction_numerical': 0.033951497860199714, 'mean_word_length': 2.908026755852843, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '486181', 'license': 'MIT', 'n_tokens_mistral': 2746, 'n_tokens_neox': 2641, 'n_words': 847, 'path': 'Faszination Mathematik-Cryptography/Primzahlen.ipynb', 'repo_name': 'michaelneururer/notebooks-teaching', 'size': '7030'}