TI nspire Python Scripts

Antworten
jkessler
Beiträge: 5
Registriert: 14.06.2022 09:38

TI nspire Python Scripts

Beitrag von jkessler »

TI-nspire Python Scripts verschiedenster Algorithmen.

Boolsches Produkt

Code: Alles auswählen

# Author Joel Kessler
def boolean_product(A, B, n_r, m_r):
    res = []
    for row_i in range(0, n_r):
        row = []
        for col_i in range(0, m_r):
            sel_row = A[row_i]
            sel_col = [B_row[col_i] for B_row in B]
            product_row_col = 0
            # (....) or (....)
            for sel_row_e_i in range(0, len(sel_row)):
                sel_row_e = sel_row[sel_row_e_i]
                sel_col_e = sel_col[sel_row_e_i]
                
                if sel_row_e == 1 and sel_col_e == 1:
                    # (a1 and b1) or (....)
                    product_row_col = 1
                    break
            row.append(product_row_col)
        res.append(row)
    return res
    
A = []
B = []
print("Dimension Linke A-Matrix (n x m):")
n_a = int(input("n:"))
m_a = int(input("m:"))
print("Dimension Rechte B-Matrix (n x m):")
n_b = int(input("n:"))
m_b = int(input("m:"))
# (n x m) (n x m)
if m_a != n_b:
    print("Dimensionsfehler.")
else:
    print("Resultierende Matrix: ({},{})".format(n_a, m_b))

    print("Matrix A:")
    for row_i in range(0, n_a):
        row = []
        for pos_i in range(0, m_a):
            row.append(int(input("Position: ({}, {}): ".format(row_i+1, pos_i+1))))
        A.append(row)
    print("Matrix B:")
    for row_i in range(0, n_b):
        row = []
        for pos_i in range(0, m_b):
            row.append(int(input("Position: ({}, {}): ".format(row_i+1, pos_i+1))))
        B.append(row)
        
    print("Matrix A:")
    for row in A:
        print(row)
        
    print("Matrix B:")
    for row in B:
        print(row)
        
res = boolean_product(A, B, n_a, m_b)
print("Boolsches Produkt:")
for row in res:
    print(row)
Dijkstra Algorithmus

Code: Alles auswählen

# Author Joel Kessler 
def remove_from_dict(dict_data, l2):
    for e in l2:
        dict_data.pop(e, None)
        
def remove_from_list(l1, l2):
    lr = list(l1)
    for e in l2:
        if e in lr:
            lr.remove(e)  
    return lr

def dijkstra(edges_and_weight, start_node):
    nodes = set()
    for edge_and_weight in edges_and_weight:
        nodes.add(edge_and_weight[0])
        nodes.add(edge_and_weight[1])
    nodes = sorted(list(nodes))
    if not start_node in nodes:
        print("Ungueltiger start Punk")
        return
    S = []
    # Key: Node, Value: Laenge, Vorgaenger
    columns = [dict.fromkeys(nodes, (None, None))]
    columns[0][start_node] = (0, start_node)
    while len(S) < len(nodes):
        previous_column = columns[-1]
        shortest_l_p = None
        shortest_key = None
        # Finde kleinsten in vorgaeniger liste
        for key in remove_from_list(nodes, S):
            l, p = previous_column[key]
            if l == None:
                continue
            if shortest_l_p == None or l < shortest_l_p[0]:  
                shortest_l_p = (l, p)
                shortest_key = key    
        # Knoten an S hinzufuegen
        S.append(shortest_key)        
        print("Shortest: ", shortest_key, shortest_l_p)
        # Finde verbundene knoten punkte
        neighbours = [ew for ew in edges_and_weight if ew[0] == shortest_key or ew[1] == shortest_key]
        # Entferne benachbarte welche y E (nodes - S)
        neighbours_cleaned = []
        for neighbour in neighbours:
            detected_node = neighbour[0]
            if detected_node == shortest_key:
                detected_node = neighbour[1]
            if detected_node in remove_from_list(nodes, S):
                neighbours_cleaned.append(neighbour)
        print("Neigbours:", neighbours_cleaned)
        
        # Kopiere vorgaenige kolonne
        new_column = previous_column.copy()
        # Entferne abgeschlossene knoten
        remove_from_dict(new_column, S)
        columns.append(new_column)
        print("neighbours_cleaned: " ,neighbours_cleaned)
        # Fuer jeden nachbar
        for v, w, weight in neighbours_cleaned:
            y = v
            s = w
            if v == shortest_key:
                y = w
                s = v 
            y_column_data = previous_column[y]
            if y_column_data[0] == None or y_column_data[0] > shortest_l_p[0] + weight:
                # Setzte kuerzeren weg
                new_column[y] = (shortest_l_p[0] + weight, shortest_key)
        #print("Previous: ", previous_column)
        #print("New: ", new_column)
        print("S:", S)
        print("------------------")
    return columns, S

more_data = True
print("Abbruch mit allen Werten = 0")
start_point = input("Start knoten fuer Algorithmus:")
e_and_w = []
while more_data:
    print("Daten für Punkt:", len(e_and_w))
    a = input("Anfangsknoten:")
    b = input("Endknoten:")
    weight = int(input("Kantengewicht:"))
    if a == "0" and b == "0" and weight == 0:
        more_data = False
        continue
    e_and_w.append((a, b, weight))
cols, diS = dijkstra(e_and_w, start_point)
print("Knoten: (Distanz, Vorgaenger)")
for col in cols:
    print(col)
print("S:", diS)
Erwartungswert / Varianz

Code: Alles auswählen

# Author Joel Kessler V2
def e_randomvar(k_and_ps):
    E_X, VAR_X, SD_X = 0, 0, 0
    # Berechne E(X)
    for k_and_p in k_and_ps:
        k, p = k_and_p
        E_X += k * p
    # Berechne VAR(X)
    for k_and_p in k_and_ps:
        k, p = k_and_p
        VAR_X += ((k - E_X) ** 2) * p
    
    return E_X, VAR_X, VAR_X ** (1/2)

# Based on: https://www.johndcook.com/blog/2010/10/20/best-rational-approximation/
def farey(x, N):
    # y = Ganzzahl faktor
    y = 0
    if x % 1 > 0:
        y = x - (x % 1)
        x = x % 1
    if x == 0:
        return y
    a, b = 0, 1
    c, d = 1, 1
    while (b <= N and d <= N):
        mediant = float(a+c)/(b+d)
        if x == mediant:
            if b + d <= N:
                return "{}/{}".format(int(y * b+d) + a+c, b+d)
            elif d > b:
                return "{}/{}".format(int(y * d) + c, d)
            else:
                return "{}/{}".format(int(y * b) + a, b)
        elif x > mediant:
            a, b = a+c, b+d
        else:
            c, d = a+c, b+d
    if (b > N):
        return "{}/{}".format(int(y * d) + c, d)
    else:
        return "{}/{}".format(int(y * b) + a, b)

more_data = True
print("Abbruch mit allen Werten = esc, BRUECHE UNTERSTUETZT")
print("Ausgabe: E(X) / VAR(X) / SD(X):")
data = []
while more_data:
    print("n-te Variable:", len(data))
    k = input("k:")
    p = input("P(X=k):")
    if k == "esc" and p == "esc":
        more_data = False
        continue
    data.append((float(eval(k)), float(eval(p))))

E_X, VAR_X, SD_X = e_randomvar(data)
print("------------")
print("E(X): ", farey(E_X, 1000), " -> ", round(E_X, 8))
EX_2 = VAR_X + (E_X ** 2)
print("E(X^2): ", farey(EX_2, 1000), " -> ", round(EX_2, 8))
print("VAR(X): ", farey(VAR_X, 1000), " -> ", round(VAR_X, 8))
print("SD(X): ", round(SD_X, 8))
Erweiterter Euklid

Code: Alles auswählen

# Author Joel Kessler
def euclidean_extended(a, b):
    x, y = a, b
    if a < b:
        print("a muss grösser als b sein. Vertausche diese.")
        return [None, None, None, None]
    top_rows = [[a, None, 1, 0], [b, a // b, 0, 1]]
    print(top_rows[0])
    print(top_rows[1])
    breaker_step = 0
    while breaker_step < 25:
        step_row = [None, None, None, None]
        breaker_step += 1
        step_row[0] = top_rows[0][0] - top_rows[1][0] * top_rows[1][1]
        if step_row[0] <= 0:
            print(step_row)
            break
        step_row[1] = top_rows[1][0] // step_row[0]
        step_row[2] = top_rows[0][2] - top_rows[1][2] * top_rows[1][1]
        step_row[3] = top_rows[0][3] - top_rows[1][3] * top_rows[1][1]
        print(step_row)
        top_rows[0] = top_rows[1]
        top_rows[1] = step_row
    return top_rows[1]

in_a = int(input("a = "))
in_b = int(input("b = "))
ggt, _, x, y = euclidean_extended(in_a, in_b)
print("GGT:", ggt)
print("x:", x)
print("y:", y)
print("Diophantische Gleichung: " + str(in_a) + " * " + str(x) + " + " + str(in_b) + " * " + str(y) + " = 1")
print("Allgemein (k E N): " + str(in_a) + " * " + "(" + str(x) + " + " + str(in_b) + " * k) + " + str(in_b) + " * " + "(" + str(y) + " - " + str(in_a) + " * k) = 1")
Euklid

Code: Alles auswählen

# Author Joel Kessler 2
def euclidean(a, b):
    x, y = a, b
    if a < b:
        print("a muss grösser als b sein. Vertausche diese.")
        return None
    previous_row = [a, a // b, b, a - (a // b) * b]
    breaker_step = 0
    while breaker_step < 25:
        print("{} = {} * {} + {}".format(previous_row[0],previous_row[1],previous_row[2],previous_row[3]))
        breaker_step += 1
        if previous_row[3] == 0:
            return previous_row[2]
        step_row = [previous_row[2], previous_row[2] // previous_row[3], previous_row[3], previous_row[2] - (previous_row[2] // previous_row[3]) * previous_row[3]]
        if step_row[3] <= 0:
            print("{} = {} * {} + {}".format(step_row[0],step_row[1],step_row[2],step_row[3]))
            return step_row[2]
        previous_row = step_row
    return None

in_a = int(input("a = "))
in_b = int(input("b = "))
ggt = euclidean(in_a, in_b)
print("GGT:", ggt)
Euler Phi

Code: Alles auswählen

# Author Ramon Stoffel
def euler_phi_numbers(n):
    zn = [x for x in range(n)]
    relatives_primes = []
    for i in zn:
        if ggt(n, zn[i])==1:
            relatives_primes.append(zn[i])
        else:
            continue
    return relatives_primes

def ggt(x , y):
    if y == 0:
        return x
    return ggt(y, x % y)

def modular_invers(a, n):
    v = 1
    d = a
    u = (a == 1)
    t = 1-u
    if (t == 1):
        c = n % a
        u = n // a
        while c != 1 and t == 1:
            q = d // c
            d = d % c
            v = v + q*u
            t = (d != 1)
            if (t == 1):
                q = c // d
                c = c % d
                u = u + q*v
        u = v*(1 - t) + t*(n - u)
    return u
n = int(input("Geben Sie Z-n ein:  "))
print("------------")
res = euler_phi_numbers(n)
print("EULERISCHE PHI FUNKTION: ",len(res))
print("------------")
print("TEILERFREMDE-ELEMENTE / Z-STERN: ",res)
mod_inv_list = []
for i in range(len(res)):
    inv_mod = modular_invers(res[i],n)
    if inv_mod == True:
        mod_inv_list.append(1)
    else:
        mod_inv_list.append(inv_mod)
print("------------")
print("INVERSE VON TEILERFREMDEN_ELEMENTEN AUS Z-STERN: ",mod_inv_list)
Mengen Kreuzprodukt

Code: Alles auswählen

# Author Joel Kessler
def cross_product(A, B):
    res = []
    for b in B:
        for a in A:
            res.append((a, b))
    return res
    
A = []
B = []
print("Abbruch mit allen Werten = esc")
print("Menge A:")
more_data = True
while more_data:
    a = input("a{}:".format(len(A)))
    if a == "esc":
        more_data = False
        continue
    A.append(a)
print("Menge B:")
more_data = True
while more_data:
    b = input("b{}:".format(len(B)))
    if b == "esc":
        more_data = False
        continue
    B.append(b)
A = sorted(set(A))
B = sorted(set(B))
print("--------")
print(sorted(cross_product(A, B)))
Kruskal Algorithmus

Code: Alles auswählen

# Author Joel Kessler
def remove_from_list(l1, l2):
    lr = list(l1)
    for e in l2:
        if e in lr:
            lr.remove(e)  
    return lr

def kruskal_algorithm(edges_and_weights):
    V = set()
    edges_grouped = dict()
    for edge_and_weight in edges_and_weights:
        V.add(edge_and_weight[0])
        V.add(edge_and_weight[1])
        
        if edge_and_weight[2] not in edges_grouped:
            edges_grouped[edge_and_weight[2]] = [(edge_and_weight[0], edge_and_weight[1]), ]
        else:
            edges_grouped[edge_and_weight[2]].append((edge_and_weight[0], edge_and_weight[1]))
    edges_sorted_indecies = sorted(edges_grouped)
    V = sorted(list(V))
    R = [[node] for node in V]
    T = []
    w_T = 0
    # Wiederhole bis alle Knoten besucht
    while V != sorted(list(sum(T, ()))):
        # Gewicht, x E R[a], y E R[b]
        selected_edge = None
        # Kante mit minimalem gewicht finden
        for key in edges_sorted_indecies:
            for i in range(0, len(edges_grouped[key])):
                v, w = edges_grouped[key][i]
                # Finde klassen von v und w
                v_class = None
                w_class = None
                for R_class in R:
                    if v in R_class:
                        v_class = R_class
                    elif w in R_class:
                        w_class = R_class   
                if w_class == None or v_class == None:
                    continue
                if v_class != w_class:
                    # Wenn klasse gefunden, fuege alle elemente aus klasse w zu klasse von v hinzu
                    for w_el_i in range(0, len(w_class)):
                        v_class.append(w_class[0])
                        w_class.remove(w_class[0])
                    # Entferne leere klasse
                    if len(w_class) == 0:
                        R.remove(w_class)
                    selected_edge = (key, v, w)
                    # Loesche selektierte kante
                    edges_grouped[key].remove(edges_grouped[key][i])    
                    break
            if selected_edge != None:
                break
        if selected_edge == None:
            return R, T, w_T
        w_T += selected_edge[0]
        T.append((selected_edge[1], selected_edge[2]))
        print("T added: ", (selected_edge[1], selected_edge[2]))
        print("w(T) added: ", selected_edge[0])
        print("R classes: ", R)
        print("------------")

more_data = True
print("Abbruch mit allen Werten = 0")
e_and_w = []
while more_data:
    print("Daten für Punkt:", len(e_and_w))
    a = input("Anfangsknoten:")
    b = input("Endknoten:")
    weight = int(input("Kantengewicht:"))
    if a == "0" and b == "0" and weight == 0:
        more_data = False
        continue
    e_and_w.append((a, b, weight))
R, T, w_T = kruskal_algorithm(e_and_w)
print("------------")
print("R: ", R)
print("T: ", T)
print("w(T): ", w_T)
Mengenlehre

Code: Alles auswählen

# Author Joel Kessler
def set_values(A, B):
    AANDB = set([a for a in A if a in B])
    AORB = A.union(B)
    ADIFFB = set([a for a in A if a not in B])
    BDIFFA = set([b for b in B if b not in A])
    return AANDB, AORB, ADIFFB, BDIFFA
print("Abbruch mit allen Werten = esc")
print("A:")
more_data = True
A = []
while more_data:
    a = input("a{}:".format(len(A)))
    if a == "esc":
        more_data = False
        continue
    A.append(a)
more_data = True
B = []
while more_data:
    b = input("b{}:".format(len(B)))
    if b == "esc":
        more_data = False
        continue
    B.append(b)
AANDB, AORB, ADIFFB, BDIFFA = set_values(set(A), set(B))
print("A ∩ B: ", sorted(AANDB))
print("A ∪ B: ", sorted(AORB))
print("A \ B:", sorted(ADIFFB))
print("B \ A:", sorted(BDIFFA))
Pagerank Algorithmus

Code: Alles auswählen

# Author Joel Kessler
approx_decimal = 100000
def farey(x, N):
    a, b = 0, 1
    c, d = 1, 1
    while (b <= N and d <= N):
        mediant = float(a+c)/(b+d)
        if x == mediant:
            if b + d <= N:
                return a+c, b+d
            elif d > b:
                return c, d
            else:
                return a, b
        elif x > mediant:
            a, b = a+c, b+d
        else:
            c, d = a+c, b+d
    if (b > N):
        return c, d
    else:
        return a, b

def gauss_jordan(a):
    n = len(a)
    x = [0 for _ in range(0, len(a))]
    # Applying Gauss Elimination
    for i in range(n):
        if a[i][i] == 0.0:
            print("Divide by zero detected!")
            return
        for j in range(i+1, n):
            ratio = a[j][i]/a[i][i]
            for k in range(n+1):
                a[j][k] = a[j][k] - ratio * a[i][k]
    # Back Substitution
    x[n-1] = a[n-1][n]/a[n-1][n-1]
    for i in range(n-2,-1,-1):
        x[i] = a[i][n]
        for j in range(i+1,n):
            x[i] = x[i] - a[i][j]*x[j]
        x[i] = x[i]/a[i][i]
    return x

def pagerank_algorithm(edges, d):
    V = sorted(set(sum(edges, ())))
    N = len(V)
    res = []
    #print(["PR[{}]".format(i) for i in V])
    rhs = []
    for i in V:
        sum_of_pr = []
        res_row = [0 for _ in V]
        res_row[V.index(i)] = 1
        # Endknoten potential_j[1]
        j_to_is = [potential_j for potential_j in edges if potential_j[1] == i]
        #print(i, "->", j_to_is)
        for j_to_i in j_to_is:
            # j = j_to_i[0]
            c_j = len([j_outgoing for j_outgoing in edges if j_outgoing[0] == j_to_i[0]])
            res_row[V.index(j_to_i[0])] += d * (1 / c_j) * -1
            if c_j == 1:
                sum_of_pr.append("PR[{}]".format(j_to_i[0]))
            else:
                sum_of_pr.append("PR[{}] * (1/{})".format(j_to_i[0], c_j))
        sum_of_pr = " + ".join(sum_of_pr)
        if sum_of_pr == "":
            sum_of_pr = "0"
        sum_of_pr = "({})".format(sum_of_pr)
        #d * sum_of_pr + (1 - d) * (1 / N)
        d_approx = farey(d, approx_decimal)
        one_sub_d_approx = farey((1 - d), approx_decimal)
        pr_node = "PR[{}] = ({}/{}) * {} + ({}/{}) * (1/{})".format(i, d_approx[0], d_approx[1], sum_of_pr, one_sub_d_approx[0], one_sub_d_approx[1], N)
        print(pr_node)
        rhs.append((1 - d) * (1 / N))
        res.append(res_row)
    #for row in res:
    #    print(row, rhs[res.index(row)])
    for rhs_index in range(0, len(rhs)):
        res[rhs_index].append(rhs[rhs_index])
    res_eval = gauss_jordan(res)
    # Displaying solution
    print("Loesung: ")
    #sorted_res_eval = dict.fromkeys(res_eval)
    for x_i in range(0, len(res_eval)):
        x = res_eval[x_i]
        approx_x = farey(x, approx_decimal)
        #print("PR[{}] = ({}/{}) = {}".format(V[x_i], approx_x[0], approx_x[1], x))
        #sorted_res_eval[res_eval[x_i]] = ["PR[{}]".format(V[x_i]), "({}/{})".format(approx_x[0], approx_x[1])]
        print("PR[{}] = ({}/{}) = {}".format(str(V[x_i]), approx_x[0], approx_x[1], x))
    """print("Sortierte Loesung: ")
    for key in sorted(sorted_res_eval.keys(), reverse=True):
        print("{} = {} = {}".format(sorted_res_eval[key][0], sorted_res_eval[key][1], key))"""
    return res_eval

more_data = True
edges = []
print("Abbruch mit allen Werten = esc")
d = float(eval(input("Daempfungsfaktor d: ")))
while more_data:
    print("Daten für Punkt:", len(edges))
    a = input("Von Knoten:")
    b = input("Zu Knoten:")
    if a == "esc" and b == "esc":
        more_data = False
        continue
    edges.append((a, b))
R = pagerank_algorithm(edges, d)
#pagerank_algorithm([("1", "3"), ("3", "6"), ("3", "4"), ("3", "2"), ("5", "2"), ("2", "1"), ("4", "2")], 4/5)
Potenzmenge

Code: Alles auswählen

def powerset(fullset):
    # See: https://www.delftstack.com/de/howto/python/powerset-python/
    listsub = list(fullset)
    subsets = []
    for i in range(2**len(listsub)):
        subset = []
        for k in range(len(listsub)):            
            if i & 1<<k:
                subset.append(listsub[k])
        subsets.append(sorted(subset))        
    return subsets
print("Abbruch mit allen Werten = esc")
print("Menge:")
more_data = True
A = []
while more_data:
    a = input("a{}:".format(len(A)))
    if a == "esc":
        more_data = False
        continue
    A.append(a)
subsets = powerset(set(A))
print(len(subsets), subsets)
Prim Algorithmus

Code: Alles auswählen

# Author Joel Kessler 2
def remove_from_list(l1, l2):
    lr = list(l1)
    for e in l2:
        if e in lr:
            lr.remove(e)  
    return lr

def prim_algorithm(edges_and_weights, start_node):
    V = set()
    edges_grouped = dict()
    for edge_and_weight in edges_and_weights:
        V.add(edge_and_weight[0])
        V.add(edge_and_weight[1])
        
        if edge_and_weight[2] not in edges_grouped:
            edges_grouped[edge_and_weight[2]] = [(edge_and_weight[0], edge_and_weight[1]), ]
        else:
            edges_grouped[edge_and_weight[2]].append((edge_and_weight[0], edge_and_weight[1]))
    edges_sorted_indecies = sorted(edges_grouped)
    V = sorted(list(V))
    if not start_node in V:
        print("Ungueltiger start Punkt")
        return
    S = [start_node]
    V.remove(start_node)
    T = []
    w_T = 0
    num_nodes = len(V) + 1
    while len(S) < num_nodes:
        # Gewicht, x E S, y E (V - S)
        selected_edge = None
        # Kante mit minimalem gewicht finden
        for key in edges_sorted_indecies:
            for i in range(0, len(edges_grouped[key])):
                v, w = edges_grouped[key][i]
                if (v in S and w in V) or (w in S and v in V):
                    x = v
                    y = w
                    if y in S:
                        x = w
                        y = v
                    selected_edge = (key, x, y)
                    edges_grouped[key].remove(edges_grouped[key][i]) 
                    break
            if selected_edge != None:
                break
        # Menge S hinzuefuegen
        S.append(selected_edge[2])
        V.remove(selected_edge[2])
        T.append((selected_edge[1], selected_edge[2]))
        w_T += selected_edge[0]
        print("S added: ", selected_edge[2])
        print("T added: ", (selected_edge[1], selected_edge[2]))
        print("w(T) added: ", selected_edge[0])
    return S, T, w_T

more_data = True
print("Abbruch mit allen Werten = 0")
start_point = input("Start knoten fuer PRIM Algorithmus:")
e_and_w = []
while more_data:
    print("Daten für Punkt:", len(e_and_w))
    a = input("Anfangsknoten:")
    b = input("Endknoten:")
    weight = int(input("Kantengewicht:"))
    if a == "0" and b == "0" and weight == 0:
        more_data = False
        continue
    e_and_w.append((a, b, weight))

S, T, w_T = prim_algorithm(e_and_w, start_point)
print("------------")
print("S: ", S)
print("T: ", T)
print("w(T): ", w_T)
Quadratische Restzahlen

Code: Alles auswählen

# Author Joel Kessler und Ramon Stoffel
def euler_phi_numbers(n):
    zn = [x for x in range(n)]
    relatives_primes = []
    for i in zn:
        if ggt(n, zn[i])==1:
            relatives_primes.append(zn[i])
        else:
            continue
    return relatives_primes

def ggt(x , y):
    if y == 0:
        return x
    return ggt(y, x % y)

def modular_invers(a, n):
    v = 1
    d = a
    u = (a == 1)
    t = 1-u
    if (t == 1):
        c = n % a
        u = n // a
        while c != 1 and t == 1:
            q = d // c
            d = d % c
            v = v + q*u
            t = (d != 1)
            if (t == 1):
                q = c // d
                c = c % d
                u = u + q*v
        u = v*(1 - t) + t*(n - u)
    return u

def quadratic_remainders(n):
    remainders = []
    Z_n = euler_phi_numbers(n)
    for i in Z_n:
        remainders.append(i ** 2 % n)
    quadratic_remainders_dict = dict.fromkeys(sorted(Z_n))
    # Leere listen erstellen
    for key in quadratic_remainders_dict.keys():
        quadratic_remainders_dict[key] = []
    # Ordne x quadrate den Restklassen zu
    for remainder_index in range(0, len(remainders)):
        quadratic_remainders_dict[remainders[remainder_index]].append(Z_n[remainder_index])
    # Entferne leere Restklassen
    for key in list(quadratic_remainders_dict.keys()):
        if quadratic_remainders_dict[key] == []:
            quadratic_remainders_dict.pop(key)
    return remainders, quadratic_remainders_dict, Z_n

n = int(input("n = "))
r, qrd, Z_n = quadratic_remainders(n)
print("Z({})*: {}".format(n, Z_n))
print("x-Quadrate:", r)
print("Restklassen:", qrd)
Square-Multiply Algorithmus

Code: Alles auswählen

#Author Joel Kessler
def square_and_multiply_algorithm(basis, exponent, modulo):
    x = basis
    ex_bin = str(bin(exponent))[2:].replace("1", "QM").replace("0", "Q")[2:]
    y_step = x
    print(str(y_step), end=" -> ")
    for letter in ex_bin:
        if y_step >= modulo:
            print(str(y_step) + " mod " + str(modulo), end=" -> ")
            y_step = y_step % modulo
        if letter == "Q":
            y_step = y_step ** 2
            print(str(y_step) + " Q ", end=" -> ")
        if letter == "M":
            y_step = y_step * x
            print(str(y_step) + " M ", end=" -> ")
    print(str(y_step) + " mod " + str(modulo))
    if y_step >= modulo:
        y_step = y_step % modulo
    return y_step
basis, exponent, modulo = int(input("basis = ")), int(input("exponent = ")), int(input("modulo = "))
mod_val = square_and_multiply_algorithm(basis, exponent, modulo)
print("{}^{} mod {} = {}".format(basis, exponent, modulo, mod_val))

Antworten