rekursion unformung

[rekursiv (Gast)]

Hallo,

Ich benötige etwas Hilfe und zwar hätte ich gern die Iterative Umformung 
von. Mir ist klar das ich ne schleife reinbauen muss um den 
Rekursionsaufruf wegzubekommen:

def inv(a, k):
    if k==1:
        return 1
    m=1<<k    # 2**k
    a=a % m
    r=inv(a, (k+1)//2)
    return (2-a*r) * r % m

[Keiner N. (nichtgast)]

Moin,

helfen kann ich dir nicht.

Was macht denn der Algorithmus? Kannst du den Variablen und der Funktion 
mal aussagekräftigere Namen geben?

[rekursion (Gast)]

Die Funktion findet man hier: montgomery-multiplikation - 
http://www.inf.fh-flensburg.de/lang/algorithmen/arithmetik/montgomery-multiplikation.htm

Diese Funktion bildet das Inverse Element zur Berechnung der montgomery 
multiplikation a*b*2^-k % M

[Yalu X. (yalu) (Moderator)]

Bspw. so:

def inv2(a, k):
  k -= 1
  r = 1
  n = k.bit_length()
  while n:
    n -= 1
    m = 2 << (k >> n)
    r = (2 - a * r) * r % m
  return r

Die Zeile

    a=a % m

im Originalcode ist übrigens überflüssig.

[rekursion (Gast)]

Yalu, ich weis garnicht wie ich dir danken kann :)

[Yalu X. (yalu) (Moderator)]

Die rekursive Lösung ist IMHO dennoch die elegantere, und ich hatte
einige Mühe, den nichtrekursiven Algorithmus so hinzubiegen, dass er
ähnlich effizient wie der rekursive ist. Auch der Stackverbrauch ist
hier kaum ein Argument gegen die Rekursion, da er nur mit log2(k) bzw.
log2(log2(m)) wächst, angesichts des Speicherverbrauchs von m also
vernachlässigbar ist.

[rekursion (Gast)]

Vielen Dank Yalu. Für mich ist es nur in der Iterativen Form möglich den 
Algorithmus in Verilog zu übertragen.

[Arc N. (arc)]

Falls es um Krypto geht, dann sollte man sich u.U. ein paar Paper dazu 
ansehen (u.a. auch auf Wikipedia verlinkt), die auch die 
Seitenkanalresistenz und Fehlersicherheit betrachten u.a.:

The Montgomery Powering Ladder
https://cr.yp.to/bib/2003/joye-ladder.pdf

Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR 
Microcontrollers
http://www.caad.arch.ethz.ch/noolab/files/external/conferences/IoT2010_proceedings/pdf/WS1/WS1_6.%20seciot2010_submission_12_final_v0.pdf#page=8

[Hans (Gast)]

Siehe auch hier:
http://www.inf.fh-flensburg.de/lang/zahlentheorie/hensel-lifting.htm