Zahlentheoretische Algorithmen Hensel-Liftung Multiplikativ inverses Element modulo einer Zweierpotenz bestimmen

Ziel ist es, das multi­plikativ inverse Element a^-1 einer ganzen Zahl a modulo einer Zweierpotenz n = 2^k zu berechnen. Beispiels­weise gilt 5·13    1 (mod 32), d.h. a^-1 = 13 ist das multi­plikativ inverse Element zu a = 5 modulo der Zweierpotenz n = 2⁵ = 32. Natürlich aber geht es nicht um kleine Zahlen wie 5 und 13, sondern um sehr große Zahlen, etwa der Länge von 1024 Bit.

Die Berechnung des multi­plikativ inversen Elements modulo einer Zweierpotenz wird beispiels­weise bei der Montgomery-Multi­plikation benötigt.

Das Standard­verfahren zur Berechnung des multi­plikativ inversen Elementes modulo n ist der erweiterte euklidische Algorithmus, dieser hat eine Zeit­komplexität von Θ(log(n)). Dies ist zwar schnell, aber in dem speziellen Fall, dass der Modul n eine Zweierpotenz ist, geht es schneller, nämlich in Zeit O(log(log(n))). Der entsprechende Algorithmus beruht auf einer zahlen­theoretischen Methode, die als Hensel-Liftung (engl.: Hensel lifting) bekannt ist (nach K. Hensel).

Die Methode eignet sich grund­sätzlich auch für die Berechnung des multi­plikativ inversen Elementes modulo p^k mit p > 2.

Vorbemerkungen

Wenn zwei ganze Zahlen a und b beispiels­weise kongruent modulo 1000 sind, wie etwa a = 7365 und b = 365, dann sind sie auch kongruent modulo 100 und kongruent modulo 10. Dies gilt allgemein für beliebige Modul-Potenzen.

Inverse Elemente

Wir benutzen den Hilfssatz zunächst für folgende Aussage über multi­plikativ inverse Elemente.

Es ist also leicht, wenn das inverse Element von a modulo p^k vorliegt, das inverse Element von a modulo einer kleineren Potenz p^m zu berechnen. Gegebenen­falls ist eine Reduktion modulo p^m erforderlich, damit das inverse Element in die Menge {0, ..., p^m-1} fällt.

An den obigen Zahlen wird deutlich, dass die Umkehrung nicht gilt. Modulo 10 gerechnet ist 7 zu 3 invers, modulo 100 gerechnet jedoch nicht. Es stellt sich die Frage, ob sich das inverse Element modulo 100 irgendwie in einfacher Weise aus dem inversen Element modulo 10 berechnen lässt. Die Antwort ist "ja", und zwar mit der Methode der Hensel-Liftung.

Lemma von Hensel

Das Lemma von Hensel macht eine sehr allgemeine Aussage über Nullstellen von Polynomen modulo Potenzen einer Primzahl. Mit dem speziellen Polynom f(x)  =  a·x – 1 liefert das Lemma von Hensel den Ansatz für die Berechnung von multi­plikativ inversen Elementen modulo Potenzen einer Primzahl.

Anwendung für multi­plikativ inverse Elemente

Sei eine ganze Zahl a gegeben, a teilerfremd zu p. Um das multi­plikativ inverse Element von a modulo p^k zu berechnen, verwenden wir das Polynom

f(x)  =  a·x – 1

Seien zunächst m, k = 1. Wenn r = a^-1 das multi­plikativ inverse Element von a modulo p ist, gilt

f(r)    a·r – 1    0   (mod p)

Die erste Ableitung von f(x) ist f '(x) = a. Damit gilt

f '(r)  =  a    0   (mod p)

denn a und p sind teilerfremd.

Die Voraus­setzungen für das Lemma sind somit erfüllt. Gesucht ist nun eine Zahl s mit s    r  (mod p), derart dass

f(s)    0   (mod p²)

Diese Zahl s lässt sich folgender­maßen berechnen (in ), sie ist modulo p² eindeutig bestimmt:

s   =   r – f(r)·c

wobei für c gilt

c    (f '(r))^-1    a^-1   (mod p)

Um also von r = a^-1, dem inversen Element von a modulo p, zum inversen Element von a modulo p² zu gelangen, berechnet man mit c = a^-1 = r

s   =   r – f(r)·c   =   r – (a·r – 1) · r   =   (2 – a·r) · r

Damit das Ergebnis s in die Menge {0, ..., p²-1} fällt, wird es noch modulo p² reduziert.

Beispiel

Bei dem verwendeten Polynom f(x)  =  a·x – 1 ist es noch nicht einmal erforderlich, dass p eine Primzahl ist. Im folgenden Beispiel verwenden wir p = 10.

Ausgehend vom inversen Element modulo p² lässt sich in entsprechender Weise das inverse Element modulo p⁴ berechnen, usw. Das folgende Programm folgt diesem Ansatz.

Implementierung in Python

Es folgt ein entsprechendes Programm in der Programmier­sprache Python.

Iterative Version

Das Programm berechnet das multi­plikativ inverse Element von a modulo p^k', wobei k' die kleinste Zweierpotenz ist, die größer oder gleich k ist. Wie oben gezeigt, ist das berechnete Ergebnis auch modulo aller kleineren Potenzen von p invers zu a.

# schnelle Berechnung des multiplikativ inversen Elements
# von a modulo einer Potenz p^k
# (iterative Version)
def inv(a, p, k):
    e=1
    r=modinverse(a, p)
    while e<k:
        e+=e
        p*=p
        r = (2-a*r) * r % p
    return r

Der Aufruf inv(3, 10, 5) berechnet als das inverse Element von 3 modulo 10⁵ den Wert 66666667. Dieser Wert ist invers zu 3 modulo 10⁸, aber zugleich auch invers zu 3 modulo aller kleineren Potenzen von 10, also auch modulo 10⁵. Eine Reduktion modulo p^k wird am Schluss des Programms nicht durchgeführt, da der Wert p^k hier nicht zur Verfügung steht.

Rekursive Version

In der rekursiven Version ist dies anders, der Wert n = p^k steht hier zur Verfügung.

# schnelle Berechnung des multiplikativ inversen Elements
# von a modulo einer Potenz p^k
# (rekursive Version)
def invr(a, p, k):
    if k==1:
        return modinverse(a, p)
    n=p**k
    a=a % n
    r=invr(a, p, (k+1)//2)
    return (2-a*r) * r % n

Zu Anfang wird das multi­plikativ inverse Element von a modulo p benötigt. Dieses wird mithilfe des erweiterten euklidischen Algorithmus durch die Funktion modinverse berechnet – ein wenig zusätzlicher Aufwand, aber für die relativ kleine Zahl p. Für p = 2 entfällt dieser Aufwand sogar völlig, denn das multi­plikativ inverse Element zu einer (ungeraden) Zahl a ist stets 1.

Rekursive Version für Zweier­potenzen

Um beispiels­weise das inverse Element von a modulo 2⁵ zu berechnen, geht das rekursive Programm vom inversen Element von a modulo 2³ aus und liftet es nach der oben angegebenen Formel. Das Ergebnis ist das inverse Element von a modulo 2⁶, aber dieses wird unmittelbar modulo 2⁵ reduziert.

Das inverse Element von a modulo 2³ wird rekursiv aus dem inversen Element von a modulo 2² berechnet usw.

Das inverse Element einer ungeraden Zahl a modulo 2¹ ist stets 1; dies ist der Rückgabewert der Funktion für den Exponenten k = 1.

# schnelle Berechnung des multiplikativ inversen Elements
# von a mit a ungerade modulo einer Zweierpotenz n = 2^k
# (rekursive Version)
def inv2(a, k):
    if k==1:
        return 1
    n=2**k
    a=a % n
    r=inv2(a, (k+1)//2)
    return (2-a*r) * r % n

Die Berechnung von n = 2^k lässt sich effizient durch die Bit-Schiebe­operation 1<<k realisieren. Die Reduktion modulo n lässt sich effizient durch die Bit-Maskierungs­operation & n-1 realisieren.

Sinnvoll ist es dann, bereits nach der Berechnung von a·r eine Reduktion modulo n einzuschieben (und die Modulo-Operation natürlich durch eine Bit-Maskierungs­operation zu implementieren):

    return (2-a*r%n) * r % n

Die folgende Funktion inv2s entspricht der vorigen Funktion inv2 mit dieser Änderung sowie mit der Anwendung von Bit-Schiebe­operationen und Bit-Maskierungs­operationen.

# schnelle Berechnung des multiplikativ inversen Elements
# von a mit a ungerade modulo einer Zweierpotenz n = 2^k
# (rekursive Version, mit Schiebe- und Maskierungsoperationen)
def inv2s(a, k):
    if k==1:
        return 1
    m=(1<<k)-1
    a=a & m
    r=inv2s(a, (k+1)>>1)
    return (2-(a*r & m)) * r & m

Zeitkomplexität

Wir gehen davon aus, dass p = 2 ist, dass also das multi­plikativ inverse Element modulo einer Zweierpotenz gesucht ist. Dann verursacht der Aufruf der Funktion modinverse keinen Aufwand.

In der iterativen Version wird der Exponent e, beginnend bei 1, solange verdoppelt, bis er den Wert k erreicht oder über­schritten hat. Dies ist nach log(k) Schritten geschehen.

In der rekursiven Version wird der Wert von k solange halbiert, bis er den Wert 1 erreicht hat. Dies ist ebenfalls nach log(k) Schritten geschehen.

Die Zeit­komplexität der beiden Verfahren liegt demnach in O(log(k)) bzw. bezogen auf den Modul n = 2^k in O(log(log(n))).

Implementierung in Haskell

Es folgen noch entsprechende Implementierungen der Funktionen inv sowie inv2 in der funktionalen Programmier­sprache Haskell.

Für die Implementierung der iterativen Version wird eine Methode verwendet, die von einem Iterations­schema ausgeht, daraus Iterations­gleichungen ableitet und diese dann in systematischer Weise in ein Haskell-Programm überführt.

-- schnelle Berechnung des multiplikativ inversen Elements
-- von a modulo einer Potenz p^k
-- (iterative Version)
inv :: Integer -> Integer -> Integer -> Integer
inv a p k = iterate 1 p (modinverse a p) 
    where
    iterate e p r | e>=k    = r
                  | otherwise = iterate (e+e) (p*p) ((2-a*r)*r `mod` (p*p))

Auch hier wird die Funktion modinverse verwendet, um zu Anfang das multi­plikativ inverse Element von a modulo p zu berechnen.

Die rekursive Version zur Berechnung des multi­plikativ inversen Elements modulo einer Zweierpotenz entspricht genau der entsprechenden Python-Funktion inv2.

-- schnelle Berechnung des multiplikativ inversen Elements
-- von a mit a ungerade modulo einer Zweierpotenz n = 2^k
inv2 :: Integer -> Integer -> Integer
inv2 a 1 = 1
inv2 a k = (2-a*r) * r `mod` n
    where
    n = 2^k
    r = inv2 (a `mod` n) ((k+1) `div` 2)

Literatur

Weiter mit:

H.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 24.09.2018   Updated: 27.08.2021