[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

21. Zahlentheorie


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

21.1 Funktionen und Variablen der Zahlentheorie

Funktion: bern (n)

Gibt die n-te Bernoulli-Zahl der ganzen Zahl n zurück. Hat die Optionsvariable zerobern den Wert false, werden Bernoulli-Zahlen unterdrückt, die Null sind.

Siehe auch burn.

(%i1) zerobern: true$
(%i2) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
                  1  1       1      1        1
(%o2)       [1, - -, -, 0, - --, 0, --, 0, - --]
                  2  6       30     42       30
(%i3) zerobern: false$
(%i4) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
            1  1    1   5     691   7    3617  43867
(%o4) [1, - -, -, - --, --, - ----, -, - ----, -----]
            2  6    30  66    2730  6    510    798

Funktion: bernpoly (x, n)

Gibt das n-te Bernoulli-Polynom in der Variablen x zurück.

Function: bfzeta (s, n)

Die Riemannsche Zeta-Funktion für das Argument s, die wie folgt definiert ist:

                 inf
                 ====
                 \     1
     zeta(s) =    >    --
                 /      s
                 ====  k
                 k = 1

bfzeta gibt einen Wert als große Gleitkommazahl zurück. Die Anzahl der Stellen wird durch das Argument n angegeben.

Anstatt der Funktion bfzeta ist die Funktion zeta zu bevorzugen, die sowohl für reelle und komplexe Gleitkommazahlen und Gleitkommazahlen mit eine beliebigen Genauigkeit die Riemannsche Zeta-Funktion berechnen kann.

Funktion: bfhzeta (s, h, n)

Die Hurwitzsche Zeta-Funktion für die Argumente s und h, die wie folgt definiert ist:

                        inf
                        ====
                        \        1
         zeta (s,h)  =   >    --------
                        /            s
                        ====  (k + h)
                        k = 0

bfhzeta gibt einen Wert als große Gleitkommazahl zurück. Die Anzahl der Stellen wird durch das Argument n angegeben.

Funktion: burn (n)

Gibt eine rational Zahl zurück, die eine Näherung für die n-te Bernoulli Zahl für die ganze Zahl n ist. burn berechnet eine Näherung als große Gleitkommatzahl mit der folgenden Beziehung:

                   n - 1  1 - 2 n
              (- 1)      2        zeta(2 n) (2 n)!
     B(2 n) = ------------------------------------
                                2 n
                             %pi

burn kann effizienter als die Funktion bern für große, einzelne ganze Zahlen n sein, da bern zunächst alle Bernoulli Zahlen bis n berechnet. burn ruft für ungerade ganze Zahlen und Zahlen die kleiner oder gleich 255 die Funktion bern auf.

Das Kommando load(bffac) lädt die Funktion. Siehe auch bern.

Funktion: chinese ([r_1, …, r_n], [m_1, …, m_n])

Löst die simultanen Kongruenzen x = r_1 mod m_1, …, x = r_n mod m_n. Die Reste r_n und die Moduli m_n müssen ganze Zahlen sein, die Moduli zusätzlich positiv und paarweise teilerfremd.

(%i1) mods : [1000, 1001, 1003, 1007];
(%o1)                   [1000, 1001, 1003, 1007]
(%i2) lreduce('gcd, mods);
(%o2)                               1
(%i3) x : random(apply("*", mods));
(%o3)                         685124877004
(%i4) rems : map(lambda([z], mod(x, z)), mods);
(%o4)                       [4, 568, 54, 624]
(%i5) chinese(rems, mods);
(%o5)                         685124877004
(%i6) chinese([1, 2], [3, n]);
(%o6)                    chinese([1, 2], [3, n])
(%i7) %, n = 4;
(%o7)                              10

Funktion: divsum (n, k)
Funktion: divsum (n)

divsum(n, k) potenziert die Teiler des Argumentes n mit dem Argument k und gibt die Summe als Ergebnis zurück.

divsum(n) gibt die Summe der Teiler der Zahl n zurück.

(%i1) divsum (12);
(%o1)                          28
(%i2) 1 + 2 + 3 + 4 + 6 + 12;
(%o2)                          28
(%i3) divsum (12, 2);
(%o3)                          210
(%i4) 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2;
(%o4)                          210

Funktion: euler (n)

Gibt die n-te Eulersche Zahl für eine nichtnegative ganze Zahl n zurück.

Für die Euler-Mascheroni Konstante siehe %gamma.

Beispiele:

(%i1) map (euler, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
(%o1)    [1, 0, - 1, 0, 5, 0, - 61, 0, 1385, 0, - 50521]

Funktion: fib (n)

Gibt die n-te Fibonacci-Zahl zurück. Die Fibonacci-Folge ist rekursiv definiert:

   fib(0) = 0
   fib(1) = 1
   fib(n) = fib(n-1) + fib(n-2)

Für negative ganze Zahlen kann die Fibonacci-Folge erweitert wird mit:

                   n + 1
   fib(- n) = (- 1)      f(n)

Nach einem Aufruf der Funktion fib(n), enthält die Systemvariable prevfib die zur Zahl n vorhergehende Fibonacci-Zahl.

(%i1) map (fib, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
(%o1)         [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Funktion: fibtophi (expr)

Fibonacci-Zahlen im Ausdruck expr werden durch die Goldene Zahl %phi ausgedrückt. Siehe %phi.

Beispiele:

(%i1) fibtophi (fib (n));
                           n             n
                       %phi  - (1 - %phi)
(%o1)                  -------------------
                           2 %phi - 1
(%i2) fib (n-1) + fib (n) - fib (n+1);
(%o2)          - fib(n + 1) + fib(n) + fib(n - 1)
(%i3) fibtophi (%);
            n + 1             n + 1       n             n
        %phi      - (1 - %phi)        %phi  - (1 - %phi)
(%o3) - --------------------------- + -------------------
                2 %phi - 1                2 %phi - 1
                                          n - 1             n - 1
                                      %phi      - (1 - %phi)
                                    + ---------------------------
                                              2 %phi - 1
(%i4) ratsimp (%);
(%o4)                           0

Funktion: ifactors (n)

Faktorisiert eine positive ganze Zahl n. Sind n = p1^e1 * ... * pk^nk die Faktoren der ganzen Zahl n, dann gibt ifactor das Ergebnis [[p1, e1], ..., [pk, ek]] zurück.

Für die Faktorisierung kommen Probedivisionen mit Primzahlen bis 9973, Pollards Rho- und p-1-Methode oder Elliptischen Kurven zum Einsatz.

Die Rückgabe von ifactors wird von der Optionsvariablen @ref{factors_only}.

beeinflusst. Werden lediglich die Primfaktoren ohne ihre Multiplizität benötigt, genügt es hierfür, factors_only : true zu setzen.

(%i1) ifactors(51575319651600);
(%o1)     [[2, 4], [3, 2], [5, 2], [1583, 1], [9050207, 1]]
(%i2) apply("*", map(lambda([u], u[1]^u[2]), %));
(%o2)                        51575319651600
(%i3) ifactors(51575319651600), factors_only : true;
(%o3)                   [2, 3, 5, 1583, 9050207]

Funktion: igcdex (n, k)

Gibt die Liste [a, b, u] zurück, in der u der größte gemeinsame Teiler von n und k ist und in der zusätzlich gilt, dass u = a * n + b * k.

igcdex verwendet den Euklidischen Algorithmus. Siehe auch gcdex. .

Die Eingabe load(gcdex) lädt diese Funktion.

Beispiele:

(%i1) load(gcdex)$

(%i2) igcdex(30, 18);
(%o2)                      [- 1, 2, 6]
(%i3) igcdex(1526757668, 7835626735736);
(%o3)            [845922341123, - 164826435, 4]
(%i4) igcdex(fib(20), fib(21));
(%o4)                   [4181, - 2584, 1]

Funktion: inrt (x, n)

Gibt die ganzzahlige n-te Wurzel des Betrags von x zurück.

(%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
(%i2) map (lambda ([a], inrt (10^a, 3)), l);
(%o2) [2, 4, 10, 21, 46, 100, 215, 464, 1000, 2154, 4641, 10000]

Funktion: inv_mod (n, m)

Berechnet das modulare Inverse von n zum Modul m. Das Argument n muss eine ganze Zahl und der Modul p eine positive ganze Zahl sein. inv_mod(n, m) gibt false zurück, wenn das modulare Inverse nicht existiert. Das modulare Inverse existiert, wenn n teilerfremd zum Modul m ist.

Siehe auch die Funktionen power_mod und mod.

Beispiele:

(%i1) inv_mod(3, 41);
(%o1)                           14
(%i2) ratsimp(3^-1), modulus = 41;
(%o2)                           14
(%i3) inv_mod(3, 42);
(%o3)                          false

Funktion: isqrt (x)

Gibt die ganzzahlige Wurzel des Betrages von x zurück, wenn x eine ganze Zahl ist. Andernfalls wird eine Substantivform zurückgegeben.

Funktion: jacobi (p, q)

Berechnet das Jacobi-Symbol für die Argumente p und q.

(%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
(%i2) map (lambda ([a], jacobi (a, 9)), l);
(%o2)         [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]

Funktion: lcm (expr_1, …, expr_n)

Gibt das kleinste gemeinsame Vielfache der Argumente zurück. Die Argumente können ganze Zahlen und allgemeine Ausdrücke sein.

Mit dem Kommando load(functs) wird die Funktion geladen.

Funktion: mod (x, p)

Berechnet den Divisionsrest x mod y des Arguments x zum Modul y. x und y können ganze Zahlen, rationale Zahlen, Gleitkommazahlen oder allgemeine Ausdrücke sein.

Sind x und y reelle Zahlen und ist y ungleich Null, gibt mod(x, y) das Ergebnis von x - y * floor(x / y) zurück. Weiterhin gilt für alle reellen Zahlen mod(x, 0) = x. Für eine Diskussion dieser Definition siehe Kapitel 3.4, "Concrete Mathematics" von Graham, Knuth, and Patashnik. Die Funktion mod(x, 1) ist eine Sägezahnfunktion mit der Periode 1 mit mod(1, 1) = 0 und mod(0, 1) = 0.

Der Hauptwert einer komplexen Zahl, die im Intervall (-%pi, %pi) liegt, kann mit %pi - mod(%pi - x, 2*%pi) bestimmt werden, wobei x die komplexe Zahl ist.

Sind x und y konstante Ausdrücke, wie zum Beispiel 10 * %pi, verwendet mod dasselbe bfloat. -Auswertungsschema wie floor und ceiling. Diese Umwandlung kann, wenn auch unwahrscheinlich, zu Fehlern führen.

Für nicht numerische Argumente x oder y kennt mod verschiedene Vereinfachungen.

Siehe auch die Funktionen power_mod und inv_mod.

Beispiele:

Zeige für zwei große ganze Zahlen, dass für das modulare Rechnen die Regel mod(a+b, m) = mod(mod(a, m) + mod(b, m), m) gilt.

(%i1) a : random(10^20) + 10^19;
(%o1)                 72588919020045581148
(%i2) b : random(10^20) + 10^19;
(%o2)                 35463666253140008825
(%i3) m : random(10^20) + 10^19;
(%o3)                 39127433614020247557
(%i4) mod(a+b, m);
(%o4)                 29797718045145094859
(%i5) mod(mod(a, m) + mod(b, m), m);
(%o5)                 29797718045145094859

Vereinfachung für nicht numerische Argumente.

(%i1) mod (x, 0);
(%o1)                           x
(%i2) mod (a*x, a*y);
(%o2)                      a mod(x, y)
(%i3) mod (0, x);
(%o3)                           0

Funktion: next_prime (n)

Gibt die kleinste Primzahl zurück, die der Zahl n folgt.

(%i1) next_prime(27);
(%o1)                       29

Funktion: power_mod (a, n, m)

Verwendet einen modularen Algorithmus, um a^n mod m zu berechnen. Die Argumente a und n müssen ganze Zahlen und der Modul m eine positive ganze Zahl sein. Ist n negativ, wird inv_mod

zur Berechnung des modularen Inversen aufgerufen.

power_mod (a, n, m) ist äquivalent zu mod(a^n, m). Der Algorithmus von power_mod ist jedoch insbesondere für große ganze Zahlen wesentlich effizienter.

Siehe auch die Funktionen inv_mod und mod.

Beispiele:

power_mod(a, n, m) ist äquivalent zu mod(a^n, m. Das modulare Inverse wird mit der Funktion inv_mod berechnet.

(%i1) power_mod(3, 15, 5);
(%o1)                          2
(%i2) mod(3^15, 5);
(%o2)                          2
(%i3) power_mod(2, -1, 5);
(%o3)                          3
(%i4) inv_mod(2, 5);
(%o4)                          3

Für große ganze Zahlen ist power_mod effizienter. Der folgende Wert kann in keiner vernünftigen Zeit mit mod(a^n, m) berechnet werden.

(%i1) power_mod(123456789, 123456789, 987654321);
(%o1)                       598987215

Funktion: primep (n)

Führt einen Primzahltest für das Argument n durch. Liefert primep das Ergebnis false, ist n keine Primzahl. Ist das Ergebnis true, ist n mit sehr großer Wahrscheinlichkeit eine Primzahl.

Für ganze Zahlen n kleiner als 341550071728321 wird eine deterministische Variante des Miller-Rabin-Tests angewandt. Hat in diesem Fall primep den Wert true, dann ist n mit Sicherheit eine Primzahl.

Für ganze Zahlen n größer 341550071728321 führt primep primep_number_of_tests Pseudo-Primzahl-Tests nach Miller-Rabin und einen Pseudo-Primzahl-Test nach Lucas durch. Die Wahrscheinlichkeit, dass eine zusammen gesetzte Zahl n einen Miller-Rabin-Test besteht, ist kleiner als 1/4. Mit dem Standardwert 25 primpe_number_of_tests sinkt diese Wahrscheinlichkeit damit unter einen Wert von 10^-15.

Optionsvariable: primep_number_of_tests

Standardwert: 25

Die Anzahl der Pseudo-Primzahl-Tests nach Miller-Rabin in der Funktion primep. .

Funktion: prev_prime (n)

Gibt die größte Primzahl zurück, die kleiner als die Zahl n ist.

(%i1) prev_prime(27);
(%o1)                       23

Funktion: qunit (n)

Findet für das Argument n Lösungen der Pellschen Gleichung a^2 - n b^2 = 1.

(%i1) qunit (17);
(%o1)                     sqrt(17) + 4
(%i2) expand (% * (sqrt(17) - 4));
(%o2)                           1

Funktion: totient (n)

Gibt die Anzahl der ganzen Zahlen zurück, die kleiner oder gleich n und teilerfremd zu n sind.

Optionsvariable: zerobern

Standardwert: true

Hat zerobern den Wert false, werden von den Funktionen bern diejenigen Bernoulli-Zahlen und von euler diejenigen Euler-Zahlen ausgeschlossen, die gleich Null sind. Siehe bern und euler.

Funktion: zeta (n)

Die Riemannsche Zeta-Funktion für s, die wie folgt definiert ist:

                 inf
                 ====
                 \     1
     zeta(s) =    >    --
                 /      s
                 ====  k
                 k = 1

Für negative ganze Zahlen n, Null und positive gerade ganze Zahlen wird zeta zu einem exakten Ergebnis vereinfacht. Damit diese Vereinfachung für positive ganze Zahlen ausgeführt wird, muss die Optionsvariable zeta%pi den Wert true haben. Siehe zeta%pi. . Für einfache und beliebig genaue Gleitkommazahlen (Typ bfloat) hat zeta ein numerisches Ergebnis. Für alle anderen Argumente einschließlich der komplexen und rationalen Zahlen gibt zeta eine Substantivform zurück. Hat die Optionsvariable zeta%pi den Wert false, gibt zeta auch für gerade ganze Zahlen eine Substantivform zurück.

zeta(1) ist nicht definiert. Maxima kennt jedoch die einseitigen Grenzwerte limit(zeta(x), x, 1, plus und limit(zeta(x), x, 1, minus.

Die Riemannsche Zeta-Funktion wird auf die Argumente von Listen, Matrizen und Gleichungen angewendet, wenn die Optionsvariable distribute_over den Wert true hat.

Siehe auch bfzeta und zeta%pi.

Beispiele:

(%i1) zeta([-2,-1,0,0.5,2,3,1+%i]);
                                             2
            1     1                       %pi
(%o1) [0, - --, - -, - 1.460354508809586, ----, zeta(3), 
            12    2                        6
                                                    zeta(%i + 1)]
(%i2) limit(zeta(x),x,1,plus);
(%o2)                          inf
(%i3) limit(zeta(x),x,1,minus);
(%o3)                         minf

Optionsvariable: zeta%pi

Standardwert: true

Hat zeta%pi den Wert true, vereinfacht die Funktion zeta(n) für gerade ganzen Zahlen n zu einem Ergebnis, das proportional zu %pi^n ist. Ansonsten ist das Ergebnis von zeta eine Substantivform für gerade ganze Zahlen.

Beispiele:

(%i1) zeta%pi: true$
(%i2) zeta (4);
                                 4
                              %pi
(%o2)                         ----
                               90
(%i3) zeta%pi: false$
(%i4) zeta (4);
(%o4)                        zeta(4)

Funktion: zn_log (a, g, n)
Funktion: zn_log (a, g, n, [[p1, e1], …, [pk, ek]])

Berechnet den diskreten Logarithmus. Sei (Z/nZ)* eine zyklische Gruppe, g eine Primitivwurzel modulo n und a ein Element dieser Gruppe. Dann berechnet zn_log (a, g, n) eine Lösung der Kongruenz g^x = a mod n.

Der verwendete Algorithmus benötigt die Primfaktorzerlegung des Totienten von n. Da diese Berechnung ebenfalls zeitaufwändig ist, kann es eventuell sinnvoll sein, die Primfaktoren des Totienten vorab zu berechnen und zn_log als viertes Argument zu übergeben. Die Form muss dabei der Rückgabe von ifactors(totient(n)) mit der Standardeinstellung false der Optionsvariable factors_only entsprechen.

Als Algorithmus wird die Pohlig-Hellman-Reduktion und das Rho-Verfahren von Pollard für den diskreten Logarithmus verwendet. Die Laufzeit von zn_log hängt im Wesentlichen von der Bitlänge des größten Primfaktors des Totienten von n ab.

Siehe auch zn_primroot , zn_order , ifactors , totient .

Beispiele:

zn_log (a, g, n) findet eine Lösung der Kongruenz g^x = a mod n.

(%i1) n : 22$
(%i2) g : zn_primroot(n);
(%o2)                               7
(%i3) ord_7 : zn_order(7, n);
(%o3)                              10
(%i4) powers_7 : makelist(power_mod(g, x, n), x, 0, ord_7 - 1);
(%o4)              [1, 7, 5, 13, 3, 21, 15, 17, 9, 19]
(%i5) zn_log(21, g, n);
(%o5)                               5
(%i6) map(lambda([x], zn_log(x, g, n)), powers_7);
(%o6)                [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Das optionale vierte Argument muss der Rückgabe von ifactors(totient(n)) entsprechen. Die Laufzeit hängt im Wesentlichen von der Bitlänge des größten Primfaktors des Totienten ab.

(%i1) (p : 2^127-1, primep(p));
(%o1)                             true
(%i2) ifs : ifactors(p - 1)$
(%i3) g : zn_primroot(p, ifs);
(%o3)                              43
(%i4) a : power_mod(g, 1234567890, p)$
(%i5) zn_log(a, g, p, ifs);
(%o5)                          1234567890
(%i6) time(%o5);  
(%o6)                            [1.204]
(%i7) f_max : last(ifs);
(%o7)                       [77158673929, 1]
(%i8) slength( printf(false, "~b", f_max[1]) );
(%o8)                              37

Funktion: zn_order (x, n)
Funktion: zn_order (x, n, [[p1, e1], …, [pk, ek]])

Ist x eine Einheit in der endlichen Gruppe (Z/nZ)*, so berechnet zn_order die Ordnung dieses Elements. Andernfalls gibt zn_order false zurück. x ist eine Einheit modulo n, falls x teilerfremd zu n ist.

Der verwendete Algorithmus benötigt die Primfaktorzerlegung des Totienten von n. Da diese Berechnung manchmal recht zeitaufwändig ist, kann es eventuell sinnvoll sein, die Primfaktoren des Totienten vorab zu berechnen und zn_order als drittes Argument zu übergeben. Die Form muss dabei der Rückgabe von ifactors(totient(n)) mit der Standardeinstellung false der Optionsvariable factors_only entsprechen.

Siehe auch zn_primroot , ifactors , totient .

Beispiele:

zn_order berechnet die Ordnung einer Einheit x aus (Z/nZ)*.

(%i1) n : 22$
(%i2) g : zn_primroot(n);
(%o2)                               7
(%i3) units_22 : sublist(makelist(i,i,1,21), lambda([x], gcd(x, n) = 1));
(%o3)              [1, 3, 5, 7, 9, 13, 15, 17, 19, 21]
(%i4) (ord_7 : zn_order(7, n)) = totient(n);
(%o4)                            10 = 10
(%i5) powers_7 : makelist(power_mod(g,i,n), i,0,ord_7 - 1);
(%o5)              [1, 7, 5, 13, 3, 21, 15, 17, 9, 19]
(%i6) map(lambda([x], zn_order(x, n)), powers_7);
(%o6)              [1, 10, 5, 10, 5, 2, 5, 10, 5, 10]
(%i7) map(lambda([x], ord_7/gcd(x, ord_7)), makelist(i, i,0,ord_7 - 1));
(%o7)              [1, 10, 5, 10, 5, 2, 5, 10, 5, 10]
(%i8) totient(totient(n));
(%o8)                               4

Das optionale dritte Argument muss der Rückgabe von ifactors(totient(n)) entsprechen.

(%i1) (p : 2^142 + 217, primep(p));
(%o1)                             true
(%i2) ifs : ifactors( totient(p) )$
(%i3) g : zn_primroot(p, ifs);
(%o3)                               3
(%i4) is( (ord_3 : zn_order(g, p, ifs)) = totient(p) );
(%o4)                             true
(%i5) map(lambda([x], ord_3/zn_order(x, p, ifs)), makelist(i,i,2,15));
(%o5)        [22, 1, 44, 10, 5, 2, 22, 2, 8, 2, 1, 1, 20, 1]

Funktion: zn_primroot (n)
Funktion: zn_primroot (n, [[p1, e1], …, [pk, ek]])

Ist die multiplikative Gruppe (Z/nZ)* zyklisch, berechnet zn_primroot die kleinste Primitivwurzel modulo n. Dies ist der Fall, wenn n gleich 2, 4, p^k oder 2*p^k ist, wobei p prim und grösser 2 und k eine natürliche Zahl ist. zn_primroot führt einen entsprechenden Prätest durch, wenn die Optionsvariable zn_primroot_pretest (Standardwert: false) true gesetzt wurde. In jedem Fall wird die Suche durch die obere Schranke zn_primroot_limit begrenzt.

Ist (Z/nZ)* nicht zyklisch oder kann bis zn_primroot_limit keine Primitivwurzel modulo n gefunden werden, gibt zn_primroot false zurück.

Der verwendete Algorithmus benötigt die Primfaktorzerlegung des Totienten von n. Diese Berechnung kann zeitaufwändig sein und es kann daher eventuell sinnvoll sein, die Primfaktoren des Totienten vorab zu berechnen und zn_primroot als zusätzliches Argument zu übergeben. Die Form muss dabei der Rückgabe von ifactors(totient(n)) mit der Standardeinstellung false der Optionsvariable factors_only entsprechen.

Siehe auch zn_primroot_p , zn_order , ifactors , totient .

Beispiele:

zn_primroot berechnet die kleinste Primitivwurzel modulo n oder gibt false zurück.

(%i1) n : 14$
(%i2) g : zn_primroot(n);
(%o2)                               3
(%i3) zn_order(g, n) = totient(n);
(%o3)                             6 = 6
(%i4) n : 15$
(%i5) zn_primroot(n);
(%o5)                             false

Das optionale zweite Argument muss der Rückgabe von ifactors(totient(n)) entsprechen.

(%i1) (p : 2^142 + 217, primep(p));
(%o1)                             true
(%i2) ifs : ifactors( totient(p) )$
(%i3) g : zn_primroot(p, ifs);
(%o3)                               3
(%i4) [time(%o2), time(%o3)];
(%o4)                    [[15.556972], [0.004]]
(%i5) is(zn_order(g, p, ifs) = p - 1);
(%o5)                             true
(%i6) n : 2^142 + 216$
(%i7) ifs : ifactors(totient(n))$
(%i8) zn_primroot(n, ifs), 
      zn_primroot_limit : 200, zn_primroot_verbose : true;
`zn_primroot' stopped at zn_primroot_limit = 200
(%o8)                             false

Optionsvariable: zn_primroot_limit

Standardwert: 1000

Definiert die obere Schranke für die Suche von zn_primroot. nach einer Primitivwurzel. Wurde die Optionsvariable zn_primroot_verbose.

(Standardwert: false) true gesetzt, wird beim Erreichen von zn_primroot_limit ein entsprechender Hinweis ausgegeben.

Funktion: zn_primroot_p (x, n)
Funktion: zn_primroot_p (x, n, [[p1, e1], …, [pk, ek]])

Testet, ob x eine Primitivwurzel in der multiplikativen Gruppe (Z/nZ)* ist.

Der verwendete Algorithmus benötigt die Primfaktorzerlegung des Totienten von n. Wird dieser Test nacheinander auf mehrere Zahlen angewandt, kann es sinnvoll sein, die Primfaktoren des Totienten vorab zu berechnen und zn_primroot_p als zusätzliches drittes Argument zu übergeben. Die Form muss dabei der Rückgabe von ifactors(totient(n)) mit der Standardeinstellung false der Optionsvariable factors_only entsprechen.

Siehe auch zn_primroot , zn_order , ifactors , totient .

Beispiele:

zn_primroot_p als Prädikatfunktion.

(%i1) n : 14$
(%i2) units_14 : sublist(makelist(i,i,1,13), lambda([i], gcd(i, n) = 1));
(%o2)                     [1, 3, 5, 9, 11, 13]
(%i3) zn_primroot_p(13, n);
(%o3)                            false
(%i4) sublist(units_14, lambda([x], zn_primroot_p(x, n)));
(%o4)                            [3, 5]
(%i5) map(lambda([x], zn_order(x, n)), units_14);
(%o5)                      [1, 6, 6, 3, 3, 2]

Das optionale dritte Argument muss der Rückgabe von ifactors(totient(n)) entsprechen.

(%i1) (p : 2^142 + 217, primep(p));
(%o1)                             true
(%i2) ifs : ifactors( totient(p) )$
(%i3) sublist(makelist(i,i,1,50), lambda([x], zn_primroot_p(x, p, ifs)));
(%o3)      [3, 12, 13, 15, 21, 24, 26, 27, 29, 33, 38, 42, 48]
(%i4) [time(%o2), time(%o3)];
(%o4)                   [[7.748484], [0.036002]]

Optionsvariable: zn_primroot_pretest

Standardwert: false

Eine multiplikative Gruppe (Z/nZ)* ist zyklisch, wenn n gleich 2, 4, p^k oder 2*p^k ist, wobei p prim und grösser 2 und k eine natürliche Zahl ist.

zn_primroot_pretest entscheidet darüber, ob zn_primroot. vor der Berechnung der kleinsten Primitivwurzel in (Z/nZ)* überprüft, ob auf n überhaupt einer der oben genannten Fälle zutrifft. Nur wenn zn_primroot_pretest true ist, wird dieser Prätest ausgeführt.

Optionsvariable: zn_primroot_verbose

Standardwert: false

Entscheidet, ob zn_primroot. beim Erreichen von zn_primroot_limit.

einen Hinweis ausgibt.


[ << ] [ >> ]           [Top] [Contents] [Index] [ ? ]

This document was generated by Robert on Juli, 9 2012 using texi2html 1.76.