Berechnungsverfahren

Python-Modul Prime

Die folgenden Python-Funktionen implementieren Berechnungen mit großen Primzahlen für kryptografische Anwendungen. Zuvor wird das Modul BasicFunctions importiert.

Erläuterungen zu den hier zusammenfassend aufgeführten Python-Funktionen finden sich im Artikel Primzahltest.

# Fermat-Test
def isCompositeFermat(n):
    return modexp(2, n-1, n) != 1

# modifizierte Version modexp2
# berechnet m hoch e mod n
def modexp2(m, e, n):
    if e==0:
        return 1
    if e%2==1:
        return m * modexp2(m, e-1, n) % n
    else:
        x=modexp2(m, e//2, n)
        p=x*x % n
        # zusaetzliche Pruefung:
        if p==1:
            assert x==1 or x==n-1
        return p

# Fermat-Test mit Basis a
# liefert true, wenn n zusammengesetzt ist
def isCompositeWitness(a, n):
    try:
        p=modexp2(a, n-1, n)
        return p!=1
    except:
        return True


# Miller-Rabin-Test mit k Wiederholungen
# liefert true, wenn n zusammengesetzt ist
def isCompositeMillerRabin(n, k=20):
    if n==2 or n==3:
        return False
    for i in range(k):
        a=randint(2, n-2)
        if isCompositeWitness(a, n):
            return True
    return False

# gibt true zurueck, wenn n (hoechstwahrscheinlich) zusammengesetzt ist
def isComposite(n):
    return isCompositeMillerRabin(n)

# gibt true zurueck, wenn n (hoechstwahrscheinlich) eine Primzahl ist
def isPrime(n):
    return n>1 and not isComposite(n)

Zufällige gewählte Primzahlen

Häufig wird eine zufällig gewählte Primzahl einer bestimmten Länge k Bit benötigt. Die folgenden Funktionen in der Programmiersprache Python liefern entsprechende Primzahlen. Hierzu wird die Funktion randomOdd aus dem Modul BasicFunctions herangezogen, die wiederum auf die kryptografisch sichere Funktion truerandint zurückgreift.

Eine Möglichkeit, eine zufällige Primzahl p der Länge k Bit zu erzeugen, besteht darin, solange zufällige ungerade Zahlen n zu ziehen, bis n eine Primzahl ist. Ein Primzahltest mit der Funktion isPrime ist oben angegeben.

# waehlt zufaellige Primzahl der Laenge k Bit, k>2
def randomPrime(k):
    n=randomOdd(k)
    while not isPrime(n):
        n=randomOdd(k)
    return n

 

Blum-Primzahlen sind Primzahlen, die kongruent 3 modulo 4 sind, also z.B. 3, 7, 11, 19, 23, 31, ...

# waehlt zufaellig eine Blum-Primzahl der Laenge k, k>2
# also eine Primzahl, die kongruent 3 mod 4 ist
def randomBlumPrime(k):
    n=randomInt(k-2)*4+3    # 3 mod 4
    while not isPrime(n):
        n=randomInt(k-2)*4+3
    return n

 

Starke Primzahlen sind Primzahlen der Form p = 2q+1, wobei auch q Primzahl ist, also z.B. 5, 7, 11, 23, 31, ... Jede starke Primzahl p > 5 ist Blum-Primzahl.

# waehlt zufaellig eine starke Primzahl der Laenge k, k>3
def randomStrongPrime(k):
    p=randomBlumPrime(k)
    while not isPrime(p//2):
        p=randomBlumPrime(k)
    return p

 

In der Gruppe ℤn* mit n einer starken Primzahl ist es sehr leicht, ein erzeugendes Element zu finden. Denn die Hälfte aller Elemente sind erzeugende Elemente, und der Test, ob eine Zahl g ein erzeugendes Element ist, besteht lediglich darin, zu prüfen, ob gn/2 mod n  ≠  1 ist.

# gibt ein zufaellig gewaehltes erzeugendes Element der
# Gruppe Zn* zurueck, wobei n eine starke Primzahl ist
def generatingElement(n):
    g=randint(2, n-2)
    while not isGeneratingElement(g, n):
        g=randint(2, n-2)
    return g

# prueft, ob g erzeugendes Element der
# Gruppe Zn* ist, wobei n eine starke Primzahl ist
def isGeneratingElement(g, n):
    return modexp(g, n//2, n)!=1

 

 

Weiter mit:   [up]

 

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