| blob | 106a6dec15a3dc850e8b28193bfa86fed4c5e897 |
1 @c -----------------------------------------------------------------------------
2 @c File : Number.de.texi
3 @c License : GNU General Public License (GPL)
4 @c Language : German
5 @c Original : Number.texi revision 1.35
6 @c Translation : Dr. Dieter Kaiser
7 @c Date : 06.01.2011
8 @c Revision : 26.02.2011
9 @c
10 @c This file is part of Maxima -- GPL CAS based on DOE-MACSYMA
11 @c -----------------------------------------------------------------------------
13 @menu
14 * Funktionen und Variablen der Zahlentheorie::
15 @end menu
17 @c -----------------------------------------------------------------------------
18 @node Funktionen und Variablen der Zahlentheorie, , Zahlentheorie, Zahlentheorie
19 @section Funktionen und Variablen der Zahlentheorie
21 @c --- 23.11.2010 DK -----------------------------------------------------------
22 @anchor{bern}
23 @deffn {Funktion} bern (@var{n})
25 @c Returns the @var{n}'th Bernoulli number for integer @var{n}.
26 @c WELL, ACTUALLY bern SIMPLIFIES, LIKE FACTORIAL -- DO WE WANT TO GET INTO THAT
27 @c OR JUST PRETEND IT'S "RETURNED" ???
28 @c Bernoulli numbers equal to zero are suppressed if @code{zerobern} is
29 @c @code{false}.
31 Gibt die @var{n}-te Bernoulli-Zahl der ganzen Zahl @var{n} zur@"uck. Hat die
32 Optionsvariable @code{zerobern} den Wert @code{false}, werden Bernoulli-Zahlen
33 unterdr@"uckt, die Null sind.
35 Siehe auch @mrefdot{burn}
37 @example
38 (%i1) zerobern: true$
39 @group
40 (%i2) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
41 1 1 1 1 1
42 (%o2) [1, - -, -, 0, - --, 0, --, 0, - --]
43 2 6 30 42 30
44 @end group
45 (%i3) zerobern: false$
46 (%i4) map (bern, [0, 1, 2, 3, 4, 5, 6, 7, 8]);
47 1 1 1 5 691 7 3617 43867
48 (%o4) [1, - -, -, - --, --, - ----, -, - ----, -----]
49 2 6 30 66 2730 6 510 798
50 @end example
51 @end deffn
53 @c --- 23.11.2010 DK -----------------------------------------------------------
54 @anchor{bernpoly}
55 @deffn {Funktion} bernpoly (@var{x}, @var{n})
57 @c Returns the @var{n}'th Bernoulli polynomial in the variable @var{x}.
59 Gibt das @var{n}-te Bernoulli-Polynom in der Variablen @var{x} zur@"uck.
60 @end deffn
62 @c TODO: DIE FUNKTION ZETA KANN INZWISCHEN IN BELIEBIGER GENAUIGKEIT RECHNEN.
64 @c --- 23.11.2010 DK -----------------------------------------------------------
65 @anchor{bfzeta}
66 @deffn {Function} bfzeta (@var{s}, @var{n})
68 @c Returns the Riemann zeta function for the argument @var{s}. The return value
69 @c is a big float (bfloat); @var{n} is the number of digits in the return value.
71 Die Riemannsche Zeta-Funktion f@"ur das Argument @var{s}, die wie folgt
72 definiert ist:
74 @tex
75 $$\zeta\left(s\right)=\sum_{k=1}^{\infty }{{{1}\over{k^{s}}}}$$
76 @end tex
77 @ifnottex
78 @example
79 inf
80 ====
81 \ 1
82 zeta(s) = > --
83 / s
84 ==== k
85 k = 1
86 @end example
87 @end ifnottex
89 @code{bfzeta} gibt einen Wert als gro@ss{}e Gleitkommazahl zur@"uck. Die Anzahl
90 der Stellen wird durch das Argument @var{n} angegeben.
92 Anstatt der Funktion @code{bfzeta} ist die Funktion @mref{zeta} zu bevorzugen,
93 die sowohl f@"ur reelle und komplexe Gleitkommazahlen und Gleitkommazahlen mit
94 eine beliebigen Genauigkeit die Riemannsche Zeta-Funktion berechnen kann.
95 @end deffn
97 @c --- 23.11.2010 DK -----------------------------------------------------------
98 @anchor{bfhzeta}
99 @deffn {Funktion} bfhzeta (@var{s}, @var{h}, @var{n})
101 @c Returns the Hurwitz zeta function for the arguments @var{s} and @var{h}.
102 @c The return value is a big float (bfloat); @var{n} is the number of digits in
103 @c the return value.
105 @c The Hurwitz zeta function is defined as
107 Die Hurwitzsche Zeta-Funktion f@"ur die Argumente @var{s} und @var{h}, die wie
108 folgt definiert ist:
110 @tex
111 $$\zeta \left(s,h\right) = \sum_{k=0}^\infty {1 \over \left(k+h\right)^{s}}$$
112 @end tex
113 @ifnottex
114 @example
115 inf
116 ====
117 \ 1
118 zeta (s,h) = > --------
119 / s
120 ==== (k + h)
121 k = 0
122 @end example
123 @end ifnottex
125 @code{bfhzeta} gibt einen Wert als gro@ss{}e Gleitkommazahl zur@"uck. Die
126 Anzahl der Stellen wird durch das Argument @var{n} angegeben.
128 @c @code{load ("bffac")} loads this function.
129 @end deffn
131 @c --- 27.11.2010 DK -----------------------------------------------------------
132 @anchor{burn}
133 @deffn {Funktion} burn (@var{n})
135 @c Returns a rational number, which is an approximation of the @var{n}'th
136 @c Bernoulli number for integer @var{n}. @code{burn} exploits the observation
137 @c that (rational) Bernoulli numbers can be approximated by (transcendental)
138 @c zetas with tolerable efficiency:
140 Gibt eine rational Zahl zur@"uck, die eine N@"aherung f@"ur die @var{n}-te
141 Bernoulli Zahl f@"ur die ganze Zahl @var{n} ist. @code{burn} berechnet eine
142 N@"aherung als gro@ss{}e Gleitkommatzahl mit der folgenden Beziehung:
144 @example
145 n - 1 1 - 2 n
146 (- 1) 2 zeta(2 n) (2 n)!
147 B(2 n) = ------------------------------------
148 2 n
149 %pi
150 @end example
152 @c @code{burn} may be more efficient than @code{bern} for large, isolated
153 @c @var{n} as @code{bern} computes all the Bernoulli numbers up to index @var{n}
154 @c before returning. @code{burn} invokes the approximation for even integers
155 @c @var{n} > 255. For odd integers and @var{n} <= 255 the function @code{bern}
156 @c is called.
158 @code{burn} kann effizienter als die Funktion @code{bern} f@"ur gro@ss{}e,
159 einzelne ganze Zahlen @var{n} sein, da @code{bern} zun@"achst alle Bernoulli
160 Zahlen bis @var{n} berechnet. @code{burn} ruft f@"ur ungerade ganze Zahlen und
161 Zahlen die kleiner oder gleich 255 die Funktion @code{bern} auf.
163 @c @code{load ("bffac")} loads this function. See also @code{bern}.
165 Das Kommando @code{load("bffac")} l@"adt die Funktion. Siehe auch @mrefdot{bern}
166 @end deffn
168 @c --- 27.03.2012 VN -----------------------------------------------------------
169 @anchor{chinese}
170 @deffn {Funktion} chinese ([@var{r_1}, @dots{}, @var{r_n}], [@var{m_1}, @dots{}, @var{m_n}])
172 L@"ost die simultanen Kongruenzen @code{x = r_1 mod m_1}, @dots{}, @code{x = r_n mod m_n}.
173 Die Reste @var{r_n} und die Moduli @var{m_n} m@"ussen ganze Zahlen sein,
174 die Moduli zus@"atzlich positiv und paarweise teilerfremd.
176 @example
177 (%i1) mods : [1000, 1001, 1003, 1007];
178 (%o1) [1000, 1001, 1003, 1007]
179 (%i2) lreduce('gcd, mods);
180 (%o2) 1
181 (%i3) x : random(apply("*", mods));
182 (%o3) 685124877004
183 (%i4) rems : map(lambda([z], mod(x, z)), mods);
184 (%o4) [4, 568, 54, 624]
185 (%i5) chinese(rems, mods);
186 (%o5) 685124877004
187 (%i6) chinese([1, 2], [3, n]);
188 (%o6) chinese([1, 2], [3, n])
189 (%i7) %, n = 4;
190 (%o7) 10
191 @end example
192 @end deffn
194 @c --- 23.11.2010 DK -----------------------------------------------------------
195 @anchor{divsum}
196 @deffn {Funktion} divsum (@var{n}, @var{k})
197 @deffnx {Funktion} divsum (@var{n})
199 @c @code{divsum (@var{n}, @var{k})} returns the sum of the divisors of @var{n}
200 @c raised to the @var{k}'th power.
202 @code{divsum(@var{n}, @var{k})} potenziert die Teiler des Argumentes @var{n}
203 mit dem Argument @var{k} und gibt die Summe als Ergebnis zur@"uck.
205 @c @code{divsum (@var{n})} returns the sum of the divisors of @var{n}.
207 @code{divsum(@var{n})} gibt die Summe der Teiler der Zahl @var{n} zur@"uck.
209 @example
210 (%i1) divsum (12);
211 (%o1) 28
212 (%i2) 1 + 2 + 3 + 4 + 6 + 12;
213 (%o2) 28
214 (%i3) divsum (12, 2);
215 (%o3) 210
216 (%i4) 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2;
217 (%o4) 210
218 @end example
219 @end deffn
221 @c --- 27.11.2010 DK -----------------------------------------------------------
222 @anchor{euler}
223 @deffn {Funktion} euler (@var{n})
225 @c Returns the @var{n}'th Euler number for nonnegative integer @var{n}.
227 Gibt die @var{n}-te Eulersche Zahl f@"ur eine nichtnegative ganze Zahl @var{n}
228 zur@"uck.
230 @c For the Euler-Mascheroni constant, see @code{%gamma}.
232 F@"ur die Euler-Mascheroni Konstante siehe @mrefdot{%gamma}
234 Beispiele:
236 @example
237 (%i1) map (euler, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
238 (%o1) [1, 0, - 1, 0, 5, 0, - 61, 0, 1385, 0, - 50521]
239 @end example
240 @end deffn
242 @c --- 27.07.2013 VvN ----------------------------------------------------------
243 @anchor{factors_only}
244 @defvr {Optionsvariable} factors_only
245 Standardwert: @code{false}
247 Hat @code{factors_only} den Standardwert @code{false}, werden von der
248 Funktion @mref{ifactors} zusammen mit den berechneten Primfaktoren auch deren
249 Multiplizit@"aten angegeben. Hat @code{factors_only} den Wert @code{true},
250 werden nur die Primfaktoren zur@"uck gegeben.
252 Beispiel: Siehe @mref{ifactors}.
253 @end defvr
255 @c --- 27.07.2013 VvN ----------------------------------------------------------
256 @anchor{fib}
257 @deffn {Funktion} fib (@var{n})
259 Gibt die @var{n}-te Fibonacci-Zahl zur@"uck. Die Fibonacci-Folge ist rekursiv
260 definiert:
262 @example
263 fib(0) = 0
264 fib(1) = 1
265 fib(n) = fib(n-1) + fib(n-2)
266 @end example
268 F@"ur negative ganze Zahlen kann die Fibonacci-Folge wie folgt erweitert werden:
270 @example
271 n + 1
272 fib(- n) = (- 1) fib(n)
273 @end example
275 @c After calling @code{fib}, @code{prevfib} is equal to @code{fib(@var{x} - 1)},
276 @c the Fibonacci number preceding the last one computed.
278 @c TODO: PREVFIB HAT KEINEN EINTRAG.
280 Nach einem Aufruf der Funktion @code{fib(n)}, enth@"alt die Systemvariable
281 @code{prevfib} die zur Zahl @code{n} vorhergehende Fibonacci-Zahl.
283 @example
284 (%i1) map (fib, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
285 (%o1) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
286 @end example
287 @end deffn
289 @c --- 23.11.2010 DK -----------------------------------------------------------
290 @anchor{fibtophi}
291 @deffn {Funktion} fibtophi (@var{expr})
293 @c Expresses Fibonacci numbers in @var{expr} in terms of the constant
294 @c @code{%phi}, which is @code{(1 + sqrt(5))/2}, approximately 1.61803399.
296 Fibonacci-Zahlen im Ausdruck @var{expr} werden durch die Goldene Zahl
297 @code{%phi} ausgedr@"uckt. Siehe @mrefdot{%phi}
299 Beispiele:
301 @example
302 (%i1) fibtophi (fib (n));
303 n n
304 %phi - (1 - %phi)
305 (%o1) -------------------
306 2 %phi - 1
307 (%i2) fib (n-1) + fib (n) - fib (n+1);
308 (%o2) - fib(n + 1) + fib(n) + fib(n - 1)
309 (%i3) fibtophi (%);
310 n + 1 n + 1 n n
311 %phi - (1 - %phi) %phi - (1 - %phi)
312 (%o3) - --------------------------- + -------------------
313 2 %phi - 1 2 %phi - 1
314 n - 1 n - 1
315 %phi - (1 - %phi)
316 + ---------------------------
317 2 %phi - 1
318 (%i4) ratsimp (%);
319 (%o4) 0
320 @end example
321 @end deffn
323 @c --- 23.03.2013 VN -----------------------------------------------------------
324 @anchor{ifactors}
325 @deffn {Funktion} ifactors (@var{n})
327 Faktorisiert eine positive ganze Zahl @var{n}. Sind @code{n = p1^e1 * ... * pk^nk} die
328 Faktoren der ganzen Zahl @var{n}, dann gibt @code{ifactor} das Ergebnis
329 @code{[[p1, e1], ..., [pk, ek]]} zur@"uck.
331 F@"ur die Faktorisierung kommen Probedivisionen mit Primzahlen bis 9973,
332 Pollards Rho- und p-1-Methode oder Elliptischen Kurven zum Einsatz.
334 Die R@"uckgabe von ifactors wird von der Optionsvariablen @mref{factors_only}
335 beeinflusst.
336 Werden lediglich die Primfaktoren ohne ihre Multiplizit@"at ben@"otigt,
337 gen@"ugt es hierf@"ur, @code{factors_only : true} zu setzen.
339 @example
340 (%i1) ifactors(51575319651600);
341 (%o1) [[2, 4], [3, 2], [5, 2], [1583, 1], [9050207, 1]]
342 (%i2) apply("*", map(lambda([u], u[1]^u[2]), %));
343 (%o2) 51575319651600
344 (%i3) ifactors(51575319651600), factors_only : true;
345 (%o3) [2, 3, 5, 1583, 9050207]
346 @end example
347 @end deffn
349 @c --- 23.03.2013 VN -----------------------------------------------------------
350 @anchor{igcdex}
351 @deffn {Funktion} igcdex (@var{n}, @var{k})
353 @c Gibt die Liste @code{[@var{a}, @var{b}, @var{u}]} zur@"uck, in der @var{u} der
354 Gibt die Liste @code{[a, b, u]} zur@"uck, in der @code{u} der
355 gr@"o@ss{}te gemeinsame Teiler von @var{n} und @var{k} ist und in der zus@"atzlich
356 @c gilt, dass @code{@var{u} = @var{a} * @var{n} + @var{b} * @var{k}}.
357 gilt, dass @code{u = a * @var{n} + b * @var{k}}.
359 @code{igcdex} verwendet den Euklidischen Algorithmus. Siehe auch @mref{gcdex}.
361 Die Eingabe @code{load("gcdex")} l@"adt diese Funktion.
363 Beispiele:
365 @example
366 (%i1) load("gcdex")$
368 (%i2) igcdex(30, 18);
369 (%o2) [- 1, 2, 6]
370 (%i3) igcdex(1526757668, 7835626735736);
371 (%o3) [845922341123, - 164826435, 4]
372 (%i4) igcdex(fib(20), fib(21));
373 (%o4) [4181, - 2584, 1]
374 @end example
375 @end deffn
377 @c --- 23.11.2010 DK -----------------------------------------------------------
378 @anchor{inrt}
379 @deffn {Funktion} inrt (@var{x}, @var{n})
381 @c Returns the integer @var{n}'th root of the absolute value of @var{x}.
383 Gibt die ganzzahlige @var{n}-te Wurzel des Betrags von @var{x} zur@"uck.
385 @example
386 (%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
387 (%i2) map (lambda ([a], inrt (10^a, 3)), l);
388 (%o2) [2, 4, 10, 21, 46, 100, 215, 464, 1000, 2154, 4641, 10000]
389 @end example
390 @end deffn
392 @c --- 27.03.2012 VN -----------------------------------------------------------
393 @anchor{inv_mod}
394 @deffn {Funktion} inv_mod (@var{n}, @var{m})
396 Berechnet das modulare Inverse von @var{n} zum Modul @var{m}. Das Argument
397 @var{n} muss eine ganze Zahl und der Modul @var{p} eine positive ganze Zahl
398 sein. @code{inv_mod(n, m)} gibt @code{false} zur@"uck, wenn das modulare Inverse
399 nicht existiert. Das modulare Inverse existiert, wenn @var{n} teilerfremd zum
400 Modul @var{m} ist.
402 Siehe auch die Funktionen @mref{power_mod} und @mrefdot{mod}
404 Beispiele:
406 @example
407 (%i1) inv_mod(3, 41);
408 (%o1) 14
409 (%i2) ratsimp(3^-1), modulus = 41;
410 (%o2) 14
411 (%i3) inv_mod(3, 42);
412 (%o3) false
413 @end example
414 @end deffn
416 @c --- 20.10.2010 DK -----------------------------------------------------------
417 @anchor{isqrt}
418 @deffn {Funktion} isqrt (@var{x})
420 @c Returns the "integer square root" of the absolute value of @var{x}, which is
421 @c an integer.
423 Gibt die ganzzahlige Wurzel des Betrages von @var{x} zur@"uck, wenn @var{x} eine
424 ganze Zahl ist. Andernfalls wird eine Substantivform zur@"uckgegeben.
425 @end deffn
427 @c --- 27.11.2010 DK -----------------------------------------------------------
428 @anchor{jacobi}
429 @deffn {Funktion} jacobi (@var{p}, @var{q})
431 @c Returns the Jacobi symbol of @var{p} and @var{q}.
433 Berechnet das Jacobi-Symbol f@"ur die Argumente @var{p} und @var{q}.
435 @example
436 (%i1) l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
437 (%i2) map (lambda ([a], jacobi (a, 9)), l);
438 (%o2) [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]
439 @end example
440 @end deffn
442 @c --- 27.03.2012 VN -----------------------------------------------------------
443 @anchor{lcm}
444 @deffn {Funktion} lcm (@var{expr_1}, @dots{}, @var{expr_n})
446 @c Returns the least common multiple of its arguments. The arguments may be
447 @c general expressions as well as integers.
449 Gibt das kleinste gemeinsame Vielfache der Argumente zur@"uck. Die Argumente
450 k@"onnen ganze Zahlen und allgemeine Ausdr@"ucke sein.
452 @c @code{load ("functs")} loads this function.
454 Mit dem Kommando @code{load("functs")} wird die Funktion geladen.
455 @end deffn
457 @c --- 27.07.2013 VvN ----------------------------------------------------------
458 @anchor{lucas}
459 @deffn {Funktion} lucas (@var{n})
461 Gibt die @var{n}-te Lucas-Zahl zur@"uck. Die Lucas-Folge ist rekursiv
462 definiert:
464 @example
465 lucas(0) = 0
466 lucas(1) = 1
467 lucas(n) = lucas(n-1) + lucas(n-2)
468 @end example
470 F@"ur negative ganze Zahlen kann die Lucas-Folge wie folgt erweitert werden:
472 @example
473 -n
474 lucas(- n) = (- 1) lucas(n)
475 @end example
477 @example
478 (%i1) map (lucas, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
479 (%o1) [7, - 4, 3, - 1, 2, 1, 3, 4, 7, 11, 18, 29, 47]
480 @end example
482 Nach einem Aufruf von @code{lucas} enth@"alt die globale Variable
483 @code{next_lucas} den Nachfolger der zuletzt zur@"ck gegebenen Lucas-Zahl.
484 Das Beispiel zeigt, wie Fibonacci-Zahlen mit Hilfe von @code{lucas}
485 und @code{next_lucas} berechnet werden k@"onnen.
487 @example
488 (%i1) fib_via_lucas(n) :=
489 block([lucas : lucas(n)],
490 signum(n) * (2*next_lucas - lucas)/5 )$
491 (%i2) map (fib_via_lucas, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]);
492 (%o2) [- 3, 2, - 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21]
493 @end example
494 @end deffn
496 @c --- 23.03.2013 VN -----------------------------------------------------------
497 @anchor{mod}
498 @deffn {Funktion} mod (@var{x}, @var{p})
500 @c If @var{x} and @var{y} are real numbers and @var{y} is nonzero, return
501 @c @code{@var{x} - @var{y} * floor(@var{x} / @var{y})}. Further for all real
502 @c @var{x}, we have @code{mod (@var{x}, 0) = @var{x}}. For a discussion of the
503 @c definition @code{mod (@var{x}, 0) = @var{x}}, see Section 3.4, of
504 @c "Concrete Mathematics," by Graham, Knuth, and Patashnik. The function
505 @c @code{mod (@var{x}, 1)} is a sawtooth function with period 1 with
506 @c @code{mod (1, 1) = 0} and @code{mod (0, 1) = 0}.
508 Berechnet den Divisionsrest @code{x mod y} des Arguments @var{x} zum Modul @var{y}.
509 @var{x} und @var{y} k@"onnen ganze Zahlen, rationale Zahlen, Gleitkommazahlen
510 oder allgemeine Ausdr@"ucke sein.
512 Sind @var{x} und @var{y} reelle Zahlen und ist @var{y} ungleich Null, gibt
513 @code{mod(@var{x}, @var{y})} das Ergebnis von @code{@var{x} - @var{y} *
514 floor(@var{x} / @var{y})} zur@"uck. Weiterhin gilt f@"ur alle reellen Zahlen
515 @code{mod(@var{x}, 0) = @var{x}}. F@"ur eine Diskussion dieser Definition siehe
516 Kapitel 3.4, "Concrete Mathematics" von Graham, Knuth, and Patashnik. Die
517 Funktion @code{mod(@var{x}, 1)} ist eine S@"agezahnfunktion mit der Periode 1
518 mit @code{mod(1, 1) = 0} und @code{mod(0, 1) = 0}.
520 @c To find the principal argument (a number in the interval @code{(-%pi, %pi]})
521 @c of a complex number, use the function @code{@var{x} |-> %pi - mod (%pi -
522 @c @var{x}, 2*%pi)}, where @var{x} is an argument.
524 Der Hauptwert einer komplexen Zahl, die im Intervall @code{(-%pi, %pi)} liegt,
525 kann mit @code{%pi - mod(%pi - @var{x}, 2*%pi)} bestimmt werden, wobei @var{x}
526 die komplexe Zahl ist.
528 @c When @var{x} and @var{y} are constant expressions (@code{10 * %pi}, for
529 @c example), @code{mod} uses the same big float evaluation scheme that
530 @c @code{floor} and @code{ceiling} uses. Again, it's possible, although
531 @c unlikely, that @code{mod} could return an erroneous value in such cases.
533 Sind @var{x} und @var{y} konstante Ausdr@"ucke, wie zum Beispiel @code{10 * %pi},
534 verwendet @code{mod} dasselbe @mref{bfloat}-Auswertungsschema wie @code{floor}
535 und @code{ceiling}. Diese Umwandlung kann, wenn auch unwahrscheinlich,
536 zu Fehlern f@"uhren.
538 @c For nonnumerical arguments @var{x} or @var{y}, @code{mod} knows several
539 @c simplification rules:
541 F@"ur nicht numerische Argumente @var{x} oder @var{y} kennt @code{mod}
542 verschiedene Vereinfachungen.
544 Siehe auch die Funktionen @mref{power_mod} und @mrefdot{inv_mod}
546 Beispiele:
548 Zeige f@"ur zwei gro@ss{}e ganze Zahlen, dass f@"ur das modulare Rechnen die
549 Regel @code{mod(a+b, m) = mod(mod(a, m) + mod(b, m), m)} gilt.
551 @example
552 (%i1) a : random(10^20) + 10^19;
553 (%o1) 72588919020045581148
554 (%i2) b : random(10^20) + 10^19;
555 (%o2) 35463666253140008825
556 (%i3) m : random(10^20) + 10^19;
557 (%o3) 39127433614020247557
558 (%i4) mod(a+b, m);
559 (%o4) 29797718045145094859
560 (%i5) mod(mod(a, m) + mod(b, m), m);
561 (%o5) 29797718045145094859
562 @end example
564 Vereinfachung f@"ur nicht numerische Argumente.
566 @example
567 (%i1) mod (x, 0);
568 (%o1) x
569 (%i2) mod (a*x, a*y);
570 (%o2) a mod(x, y)
571 (%i3) mod (0, x);
572 (%o3) 0
573 @end example
574 @end deffn
576 @c --- 27.11.2010 DK -----------------------------------------------------------
577 @anchor{next_prime}
578 @deffn {Funktion} next_prime (@var{n})
580 @c Returns the smallest prime bigger than @var{n}.
582 Gibt die kleinste Primzahl zur@"uck, die der Zahl @var{n} folgt.
584 @example
585 (%i1) next_prime(27);
586 (%o1) 29
587 @end example
588 @end deffn
590 @c --- 27.03.2012 VN -----------------------------------------------------------
591 @anchor{power_mod}
592 @deffn {Funktion} power_mod (@var{a}, @var{n}, @var{m})
594 Verwendet einen modularen Algorithmus, um @code{a^n mod m} zu berechnen.
595 Die Argumente @var{a} und @var{n} m@"ussen ganze Zahlen und der Modul @var{m}
596 eine positive ganze Zahl sein. Ist @var{n} negativ, wird @mref{inv_mod} zur
597 Berechnung des modularen Inversen aufgerufen.
599 @code{power_mod (@var{a}, @var{n}, @var{m})} ist @"aquivalent zu
600 @code{mod(a^n, m)}. Der Algorithmus von @code{power_mod} ist jedoch
601 insbesondere f@"ur gro@ss{}e ganze Zahlen wesentlich effizienter.
603 Siehe auch die Funktionen @mref{inv_mod} und @mrefdot{mod}
605 Beispiele:
607 @code{power_mod(a, n, m)} ist @"aquivalent zu @code{mod(a^n, m}. Das modulare
608 Inverse wird mit der Funktion @code{inv_mod} berechnet.
610 @example
611 (%i1) power_mod(3, 15, 5);
612 (%o1) 2
613 (%i2) mod(3^15, 5);
614 (%o2) 2
615 (%i3) power_mod(2, -1, 5);
616 (%o3) 3
617 (%i4) inv_mod(2, 5);
618 (%o4) 3
619 @end example
621 F@"ur gro@ss{}e ganze Zahlen ist @code{power_mod} effizienter. Der folgende
622 Wert kann in keiner vern@"unftigen Zeit mit @code{mod(a^n, m)} berechnet
623 werden.
625 @example
626 (%i1) power_mod(123456789, 123456789, 987654321);
627 (%o1) 598987215
628 @end example
629 @end deffn
631 @c --- 27.03.2012 VN -----------------------------------------------------------
632 @anchor{primep}
633 @deffn {Funktion} primep (@var{n})
635 F@"uhrt einen Primzahltest f@"ur das Argument @var{n} durch. Liefert
636 @code{primep} das Ergebnis @code{false}, ist @var{n} keine Primzahl. Ist das
637 Ergebnis @code{true}, ist @var{n} mit sehr gro@ss{}er Wahrscheinlichkeit eine
638 Primzahl.
640 F@"ur ganze Zahlen @var{n} kleiner als 3317044064679887385961981 wird eine deterministische
641 Variante des Miller-Rabin-Tests angewandt. Hat in diesem Fall @code{primep} den Wert
642 @code{true}, dann ist @var{n} mit Sicherheit eine Primzahl.
644 F@"ur ganze Zahlen @var{n} gr@"o@ss{}er 3317044064679887385961981 f@"uhrt @code{primep}
645 @mref{primep_number_of_tests} Pseudo-Primzahl-Tests nach Miller-Rabin und
646 einen Pseudo-Primzahl-Test nach Lucas durch. Die Wahrscheinlichkeit, dass
647 eine zusammen gesetzte Zahl @var{n} einen Miller-Rabin-Test besteht, ist kleiner
648 als 1/4. Mit dem Standardwert 25 @code{primpe_number_of_tests} sinkt diese
649 Wahrscheinlichkeit damit unter einen Wert von 10^-15.
650 @end deffn
652 @c --- 23.03.2013 VN -----------------------------------------------------------
653 @anchor{primep_number_of_tests}
654 @defvr {Optionsvariable} primep_number_of_tests
655 Standardwert: 25
657 @c Number of Miller-Rabin's tests used in @code{primep}.
659 Die Anzahl der Pseudo-Primzahl-Tests nach Miller-Rabin in der Funktion
660 @mref{primep}.
661 @end defvr
663 @c --- 13.06.2015 VN -----------------------------------------------------------
664 @anchor{primes}
665 @deffn {Funktion} primes (@var{start}, @var{end})
667 Gibt eine Liste mit allen Primzahlen von @var{start} bis @var{end} zur@"uck.
669 @example
670 (%i1) primes(3, 7);
671 (%o1) [3, 5, 7]
672 @end example
673 @end deffn
675 @c --- 27.11.2010 DK -----------------------------------------------------------
676 @anchor{prev_prime}
677 @deffn {Funktion} prev_prime (@var{n})
679 @c Returns the greatest prime smaller than @var{n}.
681 Gibt die gr@"o@ss{}te Primzahl zur@"uck, die kleiner als die Zahl @var{n} ist.
683 @example
684 (%i1) prev_prime(27);
685 (%o1) 23
686 @end example
687 @end deffn
689 @c --- 27.11.2010 DK -----------------------------------------------------------
690 @anchor{qunit}
691 @deffn {Funktion} qunit (@var{n})
693 @c Returns the principal unit of the real quadratic number field
694 @c @code{sqrt (@var{n})} where @var{n} is an integer, i.e., the element whose
695 @c norm is unity. This amounts to solving Pell's equation
696 @c @code{a^2 - @var{n} b^2 = 1}.
698 Findet f@"ur das Argument @var{n} L@"osungen der Pellschen Gleichung
699 @code{a^2 - @var{n} b^2 = 1}.
701 @example
702 (%i1) qunit (17);
703 (%o1) sqrt(17) + 4
704 (%i2) expand (% * (sqrt(17) - 4));
705 (%o2) 1
706 @end example
707 @end deffn
709 @c --- 27.03.2012 VN -----------------------------------------------------------
710 @anchor{totient}
711 @deffn {Funktion} totient (@var{n})
713 Gibt die Anzahl der ganzen Zahlen zur@"uck, die kleiner oder gleich @var{n}
714 und teilerfremd zu @var{n} sind.
715 @end deffn
717 @c --- 27.03.2012 VN -----------------------------------------------------------
718 @anchor{zerobern}
719 @defvr {Optionsvariable} zerobern
720 Standardwert: @code{true}
722 @c When @code{zerobern} is @code{false}, @code{bern} excludes the Bernoulli
723 @c numbers and @code{euler} excludes the Euler numbers which are equal to zero.
724 @c See @code{bern} and @code{euler}.
726 Hat @code{zerobern} den Wert @code{false}, werden von den Funktionen @code{bern}
727 diejenigen Bernoulli-Zahlen und von @code{euler} diejenigen Euler-Zahlen
728 ausgeschlossen, die gleich Null sind. Siehe @mref{bern} und @mrefdot{euler}
729 @end defvr
731 @c --- 23.03.2013 VN -----------------------------------------------------------
732 @anchor{zeta}
733 @deffn {Funktion} zeta (@var{n})
735 @c Returns the Riemann zeta function. If @var{n} is a negative integer, 0, or a
736 @c positive even integer, the Riemann zeta function simplifies to an exact
737 @c value. For a positive even integer the option variable @code{zeta%pi} has to
738 @c be @code{true} in addition (See @code{zeta%pi}). For a floating point or
739 @c bigfloat number the Riemann zeta function is evaluated numerically. Maxima
740 @c returns a noun form @code{zeta (@var{n})} for all other arguments, including
741 @c rational noninteger, and complex arguments, or for even integers, if
742 @c @code{zeta%pi} has the value @code{false}.
744 Die Riemannsche Zeta-Funktion f@"ur @var{s}, die wie folgt definiert ist:
746 @tex
747 $$\zeta\left(s\right)=\sum_{k=1}^{\infty }{{{1}\over{k^{s}}}}$$
748 @end tex
749 @ifnottex
750 @example
751 inf
752 ====
753 \ 1
754 zeta(s) = > --
755 / s
756 ==== k
757 k = 1
758 @end example
759 @end ifnottex
761 F@"ur negative ganze Zahlen @var{n}, Null und positive gerade ganze Zahlen
762 wird @code{zeta} zu einem exakten Ergebnis vereinfacht.
763 Damit diese Vereinfachung f@"ur positive ganze Zahlen ausgef@"uhrt wird,
764 muss die Optionsvariable @code{zeta%pi} den Wert @code{true} haben.
765 Siehe @mref{zeta%pi}. F@"ur einfache und beliebig genaue Gleitkommazahlen
766 (Typ @code{bfloat}) hat @code{zeta} ein numerisches Ergebnis.
767 F@"ur alle anderen Argumente einschlie@ss{}lich der komplexen und
768 rationalen Zahlen gibt @code{zeta} eine Substantivform zur@"uck. Hat die
769 Optionsvariable @code{zeta%pi} den Wert @code{false}, gibt @code{zeta} auch
770 f@"ur gerade ganze Zahlen eine Substantivform zur@"uck.
772 @c @code{zeta(1)} is undefined, but Maxima knows the limit
773 @c @code{limit(zeta(x), x, 1)} from above and below.
775 @code{zeta(1)} ist nicht definiert. Maxima kennt jedoch die einseitigen
776 Grenzwerte @code{limit(zeta(x), x, 1, plus} und
777 @code{limit(zeta(x), x, 1, minus}.
779 @c The Riemann zeta function distributes over lists, matrices, and equations.
781 Die Riemannsche Zeta-Funktion wird auf die Argumente von Listen, Matrizen und
782 Gleichungen angewendet, wenn die Optionsvariable @code{distribute_over}
783 den Wert @code{true} hat.
785 @c See also @code{bfzeta} and @code{zeta%pi}.
787 Siehe auch @mref{bfzeta} und @mrefdot{zeta%pi}
789 Beispiele:
791 @example
792 (%i1) zeta([-2,-1,0,0.5,2,3,1+%i]);
793 2
794 1 1 %pi
795 (%o1) [0, - --, - -, - 1.460354508809586, ----, zeta(3),
796 12 2 6
797 zeta(%i + 1)]
798 (%i2) limit(zeta(x),x,1,plus);
799 (%o2) inf
800 (%i3) limit(zeta(x),x,1,minus);
801 (%o3) minf
802 @end example
803 @end deffn
805 @c --- 27.11.2010 DK -----------------------------------------------------------
806 @anchor{zeta%pi}
807 @defvr {Optionsvariable} zeta%pi
808 Standardwert: @code{true}
810 @c When @code{zeta%pi} is @code{true}, @code{zeta} returns an expression
811 @c proportional to @code{%pi^n} for even integer @code{n}. Otherwise,
812 @c @code{zeta} returns a noun form @code{zeta (n)} for even integer @code{n}.
814 Hat @code{zeta%pi} den Wert @code{true}, vereinfacht die Funktion @code{zeta(n)}
815 f@"ur gerade ganzen Zahlen @var{n} zu einem Ergebnis, das proportional zu
816 @code{%pi^n} ist. Ansonsten ist das Ergebnis von @code{zeta} eine
817 Substantivform f@"ur gerade ganze Zahlen.
819 Beispiele:
821 @example
822 (%i1) zeta%pi: true$
823 (%i2) zeta (4);
824 4
825 %pi
826 (%o2) ----
827 90
828 (%i3) zeta%pi: false$
829 (%i4) zeta (4);
830 (%o4) zeta(4)
831 @end example
832 @end defvr
834 @c --- 27.07.2013 VvN ----------------------------------------------------------
835 @anchor{zn_add_table}
836 @deffn {Funktion} zn_add_table (@var{n})
838 zeigt eine Additionstabelle von allen Elementen in (Z/@var{n}Z).
840 Siehe auch @mref{zn_mult_table}, @mref{zn_power_table}.
841 @end deffn
843 @c -----------------------------------------------------------------------------
844 @anchor{zn_characteristic_factors}
845 @deffn {Funktion} zn_characteristic_factors (@var{n})
847 Gibt eine Liste mit den charakteristischen Faktoren des Totienten von @var{n} zur@"uck.
849 Mit Hilfe der charakteristischen Faktoren kann eine modulo @var{n} multiplikative Gruppe
850 als direktes Produkt zyklischer Untergruppen dargestellt werden.
852 Ist die Gruppe selbst zyklisch, dann enth@"alt die Liste nur den Totienten
853 und mit @code{zn_primroot} kann ein Generator berechnet werden.
854 Zerf@"allt der Totient in mehrere charakteristische Faktoren,
855 k@"onnen Generatoren der entsprechenden Untergruppen mit @code{zn_factor_generators}
856 ermittelt werden.
858 Jeder der @code{r} Faktoren in der Liste teilt die weiter rechts stehenden Faktoren.
859 Fuer den letzten Faktor @code{f_r} gilt daher @code{a^f_r = 1 (mod n)}
860 f@"ur alle @code{a} teilerfremd zu @var{n}.
861 Dieser Faktor ist auch als Carmichael Funktion bzw. Carmichael Lambda bekannt.
863 F@"ur @code{n > 2} ist @code{totient(n)/2^r} die Anzahl der quadratischen Reste
864 in der Gruppe und jeder dieser Reste hat @code{2^r} Wurzeln.
866 Siehe auch @mref{totient}, @mref{zn_primroot}, @mref{zn_factor_generators}.
868 Beispiele:
870 Die multiplikative Gruppe modulo @code{14} ist zyklisch und ihre @code{6} Elemente
871 lassen sich durch eine Primitivwurzel erzeugen.
873 @example
874 (%i1) [zn_characteristic_factors(14), phi: totient(14)];
875 (%o1) [[6], 6]
876 (%i2) [zn_factor_generators(14), g: zn_primroot(14)];
877 (%o2) [[3], 3]
878 (%i3) M14: makelist(power_mod(g,i,14), i,0,phi-1);
879 (%o3) [1, 3, 9, 13, 11, 5]
880 @end example
882 Die multiplikative Gruppe modulo @code{15} ist nicht zyklisch und ihre @code{8} Elemente
883 lassen sich mit Hilfe zweier Faktorgeneratoren erzeugen.
885 @example
886 (%i1) [[f1,f2]: zn_characteristic_factors(15), totient(15)];
887 (%o1) [[2, 4], 8]
888 (%i2) [[g1,g2]: zn_factor_generators(15), zn_primroot(15)];
889 (%o2) [[11, 7], false]
890 (%i3) UG1: makelist(power_mod(g1,i,15), i,0,f1-1);
891 (%o3) [1, 11]
892 (%i4) UG2: makelist(power_mod(g2,i,15), i,0,f2-1);
893 (%o4) [1, 7, 4, 13]
894 (%i5) M15: create_list(mod(i*j,15), i,UG1, j,UG2);
895 (%o5) [1, 7, 4, 13, 11, 2, 14, 8]
896 @end example
898 F@"ur den letzten charakteristischen Faktor @code{4} gilt
899 @code{a^4 = 1 (mod 15)} fuer alle @code{a} in @code{M15}.
901 @code{M15} hat @code{2} charakteristische Faktoren und daher die @code{8/2^2}
902 quadratischen Reste @code{1} und @code{4}, und diese haben jeweils @code{2^2} Wurzeln.
904 @example
905 (%i6) zn_power_table(15);
906 [ 1 1 1 1 ]
907 [ ]
908 [ 2 4 8 1 ]
909 [ ]
910 [ 4 1 4 1 ]
911 [ ]
912 [ 7 4 13 1 ]
913 (%o6) [ ]
914 [ 8 4 2 1 ]
915 [ ]
916 [ 11 1 11 1 ]
917 [ ]
918 [ 13 4 7 1 ]
919 [ ]
920 [ 14 1 14 1 ]
921 (%i7) map(lambda([i], zn_nth_root(i,2,15)), [1,4]);
922 (%o7) [[1, 4, 11, 14], [2, 7, 8, 13]]
923 @end example
924 @end deffn
926 @c -----------------------------------------------------------------------------
927 @anchor{zn_carmichael_lambda}
928 @deffn {Funktion} zn_carmichael_lambda (@var{n})
930 Gibt @code{1} zur@"uck, wenn @var{n} gleich @code{1} ist und andernfalls
931 den gr@"o@ss{}ten charakteristischen Faktor des Totienten von @var{n}.
933 F@"ur Erl@"auterungen und Beispiele siehe @mref{zn_characteristic_factors}.
935 @end deffn
937 @c --- 27.07.2013 VvN ----------------------------------------------------------
938 @anchor{zn_determinant}
939 @deffn {Funktion} zn_determinant (@var{matrix}, @var{p})
941 verwendet die Technik der LR-Dekomposition, um die Determinante der
942 Matrix @var{matrix} @"uber (Z/@var{p}Z) zu berechnen, wobei @var{p}
943 eine Primzahl sein muss.
945 Ist die Determinante nicht von Null verschieden, kann es sein, dass die
946 LR-Dekomposition nicht m@"oglich ist. @code{zn_determinant} berechnet
947 diesem Fall die Determinante nicht-modular und reduziert im Nachhinein.
949 Siehe auch @mref{zn_invert_by_lu}.
951 Beispiel:
953 @example
954 (%i1) m : matrix([1,3],[2,4]);
955 [ 1 3 ]
956 (%o1) [ ]
957 [ 2 4 ]
958 (%i2) zn_determinant(m, 5);
959 (%o2) 3
960 (%i3) m : matrix([2,4,1],[3,1,4],[4,3,2]);
961 [ 2 4 1 ]
962 [ ]
963 (%o3) [ 3 1 4 ]
964 [ ]
965 [ 4 3 2 ]
966 (%i4) zn_determinant(m, 5);
967 (%o4) 0
968 @end example
969 @end deffn
971 @c -----------------------------------------------------------------------------
972 @anchor{zn_factor_generators}
973 @deffn {Funktion} zn_factor_generators (@var{n})
975 Gibt eine Liste mit Faktorgeneratoren zur@"uck, die zu den charakteristischen
976 Faktoren des Totienten von @var{n} passen.
978 F@"ur Erl@"auterungen und Beispiele siehe @mref{zn_characteristic_factors}.
980 @end deffn
982 @c --- 27.07.2013 VvN ----------------------------------------------------------
983 @anchor{zn_invert_by_lu}
984 @deffn {Funktion} zn_invert_by_lu (@var{matrix}, @var{p})
986 verwendet die Technik der LR-Dekomposition, um ein modulares Inverses der
987 Matrix @var{matrix} @"uber (Z/@var{p}Z) zu berechnen. Voraussetzung ist,
988 dass @var{matrix} invertierbar und @var{p} eine Primzahl ist.
989 Sollte @var{matrix} nicht invertierbar sein, gibt @code{zn_invert_by_lu}
990 @code{false} zur@"ck.
992 Siehe auch @mref{zn_determinant}.
994 Beispiele:
996 @example
997 (%i1) m : matrix([1,3],[2,4]);
998 [ 1 3 ]
999 (%o1) [ ]
1000 [ 2 4 ]
1001 (%i2) zn_determinant(m, 5);
1002 (%o2) 3
1003 (%i3) mi : zn_invert_by_lu(m, 5);
1004 [ 3 4 ]
1005 (%o3) [ ]
1006 [ 1 2 ]
1007 (%i4) matrixmap(lambda([a], mod(a, 5)), m . mi);
1008 [ 1 0 ]
1009 (%o4) [ ]
1010 [ 0 1 ]
1011 @end example
1012 @end deffn
1014 @c --- 03.01.2020 VN -----------------------------------------------------------
1015 @anchor{zn_log}
1016 @deffn {Funktion} zn_log (@var{a}, @var{g}, @var{n})
1017 @deffnx {Funktion} zn_log (@var{a}, @var{g}, @var{n}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]])
1019 Berechnet den diskreten Logarithmus. Sei (Z/@var{n}Z)* eine zyklische Gruppe,
1020 @var{g} eine Primitivwurzel modulo @var{n} oder der Generator einer Untergruppe
1021 von (Z/@var{n}Z)* und @var{a} ein Element dieser Gruppe.
1022 Dann berechnet @code{zn_log (a, g, n)} eine L@"osung der Kongruenz
1023 @code{g^x = a mod n}. Man beachte, dass @code{zn_log} nicht terminiert,
1024 falls @var{a} keine Potenz von @var{g} modulo @var{n} ist.
1027 Der verwendete Algorithmus ben@"otigt die Primfaktorzerlegung von @code{zn_order(g)}
1028 bzw. des Totienten von @var{n}.
1029 Da diese Berechnung ebenfalls zeitaufw@"andig ist, kann es eventuell sinnvoll
1030 sein, die Primfaktoren von @code{zn_order(g)} vorab zu berechnen und @code{zn_log} als
1031 viertes Argument zu @"ubergeben. Die Form muss dabei der R@"uckgabe von
1032 @code{ifactors(totient(n))} mit der Standardeinstellung @code{false} der
1033 Optionsvariable @code{factors_only} entsprechen.
1034 Verglichen mit der Laufzeit f@"ur die Berechnung des Logarithmus hat dies jedoch nur
1035 einen recht kleinen Effekt.
1037 Als Algorithmus wird die Pohlig-Hellman-Reduktion und das Rho-Verfahren von
1038 Pollard f@"ur den diskreten Logarithmus verwendet. Die Laufzeit von @code{zn_log}
1039 h@"angt im Wesentlichen von der Bitl@"ange des gr@"o@ss{}ten Primfaktors des
1040 Totienten von @var{n} ab.
1042 Siehe auch @mref{zn_primroot}, @mref{zn_order}, @mref{ifactors}, @mref{totient}.
1044 Beispiele:
1046 @code{zn_log (a, g, n)} findet eine L@"osung der Kongruenz @code{g^x = a mod n}.
1048 @example
1049 (%i1) n : 22$
1050 (%i2) g : zn_primroot(n);
1051 (%o2) 7
1052 (%i3) ord_7 : zn_order(7, n);
1053 (%o3) 10
1054 (%i4) powers_7 : makelist(power_mod(g, x, n), x, 0, ord_7 - 1);
1055 (%o4) [1, 7, 5, 13, 3, 21, 15, 17, 9, 19]
1056 (%i5) zn_log(9, g, n);
1057 (%o5) 8
1058 (%i6) map(lambda([x], zn_log(x, g, n)), powers_7);
1059 (%o6) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1060 (%i7) ord_5 : zn_order(5, n);
1061 (%o7) 5
1062 (%i8) powers_5 : makelist(power_mod(5,x,n), x, 0, ord_5 - 1);
1063 (%o8) [1, 5, 3, 15, 9]
1064 (%i9) zn_log(9, 5, n);
1065 (%o9) 4
1066 @end example
1068 Das optionale vierte Argument muss der R@"uckgabe von @code{ifactors(totient(n))}
1069 entsprechen.
1070 Die Laufzeit h@"angt im Wesentlichen von der Bitl@"ange des gr@"o@ss{}ten
1071 Primfaktors von @code{zn_order(g)} ab.
1073 @example
1074 (%i1) (p : 2^127-1, primep(p));
1075 (%o1) true
1076 (%i2) ifs : ifactors(p - 1)$
1077 (%i3) g : zn_primroot(p, ifs);
1078 (%o3) 43
1079 (%i4) a : power_mod(g, 4711, p)$
1080 (%i5) zn_log(a, g, p, ifs);
1081 (%o5) 4711
1082 (%i6) f_max : last(ifs);
1083 (%o6) [77158673929, 1]
1084 (%i7) ord_5 : zn_order(5,p,ifs)$
1085 (%i8) (p - 1)/ord_5;
1086 (%o8) 73
1087 (%i9) ifs_5 : ifactors(ord_5)$
1088 (%i10) a : power_mod(5, 4711, p)$
1089 (%i11) zn_log(a, 5, p, ifs_5);
1090 (%o11) 4711
1091 @end example
1092 @end deffn
1094 @c -----------------------------------------------------------------------------
1095 @anchor{zn_mult_table}
1096 @deffn {Funktion} zn_mult_table (@var{n})
1097 @deffnx {Funktion} zn_mult_table (@var{n}, @var{gcd})
1099 Ohne das optionale Argument @var{gcd} zeigt @code{zn_mult_table(n)}
1100 eine Multiplikationstabelle von allen Elementen in (Z/@var{n}Z)*,
1101 d.h. von allen zu @var{n} teilerfremden Elementen.
1103 Das optionale zweite Argument @var{gcd} erlaubt es, eine bestimmte Untermenge
1104 von (Z/@var{n}Z) auszuw@"ahlen.
1105 Ist @var{gcd} eine nat@"urliche Zahl, enth@"alt die Multiplikationstabelle
1106 alle Restklassen @code{x} mit @code{gcd(x,n) = }@var{gcd}.
1107 Zur besseren Lesbarkeit werden Zeilen- und Spaltenk@"opfe hinzugef@"ugt.
1108 Falls notwendig, lassen sich diese mit @code{submatrix(1, tabelle, 1)}
1109 wieder einfach entfernen.
1111 Wird @var{gcd} auf @code{all} gesetzt, wird die Tabelle f@"ur s@"amtliche
1112 von Null verschiedene Elemente in (Z/@var{n}Z) ausgegeben.
1114 Das zweite Beispiel unten zeigt einen alternativen Weg, f@"ur Untergruppen
1115 eine Multiplikationstabelle zu erzeugen.
1117 Siehe auch @mref{zn_add_table}, @mref{zn_power_table}.
1119 Beispiele:
1121 Die Standardtabelle zeigt alle Elemente aus (Z/@var{n}Z)* und erlaubt,
1122 grundlegende Eigenschaften von modularen Multiplikationsgruppen zu zeigen und
1123 zu studieren. Z.B. stehen in der Hauptdiagonale s@"amtliche quadratische Reste,
1124 jede Zeile und Spalte enth@"alt alle Elemente, die Tabelle ist symmetrisch, etc..
1126 Wird @var{gcd} auf @code{all} gesetzt, wird die Tabelle f@"ur s@"amtliche
1127 von Null verschiedene Elemente in (Z/@var{n}Z) ausgegeben.
1129 @example
1130 (%i1) zn_mult_table(8);
1131 [ 1 3 5 7 ]
1132 [ ]
1133 [ 3 1 7 5 ]
1134 (%o1) [ ]
1135 [ 5 7 1 3 ]
1136 [ ]
1137 [ 7 5 3 1 ]
1138 (%i2) zn_mult_table(8, all);
1139 [ 1 2 3 4 5 6 7 ]
1140 [ ]
1141 [ 2 4 6 0 2 4 6 ]
1142 [ ]
1143 [ 3 6 1 4 7 2 5 ]
1144 [ ]
1145 (%o2) [ 4 0 4 0 4 0 4 ]
1146 [ ]
1147 [ 5 2 7 4 1 6 3 ]
1148 [ ]
1149 [ 6 4 2 0 6 4 2 ]
1150 [ ]
1151 [ 7 6 5 4 3 2 1 ]
1152 @end example
1154 Ist @var{gcd} eine Zahl, wird zur besseren Lesbarkeit ein Zeilen- und Spaltenkopf
1155 hinzugef@"ugt.
1157 Ist die mit @var{gcd} ausgew@"ahlte Teilmenge eine Gruppe, gibt es einen
1158 alternativen Weg, die Multiplikationstabelle zu erzeugen.
1159 Die Isomorphie zu einer Gruppe mit @code{1} als Identit@"at l@"asst sich nutzen,
1160 um eine leicht lesbare Tabelle zu erhalten. Die Abbildung gelingt mit dem CRT.
1162 In der so erzeugten zweiten Version der Tabelle @code{T36_4} steht genau wie
1163 bei @code{T9} die Identit@"at, hier @code{28}, in der linken oberen Ecke.
1166 @example
1167 (%i1) T36_4: zn_mult_table(36,4);
1168 [ * 4 8 16 20 28 32 ]
1169 [ ]
1170 [ 4 16 32 28 8 4 20 ]
1171 [ ]
1172 [ 8 32 28 20 16 8 4 ]
1173 [ ]
1174 (%o1) [ 16 28 20 4 32 16 8 ]
1175 [ ]
1176 [ 20 8 16 32 4 20 28 ]
1177 [ ]
1178 [ 28 4 8 16 20 28 32 ]
1179 [ ]
1180 [ 32 20 4 8 28 32 16 ]
1181 (%i2) T9: zn_mult_table(36/4);
1182 [ 1 2 4 5 7 8 ]
1183 [ ]
1184 [ 2 4 8 1 5 7 ]
1185 [ ]
1186 [ 4 8 7 2 1 5 ]
1187 (%o2) [ ]
1188 [ 5 1 2 7 8 4 ]
1189 [ ]
1190 [ 7 5 1 8 4 2 ]
1191 [ ]
1192 [ 8 7 5 4 2 1 ]
1193 (%i3) T36_4: matrixmap(lambda([x], chinese([0,x],[4,9])), T9);
1194 [ 28 20 4 32 16 8 ]
1195 [ ]
1196 [ 20 4 8 28 32 16 ]
1197 [ ]
1198 [ 4 8 16 20 28 32 ]
1199 (%o3) [ ]
1200 [ 32 28 20 16 8 4 ]
1201 [ ]
1202 [ 16 32 28 8 4 20 ]
1203 [ ]
1204 [ 8 16 32 4 20 28 ]
1205 @end example
1206 @end deffn
1208 @c -----------------------------------------------------------------------------
1209 @anchor{zn_nth_root}
1210 @deffn {Funktion} zn_nth_root (@var{x}, @var{n}, @var{m})
1211 @deffnx {Funktion} zn_nth_root (@var{x}, @var{n}, @var{m}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]])
1213 Gibt eine Liste mit allen @var{n}-ten Wurzeln von @var{x} aus der multiplikativen
1214 Untergruppe von (Z/@var{m}Z) zur@"uck, in der sich @var{x} befindet,
1215 oder @code{false}, falls @var{x} keine @var{n}-te Potenz modulo @var{m} oder
1216 kein Element einer multiplikativen Untergruppe von (Z/@var{m}Z) ist.
1218 @var{x} ist Element einer multiplikativen Untergruppe modulo @var{m}, wenn der
1219 gr@"o@ss{}te gemeinsame Teiler @code{g = gcd(x,m)} zu @code{m/g} teilerfremd ist.
1221 @code{zn_nth_root} basiert auf einem Algorithmus von Adleman, Manders und Miller
1222 und S@"atzen @"uber modulare Multiplikationsgruppen von Daniel Shanks.
1224 Der Algorithmus ben@"otigt eine Primfaktorzerlegung des Modulus @var{m}.
1225 Es kann eventuell sinnvoll sein, diese Zerlegung vorab zu berechnen und
1226 als viertes Argument zu @"ubergeben. Die Form muss dabei der R@"uckgabe von
1227 @code{ifactors(m)} mit der Standardeinstellung @code{false} der
1228 Optionsvariable @code{factors_only} entsprechen.
1230 Beispiele:
1232 Eine Potenztabelle der multiplikativen Gruppe modulo @code{14}
1233 gefolgt von einer Liste mit Listen von @var{n}-ten Wurzeln der @code{1},
1234 wobei @var{n} von @code{1} bis @code{6} variiert.
1236 @example
1237 (%i1) zn_power_table(14);
1238 [ 1 1 1 1 1 1 ]
1239 [ ]
1240 [ 3 9 13 11 5 1 ]
1241 [ ]
1242 [ 5 11 13 9 3 1 ]
1243 (%o1) [ ]
1244 [ 9 11 1 9 11 1 ]
1245 [ ]
1246 [ 11 9 1 11 9 1 ]
1247 [ ]
1248 [ 13 1 13 1 13 1 ]
1249 (%i2) makelist(zn_nth_root(1,n,14), n,1,6);
1250 (%o2) [[1], [1, 13], [1, 9, 11], [1, 13], [1], [1, 3, 5, 9, 11, 13]]
1251 @end example
1253 Im folgenden Beispiel ist @var{x} nicht zu @var{m} teilerfremd,
1254 aber es ist Element einer multiplikativen Untergruppe von (Z/@var{m}Z)
1255 und jede @var{n}-te Wurzel ist aus der selben Untergruppe.
1257 Die Restklasse @code{3} ist kein Element in irgend einer multiplikativen
1258 Untergruppe von (Z/63Z) und wird daher nicht als dritte Wurzel von @code{27}
1259 zur@"uck gegeben.
1261 Hier zeigt @code{zn_power_table} alle Reste @code{x} in (Z/63Z)
1262 mit @code{gcd(x,63) = 9}. Diese Untergruppe ist isomorph zu (Z/7Z)*
1263 und seine Identit@"at @code{36} wird mit Hilfe des CRT berechnet.
1265 @example
1266 (%i1) m: 7*9$
1268 (%i2) zn_power_table(m,9);
1269 [ 9 18 36 9 18 36 ]
1270 [ ]
1271 [ 18 9 36 18 9 36 ]
1272 [ ]
1273 [ 27 36 27 36 27 36 ]
1274 (%o2) [ ]
1275 [ 36 36 36 36 36 36 ]
1276 [ ]
1277 [ 45 9 27 18 54 36 ]
1278 [ ]
1279 [ 54 18 27 9 45 36 ]
1280 (%i3) zn_nth_root(27,3,m);
1281 (%o3) [27, 45, 54]
1282 (%i4) id7:1$ id63_9: chinese([id7,0],[7,9]);
1283 (%o5) 36
1284 @end example
1286 Im folgenden RSA-@"ahnlichen Beispiel, in dem der Modulus @code{N} quadratfrei ist,
1287 d.h. in paarweise verschiedene Primfaktoren zerf@"allt,
1288 ist jedes @code{x} von @code{0} bis @code{N-1}
1289 in einer multiplikativen Untergruppe enthalten.
1291 Zur Entschl@"usselung wird die @code{e}-te Wurzel berechnet.
1292 @code{e} ist teilerfremd zu @code{N} und die @code{e}-te Wurzel ist deshalb
1293 eindeutig. @code{zn_nth_root} wendet hier effektiv den als CRT-RSA
1294 bekannten Algorithmus an.
1295 (Man beachte, dass @code{flatten} Klammern entfernt und keine L@"osungen.)
1297 @example
1298 (%i1) [p,q,e]: [5,7,17]$ N: p*q$
1300 (%i3) xs: makelist(x,x,0,N-1)$
1302 (%i4) ys: map(lambda([x],power_mod(x,e,N)),xs)$
1304 (%i5) zs: flatten(map(lambda([y], zn_nth_root(y,e,N)), ys))$
1306 (%i6) is(zs = xs);
1307 (%o6) true
1308 @end example
1310 Im folgenden Beispiel ist die Faktorisierung des Modulus bekannt und wird
1311 als viertes Argument @"ubergeben.
1313 @example
1314 (%i1) p: 2^107-1$ q: 2^127-1$ N: p*q$
1316 (%i4) ibase: obase: 16$
1318 (%i5) msg: 11223344556677889900aabbccddeeff$
1320 (%i6) enc: power_mod(msg, 10001, N);
1321 (%o6) 1a8db7892ae588bdc2be25dd5107a425001fe9c82161abc673241c8b383
1322 (%i7) zn_nth_root(enc, 10001, N, [[p,1],[q,1]]);
1323 (%o7) [11223344556677889900aabbccddeeff]
1324 @end example
1325 @end deffn
1327 @c --- 29.03.2012 VN -----------------------------------------------------------
1328 @anchor{zn_order}
1329 @deffn {Funktion} zn_order (@var{x}, @var{n})
1330 @deffnx {Funktion} zn_order (@var{x}, @var{n}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]])
1332 Ist @var{x} eine Einheit in der endlichen Gruppe (Z/@var{n}Z)*, so berechnet
1333 @code{zn_order} die Ordnung dieses Elements. Andernfalls gibt @code{zn_order}
1334 @code{false} zur@"uck. @var{x} ist eine Einheit modulo @var{n}, falls @var{x}
1335 teilerfremd zu @var{n} ist.
1337 Der verwendete Algorithmus ben@"otigt die Primfaktorzerlegung des Totienten von @var{n}.
1338 Da diese Berechnung manchmal recht zeitaufw@"andig ist, kann es eventuell sinnvoll
1339 sein, die Primfaktoren des Totienten vorab zu berechnen und @code{zn_order} als
1340 drittes Argument zu @"ubergeben. Die Form muss dabei der R@"uckgabe von
1341 @code{ifactors(totient(n))} mit der Standardeinstellung @code{false} der
1342 Optionsvariable @code{factors_only} entsprechen.
1344 Siehe auch @mref{zn_primroot}, @mref{ifactors}, @mref{totient}.
1346 Beispiele:
1348 @code{zn_order} berechnet die Ordnung einer Einheit @var{x} aus (Z/@var{n}Z)*.
1350 @example
1351 (%i1) n : 22$
1352 (%i2) g : zn_primroot(n);
1353 (%o2) 7
1354 (%i3) units_22 : sublist(makelist(i,i,1,21), lambda([x], gcd(x, n) = 1));
1355 (%o3) [1, 3, 5, 7, 9, 13, 15, 17, 19, 21]
1356 (%i4) (ord_7 : zn_order(7, n)) = totient(n);
1357 (%o4) 10 = 10
1358 (%i5) powers_7 : makelist(power_mod(g,i,n), i,0,ord_7 - 1);
1359 (%o5) [1, 7, 5, 13, 3, 21, 15, 17, 9, 19]
1360 (%i6) map(lambda([x], zn_order(x, n)), powers_7);
1361 (%o6) [1, 10, 5, 10, 5, 2, 5, 10, 5, 10]
1362 (%i7) map(lambda([x], ord_7/gcd(x, ord_7)), makelist(i, i,0,ord_7 - 1));
1363 (%o7) [1, 10, 5, 10, 5, 2, 5, 10, 5, 10]
1364 (%i8) totient(totient(n));
1365 (%o8) 4
1366 @end example
1368 Das optionale dritte Argument muss der R@"uckgabe von @code{ifactors(totient(n))}
1369 entsprechen.
1371 @example
1372 (%i1) (p : 2^142 + 217, primep(p));
1373 (%o1) true
1374 (%i2) ifs : ifactors( totient(p) )$
1375 (%i3) g : zn_primroot(p, ifs);
1376 (%o3) 3
1377 (%i4) is( (ord_3 : zn_order(g, p, ifs)) = totient(p) );
1378 (%o4) true
1379 (%i5) map(lambda([x], ord_3/zn_order(x, p, ifs)), makelist(i,i,2,15));
1380 (%o5) [22, 1, 44, 10, 5, 2, 22, 2, 8, 2, 1, 1, 20, 1]
1381 @end example
1382 @end deffn
1384 @c -----------------------------------------------------------------------------
1385 @anchor{zn_power_table}
1386 @deffn {Funktion} zn_power_table (@var{n})
1387 @deffnx {Funktion} zn_power_table (@var{n}, @var{gcd})
1388 @deffnx {Funktion} zn_power_table (@var{n}, @var{gcd}, @var{max_exp})
1390 Ohne ein optionales Argument zeigt @code{zn_power_table(n)}
1391 eine Potenzierungstabelle von allen Elementen in (Z/@var{n}Z)*,
1392 d.h. von allen zu @var{n} teilerfremden Elementen.
1393 Der Exponent variiert dabei jeweils zwischen @code{1} und
1394 dem gr@"o@ss{}ten charakteristischen Faktor des Totienten von @var{n}
1395 (auch bekannt als Carmichael Funktion bzw. Carmichael Lambda),
1396 so dass die Tabelle rechts mit einer Spalte von Einsen endet.
1398 Das optionale zweite Argument @var{gcd} erlaubt es, eine bestimmte Untermenge
1399 von (Z/@var{n}Z) auszuw@"ahlen.
1400 Ist @var{gcd} eine nat@"urliche Zahl, werden Potenzen von allen Restklassen
1401 @code{x} mit @code{gcd(x,n) = }@var{gcd} zur@"uck gegeben,
1402 d.h. @var{gcd} ist standardm@"a@ss{}ig @code{1}.
1403 Wird @var{gcd} auf @code{all} gesetzt, wird die Tabelle f@"ur s@"amtliche
1404 Elemente in (Z/@var{n}Z) ausgegeben.
1406 Wird das optionale dritte Argument @var{max_exp} angegeben, variiert der
1407 Exponent zwischen @code{1} und @var{max_exp}.
1409 Siehe auch @mref{zn_add_table}, @mref{zn_mult_table}.
1411 Beispiele:
1413 Die Standardeinstellung @var{gcd}@code{ = 1} erlaubt es, grundlegende S@"atze,
1414 wie die von Fermat and Euler, zu zeigen und zu betrachten.
1416 Das Argument @var{gcd} erlaubt es, bestimmte Teilmengen von (Z/@var{n}Z)
1417 auszuw@"ahlen und multiplikative Untergruppen und Isomorphismen zu untersuchen.
1419 Z.B. sind die Gruppen @code{G10} und @code{G10_2} unter der Multiplikation
1420 beide isomorph zu @code{G5}. @code{1} ist die Identit@"at in @code{G5}.
1421 So sind @code{1} bzw. @code{6} die Identit@"aten in @code{G10} bzw. @code{G10_2}.
1422 Entsprechende Zuordnungen ergeben sich bei den Primitivwurzeln, n-ten Wurzeln, etc..
1424 @example
1425 (%i1) zn_power_table(10);
1426 [ 1 1 1 1 ]
1427 [ ]
1428 [ 3 9 7 1 ]
1429 (%o1) [ ]
1430 [ 7 9 3 1 ]
1431 [ ]
1432 [ 9 1 9 1 ]
1433 (%i2) zn_power_table(10,2);
1434 [ 2 4 8 6 ]
1435 [ ]
1436 [ 4 6 4 6 ]
1437 (%o2) [ ]
1438 [ 6 6 6 6 ]
1439 [ ]
1440 [ 8 4 2 6 ]
1441 (%i3) zn_power_table(10,5);
1442 (%o3) [ 5 5 5 5 ]
1443 (%i4) zn_power_table(10,10);
1444 (%o4) [ 0 0 0 0 ]
1445 (%i5) G5: [1,2,3,4];
1446 (%o6) [1, 2, 3, 4]
1447 (%i6) G10_2: map(lambda([x], chinese([0,x],[2,5])), G5);
1448 (%o6) [6, 2, 8, 4]
1449 (%i7) G10: map(lambda([x], power_mod(3, zn_log(x,2,5), 10)), G5);
1450 (%o7) [1, 3, 7, 9]
1451 @end example
1453 Wird @var{gcd} auf @code{all} gesetzt, wird die Tabelle f@"ur s@"amtliche
1454 Elemente in (Z/@var{n}Z) ausgegeben.
1456 Das dritte Argument @var{max_exp} erlaubt, den h@"ochsten Exponenten zu w@"ahlen.
1457 Die folgende Tabelle zeigt ein kleines RSA-Beispiel.
1459 @example
1460 (%i1) N:2*5$ phi:totient(N)$ e:7$ d:inv_mod(e,phi)$
1462 (%i5) zn_power_table(N, all, e*d);
1463 [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
1464 [ ]
1465 [ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ]
1466 [ ]
1467 [ 2 4 8 6 2 4 8 6 2 4 8 6 2 4 8 6 2 4 8 6 2 ]
1468 [ ]
1469 [ 3 9 7 1 3 9 7 1 3 9 7 1 3 9 7 1 3 9 7 1 3 ]
1470 [ ]
1471 [ 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 6 4 ]
1472 (%o5) [ ]
1473 [ 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ]
1474 [ ]
1475 [ 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 ]
1476 [ ]
1477 [ 7 9 3 1 7 9 3 1 7 9 3 1 7 9 3 1 7 9 3 1 7 ]
1478 [ ]
1479 [ 8 4 2 6 8 4 2 6 8 4 2 6 8 4 2 6 8 4 2 6 8 ]
1480 [ ]
1481 [ 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 ]
1482 @end example
1483 @end deffn
1485 @c --- 29.03.2012 VN -----------------------------------------------------------
1486 @anchor{zn_primroot}
1487 @deffn {Funktion} zn_primroot (@var{n})
1488 @deffnx {Funktion} zn_primroot (@var{n}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]])
1490 Ist die multiplikative Gruppe (Z/@var{n}Z)* zyklisch, berechnet @code{zn_primroot}
1491 die kleinste Primitivwurzel modulo @var{n}. Dies ist der Fall, wenn @var{n} gleich
1492 @code{2}, @code{4}, @code{p^k} oder @code{2*p^k} ist, wobei @code{p} ungerade und
1493 prim und @code{k} eine nat@"urliche Zahl ist. @code{zn_primroot}
1494 f@"uhrt einen entsprechenden Pr@"atest durch, wenn die Optionsvariable
1495 @mref{zn_primroot_pretest} (Standardwert: @code{false}) @code{true} gesetzt wurde.
1496 In jedem Fall wird die Suche durch die obere Schranke @mref{zn_primroot_limit} begrenzt.
1498 Ist (Z/@var{n}Z)* nicht zyklisch oder kann bis @code{zn_primroot_limit}
1499 keine Primitivwurzel modulo @var{n} gefunden werden, gibt @code{zn_primroot}
1500 @code{false} zur@"uck.
1502 Der verwendete Algorithmus ben@"otigt die Primfaktorzerlegung des Totienten von @var{n}.
1503 Diese Berechnung kann zeitaufw@"andig sein und es kann daher eventuell sinnvoll
1504 sein, die Primfaktoren des Totienten vorab zu berechnen und @code{zn_primroot}
1505 als zus@"atzliches Argument zu @"ubergeben. Die Form muss dabei der R@"uckgabe
1506 von @code{ifactors(totient(n))} mit der Standardeinstellung @code{false} der
1507 Optionsvariable @code{factors_only} entsprechen.
1509 Siehe auch @mref{zn_primroot_p}, @mref{zn_order}, @mref{ifactors}, @mref{totient}.
1511 Beispiele:
1513 @code{zn_primroot} berechnet die kleinste Primitivwurzel modulo @var{n} oder gibt
1514 @code{false} zur@"uck.
1516 @example
1517 (%i1) n : 14$
1518 (%i2) g : zn_primroot(n);
1519 (%o2) 3
1520 (%i3) zn_order(g, n) = totient(n);
1521 (%o3) 6 = 6
1522 (%i4) n : 15$
1523 (%i5) zn_primroot(n);
1524 (%o5) false
1525 @end example
1527 Das optionale zweite Argument muss der R@"uckgabe von @code{ifactors(totient(n))}
1528 entsprechen.
1530 @example
1531 (%i1) (p : 2^142 + 217, primep(p));
1532 (%o1) true
1533 (%i2) ifs : ifactors( totient(p) )$
1534 (%i3) g : zn_primroot(p, ifs);
1535 (%o3) 3
1536 (%i4) [time(%o2), time(%o3)];
1537 (%o4) [[15.556972], [0.004]]
1538 (%i5) is(zn_order(g, p, ifs) = p - 1);
1539 (%o5) true
1540 (%i6) n : 2^142 + 216$
1541 (%i7) ifs : ifactors(totient(n))$
1542 (%i8) zn_primroot(n, ifs),
1543 zn_primroot_limit : 200, zn_primroot_verbose : true;
1544 `zn_primroot' stopped at zn_primroot_limit = 200
1545 (%o8) false
1546 @end example
1547 @end deffn
1549 @c --- 23.03.2013 VN -----------------------------------------------------------
1550 @anchor{zn_primroot_limit}
1551 @defvr {Optionsvariable} zn_primroot_limit
1552 Standardwert: @code{1000}
1554 Definiert die obere Schranke f@"ur die Suche von @mref{zn_primroot} nach einer
1555 Primitivwurzel. Wurde die Optionsvariable @mref{zn_primroot_verbose}
1556 (Standardwert: @code{false}) @code{true} gesetzt, wird beim Erreichen von
1557 @code{zn_primroot_limit} ein entsprechender Hinweis ausgegeben.
1558 @end defvr
1560 @c --- 29.03.2012 VN -----------------------------------------------------------
1561 @anchor{zn_primroot_p}
1562 @deffn {Funktion} zn_primroot_p (@var{x}, @var{n})
1563 @deffnx {Funktion} zn_primroot_p (@var{x}, @var{n}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]])
1565 Testet, ob @var{x} eine Primitivwurzel in der multiplikativen Gruppe (Z/@var{n}Z)*
1566 ist.
1568 Der verwendete Algorithmus ben@"otigt die Primfaktorzerlegung des Totienten von
1569 @var{n}. Wird dieser Test nacheinander auf mehrere Zahlen angewandt,
1570 kann es sinnvoll sein, die Primfaktoren des Totienten vorab zu berechnen
1571 und @code{zn_primroot_p} als zus@"atzliches drittes Argument zu @"ubergeben.
1572 Die Form muss dabei der R@"uckgabe von @code{ifactors(totient(n))} mit der
1573 Standardeinstellung @code{false} der Optionsvariable @code{factors_only}
1574 entsprechen.
1576 Siehe auch @mref{zn_primroot}, @mref{zn_order}, @mref{ifactors}, @mref{totient}.
1578 Beispiele:
1580 @code{zn_primroot_p} als Pr@"adikatfunktion.
1582 @example
1583 (%i1) n : 14$
1584 (%i2) units_14 : sublist(makelist(i,i,1,13), lambda([i], gcd(i, n) = 1));
1585 (%o2) [1, 3, 5, 9, 11, 13]
1586 (%i3) zn_primroot_p(13, n);
1587 (%o3) false
1588 (%i4) sublist(units_14, lambda([x], zn_primroot_p(x, n)));
1589 (%o4) [3, 5]
1590 (%i5) map(lambda([x], zn_order(x, n)), units_14);
1591 (%o5) [1, 6, 6, 3, 3, 2]
1592 @end example
1594 Das optionale dritte Argument muss der R@"uckgabe von @code{ifactors(totient(n))}
1595 entsprechen.
1597 @example
1598 (%i1) (p : 2^142 + 217, primep(p));
1599 (%o1) true
1600 (%i2) ifs : ifactors( totient(p) )$
1601 (%i3) sublist(makelist(i,i,1,50), lambda([x], zn_primroot_p(x, p, ifs)));
1602 (%o3) [3, 12, 13, 15, 21, 24, 26, 27, 29, 33, 38, 42, 48]
1603 (%i4) [time(%o2), time(%o3)];
1604 (%o4) [[7.748484], [0.036002]]
1605 @end example
1606 @end deffn
1608 @c --- 23.03.2013 VN -----------------------------------------------------------
1609 @anchor{zn_primroot_pretest}
1610 @defvr {Optionsvariable} zn_primroot_pretest
1611 Standardwert: @code{false}
1613 Eine multiplikative Gruppe (Z/@code{n}Z)* ist zyklisch, wenn @code{n} gleich
1614 @code{2}, @code{4}, @code{p^k} oder @code{2*p^k} ist, wobei @code{p} prim und
1615 gr@"o@ss{}er @code{2} und @code{k} eine nat@"urliche Zahl ist.
1617 @code{zn_primroot_pretest} entscheidet dar@"uber, ob @mref{zn_primroot} vor
1618 der Berechnung der kleinsten Primitivwurzel in (Z/@code{n}Z)* @"uberpr@"uft,
1619 ob auf @code{n} @"uberhaupt einer der oben genannten F@"alle zutrifft. Nur wenn
1620 @code{zn_primroot_pretest} @code{true} ist, wird dieser Pr@"atest ausgef@"uhrt.
1621 @end defvr
1623 @c --- 23.03.2013 VN -----------------------------------------------------------
1624 @anchor{zn_primroot_verbose}
1625 @defvr {Optionsvariable} zn_primroot_verbose
1626 Standardwert: @code{false}
1628 Entscheidet, ob @mref{zn_primroot} beim Erreichen von @mref{zn_primroot_limit}
1629 einen Hinweis ausgibt.
1630 @end defvr
1632 @c --- End of file Number.de.texi