I would like to commit to src/numth.lisp some new functions:
zn_primroot(n): find the smallest generator of (Z/nZ)*
zn_primroot_p(x, n): check, if x is a generator of (Z/nZ)*
zn_order(x, n): compute the order of x in (Z/nZ)*
zn_log(a, g, n): discrete logarithm: solve g^x = a in (Z/nZ)*
chinese(rems, mods): chinese remainder theorem
where n is not necessarily prime. Most of the function names I have taken
from pari/gp.
The discrete logarithm is a very time consuming computation and at least
with CLISP and GCL it will benefit from being compiled in src.
The timing results are not too bad. Compared to pari/gp a little bit
slower, but compared to the existing Galois Fields package in share
incredibly fast.
If there are no objections I will go ahead and also add the according
documentation in German and English.
In the next months I plan to revise the Galois Fields package.
Greetings
Volker van Nek