Arithmetik

Montgomery-Multiplikation in Java

Die Montgomery-Multi­plikation ist ein Verfahren zur modularen Multi­plikation, bei dem nur in einer Vorbereitungs­phase eine Reduktion modulo n erforderlich ist. Anschließend sind nur Multi­plikationen und Additionen erforderlich sowie außerdem div- und mod-Operationen mit einer Zweierpotenz m. Bei binärer Zahlen­darstellung sind aber diese beiden letzteren Operationen sehr einfach durch Bit-Operationen zu realisieren.

Implementierung in Java

Es folgt die Implementierung in der Programmier­sprache Java. In der Klasse Montgomery sind die Funktionen der Montgomery-Arithmetik zusammen­gefasst. Der Modul n wird im Konstruktor der Klasse übergeben. In der Funktion preprocess werden k und m = 2k ermittelt; ferner werden die Werte np = n' = -n-1 mod m und mm = m2 mod n voraus­berechnet.

In der Funktion mred wird die Operation mod m wird durch bitweises Und mit den k Einsen von m-1 realisiert, die Operation div m durch Rechts­schieben um k Stellen.

Für die Berechnung des inversen Elements von n modulo der Zweierpotenz m = 2k wird die superschnelle Funktion inv verwendet. Die Zeit­komplexität der Funktion inv(n, k) beträgt O(log k) = O(log log m). Die etwas seltsame Reduktion modulo m in der return-Anweisung ist erforderlich, um ein nicht­negatives Ergebnis zu erzeugen.

 

public class Montgomery
{
    private long n, np, m, mm, m1;
    private int k;

    public Montgomery(long n_)
    {
        preprocess(n_);
    }

    // ---------- Montgomery-Arithmetik

    // übernimmt den Modul n mit n ungerade,
    // setzt k und m=2^k mit m>n;
    // berechnet - n hoch -1 mod m sowie m*m mod n,
    // setzt die Montgomery-Eins m1
    private void preprocess(long n_)
    {
        n=n_;
        assert n%2==1 : "Modul n muss ungerade sein";
        k=(int)(Math.log(n)/Math.log(2)+2);
        m=1L<<k;      // 2^k
        np=m-inv(n, k);
        mm=m*m%n;
        m1=m%n;
    }

    // Montgomery-Reduktion
    public long mred(long x)
    {
        long t=(x*np)&(m-1);    // mod m
        long q=(x+t*n)>>k;      // div m
        if (q>=n)
            q=q-n;
        return q;
    }

    // Montgomery-Multiplikation
    public long mmul(long a, long b)
    {
        return mred(a*b);
    }

    // Transformation x -> h(x)
    public long mtra(long x)
    {
        return mmul(x, mm);
    }


    // ---------- Hilfsfunktion
    // berechnet das multiplikativ inverse Element von a modulo 2^k
    private static long inv(long a, int k)
    {
        if (k==1) return 1;
        long m, r;
        m=1L<<k;      // 2^k
        a=a % m;
        r=inv(a, (k+1)/2);
        return ((2-a*r) * r % m + m) % m; 
    }

    // ---------- Test

    public static void main(String[] args)
    {
        long n_=15;
        Montgomery mont=new Montgomery(n_);
        long a=7, b=13;
        System.out.println("n = "+n_+", a = "+a+", b = "+b);
        System.out.println("konventionell: a*b % n = "+(a*b % n_));
        long c=mont.mred(mont.mmul(mont.mtra(a), mont.mtra(b)));
        System.out.println("Montgomery:    a*b % n = "+c);
    }

}

 

 

Weiter mit:  [Implementierung in Python]   oder   [up]

 

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