RSA	Nachricht-zu-Zahl modulo-Rechnen modulares Potenzieren Algorithmus von Euklid Euler-Funktion Satz von Euler modulares Inverses Primfaktorzerlegung Primzahlen finden Schlüsselpaar Angriff Sicherheit Pfad: Startseite / Fächer / Informatik / Kryptologie / RSA / modulares Potenzieren
Autor: mk 10.03.2011 15:46 1397	modulares Potenzieren

Schnelles modulares Potenzieren in Python

def modpowerr(b,e,m):
    """
    Rückgabe (b**e)%m , e und m müssen natürliche Zahlen sein
    """
    if e == 0:
        return 1
    else:
        if e%2 == 1:
            return (b*modpowerr((b*b)%m,e//2,m))%m
        else:
            return (modpowerr((b*b)%m,e//2,m))%m

def modpower(b,e,m):
    """
    Rückgabe (b**e)%m , e und m müssen natürliche Zahlen sein
    """
    res = 1
    while e > 0:
        if e%2 == 1:
            res = (res*b)%m
        b = (b*b)%m
        e = e//2
    return res

Diskrete Exponentialfunktion in Delphi

  function modpot(a,e,m : int64) : int64;
  var
    quad, halb, erg : int64;
  begin
    quad := a; halb := e; erg := 1;
    while halb > 0 do
    begin
      if odd(halb) {halb mod 2 > 0} then
        erg := (erg*quad) mod m;
      quad := (quad*quad) mod m;
      halb := halb div 2;
    end;
    result := erg;
  end;

modpotenz.zip modpot_lang.zip ModPot_lang.exe

Links

• Square & Multiply