Kryptographie URL haftendorn.uni-lueneburg.de/mathe-lehramt/krypto/krypto.htm

[Kryptographie]  [Algebra]  [MuPAD]   © Prof. Dr. Dörte Haftendorn

Download des MuPAD-Notebooks     Save Link Taget As..., Ziel speichern unter... Powermod: Programmierung von pmod(a,b,m)
Mathematik mit MuPAD 3.11, Prof. Dr. Dörte Haftendorn Sept. 05
Web: haftendorn.uni-lueneburg.de/mathe-lehramt haftendorn.uni-lueneburg.de/ing-math
Achtung: Menu ->Notebook->Evaluiere->Alle Eingaben

Der wichtigste Term der Kryptographie ist
Dabei sind alle drei Variablen riesige Zahlen mit einer Dezimalen Stellenlänge weit über 100.
Aber auch schon im bescheidenen Rahmen einer Berechung mit 3-stelligen Zahlen in der Lehre
kann man (ohne großes CAS) nicht einfach die Potenz ausrechnen und dann den modularen Rest bestimmen:

• pot:=109^47

• pot mod 211

Alle großen CAS haben dafür den Befehl powermod(a,b,m) (in irgeneiner Syntax), bei dem
mit geschickten Zwischenrechnungen immer sofort modular "heruntergebrochen" wird.
Kleinen CAS, insbesondere CAS-Taschenrechnern wie dem TI-voyage, fehlt diese Fkt.
Die unten entwickelte Prozedur kann -unter Beachtung kleiner Sytaxanpassungen- sofort
auf den TI-voyage (oder TI92 ) übertragen werden. download der TI-Datei ist möglich.

Grundidee Es werden nacheinander "Potenztürme" gebaut:
Bei der Entscheidung, ob ein solcher Turm als Faktor zum
Aufbau von benötigt wird hilft die Dualdarstellung des Exponenten b.
Zum Beispiel b=11. Dann ist und .
Nun braucht man aber diese Dualdarstellung nicht explizit zu erzeugen, sondern man
nutzt die "Doublel-Daddel-Methode" statt zum Erzeugen der Dualzahl gleich zu Erzeugen der Potenz.

"Doublel-Daddel-Methode" zum Erzeugen der Dualzahl ---->Extraseite

Programmierung von pmod(a,k,m) #######################

• pmod:=proc(a: Type::Rational,k: Type::Integer,m: Type::Integer)
          local x,kk,pot;
          begin 
            kk:=k; x:=1: pot:=a:
            if k<0 then kk:=-k: pot:=1/a: end_if;
            //Abfangen negativer Exponenten
              if k=0  then 
                     if a<>0 then return(1);
                     elif a=0 then  return ("unbestimmt");  
                     end_if;
               end_if;
            //Abfangen von a^0 und 0^0
          repeat
            if kk mod 2 =1 then
               x:= x*pot mod m ;
               if kk=1 then return(x); end_if;
               kk:=kk-1; //hiernach ist k gerade
             end_if;
             kk:= kk/2;   //immer möglich
             pot:= pot*pot mod m;
          until 3=5 end_repeat;
        end_proc:
               

• pmod(27,5,31);
  powermod(27,5,31);  // MuPAD-Funktion

Die folgende Matrix zeigt, dass das eigene pmod und das eingebaute powermod
für einige positive Eingaben identische Werte liefern.

• matrix([[[pmod(a,k,31),powermod(a,k,31)] $ k=25..31]
                                           $ a=27..30]);

Übrigens kann man an dieser Liste schon sehen, dass bei Potenzen im Modul
allerlei Besonderheiten auftauchen, die man erkunden kann.
Siehe Extraseite zu Potenzen.

Tests zu Sonderfällen ##############################

• powermod(2,0,7);
  pmod(2,0,7);

• powermod(0,0,7);
  pmod(0,0,7);

Na, da ist das eigene pmod sogar besser!

Als Basis können rationale Zahlen genommen werden,
denn der mod-Befehl von MuPAD kann diese verarbeiten.

• pmod(15/13,1,17)

• 15/13 mod 17

Probe

• i13:=(1/13 mod 17);
  i13*13 mod 17;
  (15*i13)*13 mod 17;

Auch negative Basen können genommen werden.

• -3 mod 11;
  pmod(-3,5,11);
  powermod(-3,5,11);
  

Beide Funktionen verarbeiten auch negative Exponenten,

• powermod(2,-3,11);
  pmod(2,-3,11);

• 7*2^3 mod 11   //Probe

[Kryptographie]  [Algebra]  [MuPAD]

Inhalt und Webbetreuung ©Prof. Dr. Dörte Haftendorn 2001, hier neu 2005, update 17. September 2005

Direkte Internetadressen [www.doerte-haftendorn.de] [haftendorn.uni-lueneburg.de/mathe-lehramt]    [haftendorn.uni-lueneburg.de/ing-math]