Mathe-Lehramt: Zahlentheorie, Restklassen

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...

ggtex erweiterter Euklidischer Algoritmus mit Textausgabe
Programmierung mit MuPAD Die Prozeduren sind dann in dem package zahltheo verborgen.
Mathematik mit MuPAD 3.11, Prof. Dr. Dörte Haftendorn ursprünglich 02 überarbeitet Sept. 05 Version vom 14.9.05
Web: haftendorn.uni-lueneburg.de/mathe-lehramt haftendorn.uni-lueneburg.de/ing-math
Achtung: Menu ->Notebook->Evaluiere->Alle Eingaben
Aufruf: ggtex(a,b)

ggtex:=proc(a,b)
           local r0,r1,r2,q0,s0,s1,s2,t0,t1,t2;
           begin
              r0:=a:  r1:=b: q0:=a div b: s0:=1: s1:=0: t0:=0: t1:=1:
              repeat
                r2:=r0 mod r1:
                if r2=0 then
                  print(Unquoted,"ggT(".a.",".b.")= ".r1.
                  "       VSD  ".r1."= ".s1."*".a."+ (".t1.")*".b);
                  return([r1,s1,t1]);
                end_if;
                q0:= r0 div r1: s2:=s0-q0*s1:  t2:=t0-q0*t1:
                print(Unquoted,
" ".r0."=".q0."*".r1."+".r2." und es ist  VSD  ".r2."= ".s2."*".a."+ (".t2.")*".b);
                r0:=r1:   r1:=r2: s0:=s1:  t0:=t1:  s1:=s2:   t1:=t2:
                /*alle eine Nummer herunterzählen */
              until 3=5 end_repeat;
           end_proc:

gg:=ggtex(676,18)


        676=37*18+10 und es ist  VSD  10= 1*676+ (-37)*18

          18=1*10+8 und es ist  VSD  8= -1*676+ (38)*18

          10=1*8+2 und es ist  VSD  2= 2*676+ (-75)*18

          ggT(676,18)= 2       VSD  2= 2*676+ (-75)*18

Herausgreifen der wichtigen Zahlen

gg[1],gg[2],gg[3]

Untensteht eine Extra-Funktion für ggT.
Ablaufverfolgung um die Prozedur zu entwickeln und zu testen.

delete a,b,r0,r1,r2,q0,q1,s0,s1,s2,t0,t1,t2;
[r0,r1,r2,q0,s0,s1,s2,t0,t1,t2] ;

a:=676:b:=18:

r0:=a: r1:=b: q0:=a div b: s0:=1: s1:=0: t0:=0: t1:=1:
[r0,r1,r2,q0,s0,s1,s2,t0,t1,t2];

---------Marke 1--------------- ab hier wiederholt auswerten --------------------------------------------

r2:=r0 mod r1:
                if r2=0 then
                  print(Unquoted,"ggT(".a.",".b.")= ".r1.
                  "       VSD  ".r1."= ".s1."*".a."+ (".t1.")*".b);
                  return([r1,s1,t1]);
                end_if;


          ggT(676,18)= 2       VSD  2= 2*676+ (-75)*18

Aufhören, wenn hier der hier der ggT erscheint.

q0:= r0 div r1: s2:=s0-q0*s1:  t2:=t0-q0*t1:
                print(Unquoted,
" ".r0."=".q0."*".r1."+".r2." und es ist  VSD  ".r2."= ".s2."*".a."+ (".t2.")*".b);


          10=1*8+2 und es ist  VSD  2= 2*676+ (-75)*18

[r0,r1,r2,q0,s0,s1,s2,t0,t1,t2];

r0:=r1:   r1:=r2: s0:=s1:  t0:=t1:  s1:=s2:   t1:=t2:
[r0,r1,r2,q0,s0,s1,s2,t0,t1,t2];
           /*alle eine Nummer herunterzählen */

-------gehe zu Marke 1 ab hier zurück ---------------------------------------------------

Variante ohne die Textausgabe

ggte:=proc(a: Type::Integer,b:Type::Integer)
           local r0,r1,r2,q0,q1,s0,s1,s2,t0,t1,t2;
           begin
              r0:=a:  r1:=b: q0:=a div b: s0:=1: s1:=0: t0:=0: t1:=1:
              repeat
                r2:=r0 mod r1:
                if r2=0 then
                  return([r1,s1,t1]);
                end_if;
                q0:= r0 div r1: s2:=s0-q0*s1:  t2:=t0-q0*t1:
                  r0:=r1:   r1:=r2: s0:=s1:  t0:=t1:  s1:=s2:   t1:=t2:
                /*alle eine Nummer herunterzählen */
              until 3=5 end_repeat;
           end_proc:

ggte(676,18)

Variante nur ggt

ggt:=proc(a: Type::Integer,b:Type::Integer)
           local r0,r1,r2,q0,q1;
           begin
              r0:=a:  r1:=b:
              repeat
                r2:=r0 mod r1:
                if r2=0 then  return(r1)
                  end_if;
                q0:= r0 div r1:
                q1:= r1 div r2:
                r0:=r1:   r1:=r2: q0:=q1:
                /*alle eine Nummer herunterzählen */
              until r2=0 end_repeat;
           end_proc:

ggt(676,115)

WeitereTests, Vergeich mit eingebauten Funktionen

a:=676: b:= 37: ggt(a,b), gcd(a,b),ggte(a,b), igcdex(a,b);

ggtex(a,b)


        676=18*37+10 und es ist  VSD  10= 1*676+ (-18)*37

          37=3*10+7 und es ist  VSD  7= -3*676+ (55)*37

          10=1*7+3 und es ist  VSD  3= 4*676+ (-73)*37

          7=2*3+1 und es ist  VSD  1= -11*676+ (201)*37

         ggT(676,37)= 1       VSD  1= -11*676+ (201)*37

a:=666: b:= 37: ggt(a,b), gcd(a,b),ggte(a,b), igcdex(a,b),ggtex(a,b);


          ggT(666,37)= 37       VSD  37= 0*666+ (1)*37

Also der größte gemeinsame Teiler ist von MuPAD direkt zu erreichen mit
gcd(a,b) greates common divisor
Der erweiterte Euklidische Algorithmus wird von
igcdex(a,b) integer gcd extended ausgeführt. Ausgegeben wird eine Folge

a:=676:b:=37: ig:=igcdex(a,b)

Probe

-11*676+201*37

ig[1]=ig[2]*a+ig[3]*b // Automatisch

gg:=ggtex(a,b)


        676=18*37+10 und es ist  VSD  10= 1*676+ (-18)*37

          37=3*10+7 und es ist  VSD  7= -3*676+ (55)*37

          10=1*7+3 und es ist  VSD  3= 4*676+ (-73)*37

          7=2*3+1 und es ist  VSD  1= -11*676+ (201)*37

         ggT(676,37)= 1       VSD  1= -11*676+ (201)*37

gg[1]=gg[2]*a+gg[3]*b // Automatisch

[Kryptographie] [Algebra] [MuPAD]

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]