Systematische Programmentwicklung

Python-Modul BasicFunctions

Die folgenden Python-Funktionen implementieren grundlegende Berechnungen für die Arithmetik in einem endlichen Körper.

Nähere Erläuterungen zu den hier zusammenfassend aufgeführten Programmen finden Sie unter Modulare Exponentiation, Erweiterter euklidischer Algorithmus und Multiplikativ inverses Element.

Die folgende Funktion zur schnellen Exponentiation modulo n ist ein wesentlicher Baustein für viele weitere Berechnungsverfahren der Modulo-Arithmetik.

# berechnet m hoch e mod n
def modexp(m, e, n):
    if e==0:
        return 1
    elif e%2==1:    # e ungerade
        return modexp(m, e-1, n)*m % n
    else:
        return modexp(m, e//2, n)**2 % n

Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler g von zwei nichtnegativen ganzen Zahlen a und b. Der erweiterte euklidische Algorithmus berechnet zusätzlich die Koeffizienten u und v einer Darstellung des größten gemeinsamen Teilers g als ganzzahlige Linearkombination von a und b.

# berechnet den groessten gemeinsamen Teiler
# von zwei nichtnegativen ganzen Zahlen a und b
def ggt(a, b):
    if b==0:
        return a
    else:
        return ggt(b, a%b)

# berechnet den groessten gemeinsamen Teiler g von a und b
# sowie eine Darstellung von g als Linearkombination
# von a und b mit ganzzahligen Koeffizienten u und v
# gibt das Tripel (g, u, v) zurueck
def extgcd(a, b):
    if b==0:
        return a, 1, 0
    else:
        g, u, v = extgcd(b, a%b)
        q=a//b
        return g, v, u-q*v

Gesucht ist das multiplikativ inverse Element a^-1 eines Elements a in der multiplikativen Gruppe ℤ_n*. Hierzu wird der erweiterte euklidische Algorithmus verwendet. Damit a ∈ ℤ_n* gilt, müssen a und n teilerfremd sein.

# berechnet das multiplikativ inverse Element von a modulo n
def modinverse(a, n):
g, u, v = extgcd(a, n)
return u%n

Weiter mit: [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 02.10.2015 Updated: 03.11.2025
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden