GPU-Computing

Montgomery-Multiplikation in Java

 aufwärts

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.

 

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=1<<k;      // 2^k
        np=m-inverse(n, m);
        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);
    }

    // Montgomery-Eins
    public long one()
    {
        return m1;
    }

    // Montgomery-Inkrementieren
    public long inc(long x)
    {
        long i=x+one();
        return i<n? i: i-n;   // i mod n
    }

    // ---------- Hilfsfunktionen

    // berechnet das multiplikativ inverse Element von a in Zn*
    private long inverse(long a, long n)
    {
        long[] g=extgcd(a, n);
        assert g[0]==1 : "a und n müssen teilerfremd sein";
        return g[1]%n;
    }

    // erweiterter euklidischer Algorithmus
    private long[] extgcd(long a, long b)
    {
        long[] g=new long[3];
        long q, h;
        long u=1, t=1;
        long v=0, s=0;
        while (b>0)
        {
            q=a/b;
            h=a-q*b; a=b; b=h;
            h=u-q*s; u=s; s=h;
            h=v-q*t; v=t; t=h;
        }
        g[0]=a; g[1]=u; g[2]=v;
        return g;
    }

    // ---------- 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:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 29.08.2014   Updated: 07.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik