Mathe-Lehramt: Zahlentheorie, ggt, und andere Funktionen

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

Teiler, ggT, kgV, Primzahlen und so weiter
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
Gliederung:
1. ggt, kgv, Vielfachsummen und erweiterter Euklidischer Algorithmus ##################
2. Primzahlen, Primfaktorzerlegung ##################
3. Teiler, Vielfache ##################
4. Menge Z*(n) der zu n teilerfemden (relativ primen) Zahlen ##################
---------------------------------------eigene Zahlentheorie Ergänzungen---------------------------------------------

delete PACKAGEPATH:endml:=strmatch(NOTEBOOKPATH,"mathe-lehramt", Index)[2]:
gesamtpackpfad:=substring(NOTEBOOKPATH,1..endml+1).pathname("computer","mupad", "packages"):
PACKAGEPATH:=gesamtpackpfad,PACKAGEPATH://Tipps zu Packages siehe unten auf der Seite.

package("zahltheo", Forced):zahltheo::init():export(zahltheo):

---------------------------------------eigene Zahlentheorie Ergänzungen---------------------------------------------
1. ggt, kgv, Vielfachsummen und erweiterter Euklidischer Algorithmus ###

gcd(12,18); ggt(12,18); // (greatest common divisor)

lcm(12,18) //kgV(a,b) (lowest common mnultiple)

hold(gcd(12,18)*lcm(12,18))=hold(12*18);//beispiel für einen allg. Satz.
gcd(12,18)*lcm(12,18) =12*18;

In ser Kryptographie spielt die Vielfachsummen-Darstellung VSD eine besondere Rolle.
Dabei soll der größte gemeinsame Teiler von a und b als Summe von Vielfachen von a und b geschrieben werden.
ggt(a,b) = s * a + t * b
Man kann die VSD auch als Linearkombination von a und b ansehen.
Man erhält sie mit dem erweiterten Eukidischen Algorithmus:

igcdex(160,111); ggte(160,111) //Erweiterter Euklidischer Algorithmus

Die Funktion igcd(a,b) gibt den ggt, s,t als Folge aus,
Die Funktion ggte(a,b) gibt den ggt, s,t als Liste aus,
ggte ist ebenso wie ggt und ggtex in dem eigenen package zahltheo vorhanden.
Es gibt Extraseiten, die die Programmierung genau zeigen.

ggtex(160,111);


          160=1*111+49 und es ist  VSD  49= 1*160+ (-1)*111

          111=2*49+13 und es ist  VSD  13= -2*160+ (3)*111

          49=3*13+10 und es ist  VSD  10= 7*160+ (-10)*111

           13=1*10+3 und es ist  VSD  3= -9*160+ (13)*111

           10=3*3+1 und es ist  VSD  1= 34*160+ (-49)*111

          ggT(160,111)= 1       VSD  1= 34*160+ (-49)*111

Probe

34*160 + (-49)*111

2. Primzahlen, Primfaktorzerlegung ##############################

isprime(100003)

isprime(100007)

Primfaktorzerlegung

ifactor(100007)

ifactor(250348)

Probe

hold(2^2*7*8941)=2^2*7*8941

Erzeugung von Primzahllisten

primzahlen:=[]:

if isprime(i)then primzahlen:=primzahlen.[i] end_if $ i=2..500:
primzahlen;


[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,

   61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,

   131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,

   197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,

   271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,

   353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,

   433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499]

primzahlen:=[]:
if isprime(i)then primzahlen:=primzahlen.[i] end_if
$ i=2000..2400:
primzahlen;


[2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083,

   2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143,

   2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,

   2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311,

   2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383,

   2389, 2393, 2399]

numlib::proveprime(37777777777777777777777777777)

Dies Funktion proveprime arbeitet sicherer als isprime, siehe MuPAD-Hilfe

nextprime(37777777777777777777777777777)

numlib::prevprime(37777777777777777777777777777)

numlib::primedivisors(37777777777777777777777777777)

3. Teiler, Vielfache ####################################
Teilermenge

numlib::divisors(15); teiler(15);

Bei der eigenen Prozedur teiler (verwendet auch im TI92/Voyage) kann man die
Teilerpaare sehen.

teiler(24)

numlib::divisors(24)

numlib::primedivisors(24)

Hier sind nur die Primteiler ausgegeben.
Vielfachenfolge

i*7 $ i=1..15

etwas edler:

[i,i*7] $ i=1..10

noch edler das Einmaleins

delete a:

matrix([[i*a=i*k $ k=5..10] $i=1..10])

Die Teilerfremden:
Zwei Zahlen a und b heißen teilerfremd, wenn ihr ggt(a,b)=1 ist.

liste:=[]:   n:=27:
           for i from 1 to n  do
              if gcd(n,i)=1 then liste:=liste.[i]
              end_if:
           end_for:
liste

Diese Befehleszeilen sammeln einfach alle Teilerfremden auf. Sie sind in der Funktion
zstern(n) zusammengefasst, da man diese Menge stets Z*(n) nennt.

zstern(27);

Die Anzahl der Teilerfremden von n heißt Eulersches Phi(n).
Diese Anzahl erhält man leicht durch die Elemente-Zählfunktion nops(objekt)
oder durch die vorhandene Funktion numlib::phi(n);

numlib::phi(27);
nops(zstern(27));

Weiteres aus dem Tutorium
Hilfe --> Hilfe öffnen --->Turorium --->Gehe--->zu Seite ->> 40
_____________________________________________________________
Tipps zu Packages:

gesamtpackpfad

Unter Ansicht->Optionen->Kern können Sie in der Zeile Packages diesen String (ohne die "") eintragen
oder inteaktiv dort das Entsprechende auswählen. Nach dem erneuten Öffnen von MuPAD behält das
System diesen Pfad und Sie können den obigen winzig gedruckten Teil mit Voranstellen von // deaktivieren.

[Kryptographie] [Algebra] [MuPAD]

Inhalt und Webbetreuung ©Prof. Dr. Dörte Haftendorn 2001, hier neu 2005, update 14. August 2011

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