Subject: computing generating elements of ZZ_p^* ?
From: Volker van Nek
Date: Fri, 21 Oct 2011 10:24:18 +0200
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*.
Let us see what elements of z7* the number 3 can generate:
(%i3) (z7:set(), for i:1 thru 6 do z7:adjoin(power_mod(3,i,7), z7), z7);
(%o3) {1, 2, 3, 4, 5, 6}
The same test for number 2:
(%i4) (z7:set(), for i:1 thru 6 do z7:adjoin(power_mod(2,i,7), z7), z7);
(%o4) {1, 2, 4}
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.
(%i6) for i:1 thru 6 do if primrootp(i, 7) then print(i);
3
5
(%o6) done
primrootp has to compute the prime factors of 6. To be more efficient in
repeated computation it is possible to pass this list of factors to
primrootp:
(%i7) factors: ifactors(6), factors_only: true;
(%o7) [2, 3]
(%i8) for i:1 thru 6 do if primrootp(i, 7, factors) then print(i);
3
5
(%o8) done
Volker van Nek
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
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: primroot.lisp
Type: application/octet-stream
Size: 2095 bytes
Desc: not available
URL: <http://www.math.utexas.edu/pipermail/maxima/attachments/20111021/88ed166e/attachment-0001.obj>;