Bessere Möglichkeiten, eine Modulo-Operation zu implementieren (Algorithmusfrage)

Question

Ich habe kürzlich versucht, einen modularen Potenzierer zu implementieren. Ich schreibe den Code in VHDL, aber ich suche einen eher algorithmischen Rat. Die Hauptkomponente des modularen Exponentiators ist ein modularer Multiplikator, den ich auch selbst implementieren muss. Ich hatte keine Probleme mit dem Multiplikationsalgorithmus - es fügt nur hinzu und verschiebt sich und ich habe einen guten Job dabei gemacht herauszufinden, was alle meine Variablen bedeuten, so dass ich in einer ziemlich vernünftigen Zeitmenge multiplizieren kann.

Das Problem, das ich habe, ist mit der Implementierung der Modulo-Operation im Multiplikator. Ich weiß, dass wiederholte Subtraktionen funktionieren, aber es wird auch langsam sein. Ich fand heraus, dass ich den Modul verschieben könnte, um große Vielfache des Moduls effektiv zu subtrahieren, aber ich denke, dass es immer noch bessere Möglichkeiten geben könnte, dies zu tun. Der Algorithmus, den ich bin Werk so etwas wie dieser mit (seltsam Pseudo-Code folgt):

result,modulus : integer (n bits) (previously defined) 
shiftcount : integer (initialized to zero) 
while((modulus<result) and (modulus(n-1) != 1)){ 
    modulus = modulus << 1 
    shiftcount++ 
} 
for(i=shiftcount;i>=0;i--){ 
    if(modulus<result){result = result-modulus} 
    if(i!=0){modulus = modulus >> 1} 
} 

So ... ist dies ein guter Algorithmus, oder zumindest ein guter Anfang? Wikipedia diskutiert nicht wirklich Algorithmen zur Implementierung der Modulo-Operation, und wenn ich versuche, anderswo zu suchen, finde ich wirklich interessante, aber unglaublich komplizierte (und oft nicht verwandte) Forschungsarbeiten und Publikationen. Wenn es einen offensichtlichen Weg gibt, das zu implementieren, was ich nicht sehe, würde ich ein Feedback sehr begrüßen.

Answer 1

Für Modulo selbst bin ich mir nicht sicher. Haben Sie für Modulo als Teil der größeren modularen Exponentialoperation Montgomery multiplication nachgeschlagen, wie in der Wikipedia-Seite unter modular exponentiation erwähnt? Es ist eine Weile her, seit ich mich mit dieser Art von Algorithmus beschäftigt habe, aber von dem, was ich weiß, wird es häufig in der schnellen modularen Exponentiation verwendet.

bearbeiten: für was es wert ist, scheint Ihr Modulo-Algorithmus auf den ersten Blick in Ordnung. Sie machen im Grunde Division, die ein wiederholter Subtraktionsalgorithmus ist.

Answer 2

Ich bin nicht sicher, was Sie dort berechnen, um ehrlich zu sein. Sie sprechen über Modulo-Operation, aber normalerweise ist eine Modulo-Operation zwischen zwei Zahlen a und b, und das Ergebnis ist der Rest der Teilung a von b. Wo ist die a und b in Ihrem Pseudocode ...?

Wie auch immer, vielleicht hilft das: a mod b = a - floor(a/b) * b.

Ich weiß nicht, ob das schneller ist oder nicht, es hängt davon ab, ob Sie Division und Multiplikation schneller als viele Subtraktionen tun können.

Eine andere Möglichkeit, den Subtraktionsansatz zu beschleunigen, ist die binäre Suche. Wenn Sie a mod b möchten, müssen Sie b von a subtrahieren, bis a kleiner als b ist. Also im Grunde Sie k so dass finden müssen:

a - k*b < b, k is min

Eine Möglichkeit, dieses k zu finden, ist eine lineare Suche:

k = 0; 
while (a - k*b >= b) 
    ++k; 

return a - k*b; 

Sie können aber auch binäre Such es (lief nur ein paar Tests aber es funktionierte auf allen):

k = 0; 
left = 0, right = a 
while (left < right) 
{ 
    m = (left + right)/2; 
    if (a - m*b >= b) 
     left = m + 1; 
    else 
     right = m; 
} 

return a - left*b; 

Ich vermute, die binäre Suchlösung wird die schnellste sein, wenn Sie handeln mit großen Zahlen.

Wenn Sie a mod b berechnen und nur a ist eine große Zahl (Sie b auf einem primitiven Datentyp speichern kann), können Sie es sogar noch schneller tun:

for each digit p of a do 
    mod = (mod * 10 + p) % b 
return mod 

Dies funktioniert, weil wir a schreiben als a_n*10^n + a_(n-1)*10^(n-1) + ... + a_1*10^0 = (((a_n * 10 + a_(n-1)) * 10 + a_(n-2)) * 10 + ...

Ich denke, die binäre Suche ist, was Sie suchen, obwohl.

Answer 3

Wenn Sie shift-and-add für die Multiplikation verwenden (was auf keinen Fall der schnellste Weg ist), können Sie die Modulo-Operation nach jedem Additionsschritt durchführen. Wenn die Summe größer als der Modul ist, subtrahieren Sie den Modul. Wenn Sie den Überlauf vorhersagen können, können Sie die Addition und Subtraktion gleichzeitig durchführen. Wenn Sie den Modulo bei jedem Schritt ausführen, wird auch die Gesamtgröße Ihres Multiplikators reduziert (die gleiche Länge wie bei der Eingabe, nicht doppelt).

Die Verschiebung des Moduls, die Sie tun, bringt Sie den größten Teil zu einem vollständigen Divisionalgorithmus (modulo nimmt nur den Rest).

EDIT Hier ist meine Implementierung in Python:

 
def mod_mul(a,b,m): 
    result = 0 
    a = a % m 
    b = b % m 
    while (b>0): 
     if (b&1)!=0: 
      result += a 
      if result >= m: result -= m 
     a = a << 1 
     if a>=m: a-= m 
     b = b>>1 
    return result 

Dies ist nur modulare Multiplikation (Ergebnis = a * b mod m). Die Modulo-Operationen an der Spitze werden nicht benötigt, sondern dienen dazu, daran zu erinnern, dass der Algorithmus annimmt, dass a und b kleiner als m sind.

Natürlich haben Sie für die modulare Exponentiation eine äußere Schleife, die diese gesamte Operation bei jedem Schritt durchführt, entweder bei der Quadrierung oder bei der Multiplikation. Aber ich denke du hast das gewusst.

Answer 4

Dieser Test (modulus(n-1) != 1) // ein bisschen Test?

-seems redundant kombiniert mit (modulus<result).

Entwerfen für Hardware-Implementierung Ich wäre mir der kleineren/größer als Tests impliziert mehr Logik (Subtraktion) als bitweise Operationen und Verzweigung auf Null.

Wenn wir leicht bitweise Tests durchführen können, könnte dies schnell sein:

m=msb_of(modulus) 

while(result>0) 
{ 
    r=msb_of(result) //countdown from prev msb onto result 
    shift=r-m  //countdown from r onto modulus or 
        //unroll the small subtraction 

    takeoff=(modulus<<(shift)) //or integrate this into count of shift 

    result=result-takeoff; //necessary subtraction 

    if(shift!=0 && result<0) 
    { result=result+(takeoff>>1); } 

    } //endwhile 

if(result==0) { return result } 
else   { return result+takeoff } 

(Code ungetestet gotchas enthalten kann)

result wird repetively erniedrigt durch modulus bei höchstwertigen Bits übereinstimmen verschoben.

Nach jeder Subtraktion: result hat eine ~ 50/50 Chance, mehr als 1 msb zu verlieren. Es hat auch ~ 50/50 Chance, negativ zu werden, Addition der Hälfte, was subtrahiert wurde, wird es immer wieder in positive setzen. > Sollte es in positive zurückgestellt werden, wenn Verschiebung

Die Arbeits Schleife beendet nicht = 0

war, als result unterschritten und ‚Shift‘ 0

war