GPU-Computing

Montgomery-Multiplikation mit Langzahlen

 aufwärts

Die Montgomery-Multi­plikation ist eine Methode zur Berechnung von a·b mod n, bei der die Reduktion modulo n ohne Division auskommt. Stattdessen wird eine Montgomery-Reduktion ausgeführt, bei der lediglich div- und mod-Operationen mit einer Zweierpotenz erforderlich sind; diese können bei binärer Zahlen­darstellung sehr einfach realisiert werden. Insbesondere bei Berechnungen mit langen Zahlen ist die Montgomery-Multi­plikation von Vorteil.

Lange Zahlen werden als Arrays von 32-Bit-Integer-Zahlen dargestellt. Die Klasse BigInt realisiert diese Darstellung und stellt die zugehörigen-Arithmetik-Operationen zur Verfügung. Die Montgomery-Reduktion mit Langzahlen lässt sich in folgender Weise durchführen.

Montgomery-Reduktion

Gegeben sind der Modul n und die Zahl b = 232. Mit k ist die Anzahl der 32-Bit-Wörter bezeichnet, die zur Darstellung des Moduls n erforderlich sind. Die Zweierpotenz m > n ergibt sich implizit als 232 k. Vorausberechnet wird die Zahl n' = - n-1 mod b.

 

Algorithmus Montgomery-Reduktion mred(x)
Eingabe:Langzahl x mit  0kleiner gleichx < n·m, vorausberechnete Zahl  n' = - n-1 mod b
Ausgabe:mred(x)  =  x·m-1 mod n
Methode:
  1. setze q = x
  2. für i = 0 bis k-1 wiederhole
    1. setze  t = q[0]·n' mod b
    2. setze  q = q + n·t
    3. schiebe q um 1 Wort nach rechts
  3. wenn qgrößer gleichn dann setze  q = q – n
  4. gib q zurück

 

 

Das folgende Programm realisiert die Funktion mred. Die Variablen k, n und np sind global deklariert. Die Variable np enthält den voraus­berechneten Wert n'.

    // führt die Montgomery-Reduktion einer Zahl x durch
    public BigInt mred(BigInt x)
    {
        assert x.compareTo(n.mul(m))<=0;   // x <= n*m

        int t;
        BigInt q=new BigInt(x);    // Copy-Konstruktor
        for (int i=0; i<k; i++)
        {
            t=q.p[0]*np;       // modulo 2^32 Rechnung
            q.addTo(n.mul(t));
            q=q.rightWordShift(1);
        }
        if (q.compareTo(n)>=0)
            q=q.sub(n);
        return q;
    }

 

Bei dieser Berechnung werden nur Addition und Multi­plikation sowie die Schiebe-Operation verwendet.

Montgomery-Multiplikation

Die Montgomery-Multi­plikation mmul(a, b) ist definiert als mred(a*b). Die ent­sprechenden Berechnungen für die Multi­plikation und die Montgomery-Reduktion lassen sich in folgender Weise ineinander verschränken.

    // Montgomery-Multiplikation von a und b
    public BigInt mmul(BigInt a, BigInt b)
    {
        int t;
        BigInt c=new BigInt();
        for (int i=0; i<k; i++)
        {
            c.addTo(a.mul(b.p[i]));
            t=c.p[0]*np;
            c.addTo(n.mul(t));
            c=c.rightWordShift(1);
        }
        if (c.compareTo(n)>=0)
            c=c.sub(n);
        return c;
    }

 

Transformation

Bevor Zahlen mittels Montgomery-Multi­plikation miteinander multi­pliziert werden können, müssen sie trans­formiert werden. Die ent­sprechende Trans­formation einer Zahl x ind den Wert h(x) entspricht einer Montgomery-Multi­plikation mit mm = m2 mod n. Der Wert von mm wird im voraus berechnet.

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

 

Modulare Exponentiation

Mithilfe der oben dar­gestellten Funktionen lässt sich die schnelle modulare Exponentiation ai mod n wie folgt realisieren:

    // modulare Exponentation a^i mod n
    public BigInt mexp(BigInt a, BigInt i)
    {
        BigInt ha=mtra(a);  // Transformation
        BigInt hc=mmodexp(ha, i);
        BigInt c=mred(hc);  // Rücktransformation
        return c;
    }

    // schnelle Exponentiation
    public BigInt mmodexp(BigInt a, BigInt i)
    {
        BigInt c=mtra(BigInt.ONE);
        for (int j=i.len-1; j>=0; j--)
            for (int k=31; k>=0; k--)
            {
                c=mmul(c, c);
                if (getBit(i.p[j], k))
                    c=mmul(a, c);
            }
        return c;
    }

   //liefert true, wenn Bit k einer int-Zahl z gleich 1 ist
    private boolean getBit(int z, int k)
    {
        return (z & (1<<k)) != 0;
    }

 

Literatur

[Mont 85]P. Montgomery: Modular Multiplication Without Trial Division. Mathematics of Computation, Vol. 44, 170, 519-521 (1985)

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 31.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