From: Volker v. N. <va...@us...> - 2013-12-14 15:56:39
|
This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Maxima CAS". The branch, master has been updated via 2a66fe4ae2cdd064f22c492b26a99b310655646c (commit) from fa8fa5c9e238e3f38c581827ae1a61d9e948eedb (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 2a66fe4ae2cdd064f22c492b26a99b310655646c Author: Volker van Nek <vol...@gm...> Date: Sat Dec 14 16:56:01 2013 +0100 introducing Shanks chracteristic factors in zn and improving zn_power_table diff --git a/doc/info/Number.texi b/doc/info/Number.texi index 0fe5f5a..23e1ec1 100644 --- a/doc/info/Number.texi +++ b/doc/info/Number.texi @@ -1171,12 +1171,13 @@ The optional third argument must be of the same form as the list returned by Without the optional argument @var{all} @code{zn_power_table(n)} shows a power table of all elements in (Z/@var{n}Z)* which are all elements invertible modulo @var{n}. -The exponent loops from @code{1} to @code{totient(n)} and the table ends with -a column of ones on the right side. +The exponent loops from @code{1} to the greatest characteristic factor of +@code{totient(n)} and the table ends with a column of ones on the right side. The optional argument @var{all} causes the table to be printed for all -non-zero elements. In this case the exponent loops from @code{1} to -@code{totient(n) + 1} and the last column is therefore equal to the first. +non-zero elements. The exponent now loops from @code{1} to +@code{totient(n) + 1} and in case the modulus factors into two different primes +the last column is equal to the first. See also @mref{zn_add_table}, @mref{zn_mult_table}. diff --git a/doc/info/de/Number.de.texi b/doc/info/de/Number.de.texi index ee29353..7173a60 100644 --- a/doc/info/de/Number.de.texi +++ b/doc/info/de/Number.de.texi @@ -1055,13 +1055,15 @@ entsprechen. Ohne das optionale Argument @var{all} zeigt @code{zn_power_table(n)} eine Potenzierungstabelle von allen Elementen in (Z/@var{n}Z)*, d.h. von allen modulo @var{n} invertierbaren Elementen. -Der Exponent @var{n} variiert jeweils zwischen @code{1} und @code{totient(n)}, +Der Exponent variiert dabei jeweils zwischen @code{1} und +dem gr@"o@ss{}ten charakteristischen Faktor des Totienten von @var{n}, so dass die Tabelle rechts mit einer Spalte von Einsen endet. Das optionale Argument @var{all} bewirkt, dass die Tabelle f@"ur alle von Null verschiedenen Elemente gezeigt wird. In diesem Fall -variiert der Exponent @var{n} zwischen @code{1} und @code{totient(n) + 1}. -Die erste und letzte Spalte stimmen dadurch @"uberein. +variiert der Exponent zwischen @code{1} und @code{totient(n) + 1}. +Ist der Modulus aus zwei Primzahlen zusammen gesetzt, stimmen dann +die erste und letzte Spalte @"uberein. Siehe auch @mref{zn_add_table}, @mref{zn_mult_table}. @@ -1092,8 +1094,8 @@ Beispiele: Ist die multiplikative Gruppe (Z/@var{n}Z)* zyklisch, berechnet @code{zn_primroot} die kleinste Primitivwurzel modulo @var{n}. Dies ist der Fall, wenn @var{n} gleich -@code{2}, @code{4}, @code{p^k} oder @code{2*p^k} ist, wobei @code{p} prim und -gr@"osser @code{2} und @code{k} eine nat@"urliche Zahl ist. @code{zn_primroot} +@code{2}, @code{4}, @code{p^k} oder @code{2*p^k} ist, wobei @code{p} ungerade und +prim und @code{k} eine nat@"urliche Zahl ist. @code{zn_primroot} f@"uhrt einen entsprechenden Pr@"atest durch, wenn die Optionsvariable @mref{zn_primroot_pretest} (Standardwert: @code{false}) @code{true} gesetzt wurde. In jedem Fall wird die Suche durch die obere Schranke @mref{zn_primroot_limit} begrenzt. diff --git a/src/numth.lisp b/src/numth.lisp index 3b6589b..650e900 100644 --- a/src/numth.lisp +++ b/src/numth.lisp @@ -571,6 +571,59 @@ (values (mod (* g b) n) (mod (+ y 1) ord) z ) ) ))) +;; characteristic factors: + +(defmfun $zn_characteristic_factors (m) + (unless (integerp m) + (gf-merror (intl:gettext "`zn_characteristic_factors': Argument must be an integer.")) ) + (cons '(mlist simp) (zn-characteristic-factors m)) ) + +;; D. Shanks - Solved and unsolved problems in number theory, 2. ed +;; definition 29 and 30 (p. 92 - 94) +;; +;; (zn-characteristic-factors 104) --> (2 2 12) +;; => Z104* is isomorphic to M2 x M2 x M12 +;; the direct product of modulo multiplication groups of order 2 resp. 12 +;; +(defun zn-characteristic-factors (m) + (let* (($intfaclim) + (pe-list (get-factor-list m)) ;; def. 29 part A + (shanks-phi ;; part D + (sort + (apply #'nconc (mapcar #'zn-shanks-phi-step-bc pe-list)) + #'zn-pe> ))) + ;; def. 30 : + (do ((todo shanks-phi (nreverse left)) + (p 0 0) (f 1 1) (left nil nil) + fs q d ) + ((null todo) fs) + (dolist (qd todo) + (setq q (car qd) d (cadr qd)) + (if (= q p) + (push qd left) + (setq p q f (* f (expt q d))) )) + (push f fs) ))) + +;; definition 29 parts B,C (p. 92) +(defun zn-shanks-phi-step-bc (pe) + (let ((p (car pe)) (e (cadr pe)) qd) + (cond + ((= 2 p) + (setq qd (list '(2 1))) + (when (> e 2) + (setq qd (nconc qd (list `(2 ,(- e 2))))) )) + (t + (setq qd (let (($intfaclim)) (get-factor-list (1- p)))) + (when (> e 1) + (setq qd (nconc qd (list `(,p ,(1- e))))) ))) + qd )) + +(defun zn-pe> (a b) + (cond ((> (car a) (car b)) t) + ((< (car a) (car b)) nil) + (t (> (cadr a) (cadr b))) )) + + ;; for educational puposes: tables of small residue class rings (defun zn-table-errchk (n fun) @@ -608,13 +661,14 @@ (defmfun $zn_power_table (n &optional all?) (zn-table-errchk n "zn_power_table") - (let ((tn ($totient n))) - (when (equal all? '$all) (incf tn)) + (let ((jj (if (equal all? '$all) + (1+ ($totient n)) + (car (last (zn-characteristic-factors n))) ))) (do ((i 1 (1+ i)) res) ((= i n) (cons '($matrix simp) (nreverse res)) ) (when (or (equal all? '$all) (= 1 (gcd i n))) - (push (mfuncall '$makelist `(power-mod ,i $j ,n) '$j 1 tn) res) )))) + (push (mfuncall '$makelist `(power-mod ,i $j ,n) '$j 1 jj) res) )))) ;; $zn_invert_by_lu (m p) ----------------------------------------------------------------------- Summary of changes: doc/info/Number.texi | 9 +++--- doc/info/de/Number.de.texi | 12 +++++--- src/numth.lisp | 60 +++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 69 insertions(+), 12 deletions(-) hooks/post-receive -- Maxima CAS |