computing generating elements of ZZ_p^* ?

Hi Volker,

On Fri, Oct 21, 2011 at 10:24:18AM +0200, Volker van Nek wrote:
> I attached a lisp file which allows the following session. Maybe that is
> what you are looking for.
> (%i1) load("~/Maxima/primroot.lisp")$
> contains 3 functions at Maxima-level: euler_phi, primroot, primrootp
> (%i2) primroot(7);
> (%o2)                                  3
> primroot searches for the smallest primitive root in z7*.
> The number of primitive roots in z7*:
> (%i5) euler_phi(6);
> (%o5)                                  2
> primrootp allows to find all primitive roots. It checks if a given number is
> a primitive root.
> 
>

Thanks a lot. Just a few remarks:
 - euler_phi is also directly in Maxima, as "totient"; seems to have
   the same run-time.
 - One doesn't need to restrict the approach to prime p, but can consider
   all natural numbers n for which the multiplicative group ZZ_n^*
   is cyclic, i.e., there exists a primitive root modulo n, where additionally
   to n=p (p prime) one than can allow n=4,p^k,2*p^k for p > 2 (p prime).
 - Implementing the functionality (generalised to all possible n) directly
   in Maxima seems to have the same run-time, except that at least under Ecl
   the run-time fluctuations are enormous.

Just to mention, for the records.

Regards

Oliver

> 2011/10/21 Oliver Kullmann <O.Kullmann at swansea.ac.uk>
> 
> > Hello,
> >
> > I wonder whether Maxima contains the following functionality (couldn't
> > find it):
> >
> > Let p be a prime number, and consider the residual field ZZ_p (residual
> > classes modulo p with modular addition and multiplication).
> > ZZ_p^* = {1,...,p-1} together with the multiplication is a cyclic group:
> > now what is needed is a test to determine whether an element i is a
> > generating
> > element --- is this somehow in Maxima?
> >
> > Thanks for your attention.
> >
> > Oliver
> >
> > _______________________________________________
> > Maxima mailing list
> > Maxima at math.utexas.edu
> > http://www.math.utexas.edu/mailman/listinfo/maxima
> >



-- 
Dr. Oliver Kullmann
Department of Computer Science
College of Science, Swansea University
Faraday Building, Singleton Park
Swansea SA2 8PP, UK
http://cs.swan.ac.uk/~csoliver/