#6467: [with patch, needs work] all primitive roots modulo n
---------------------------+------------------------------------------------
Reporter: mvngu | Owner: was
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.1.1
Component: number theory | Keywords: primitive roots, generators mod n
Reviewer: | Author: Minh Van Nguyen
Merged: |
---------------------------+------------------------------------------------
Comment(by davidloeffler):
I'm not totally convinced by this.
- The function {{{primitive_roots_prime}}} shouldn't be exported to the
global namespace. At present *everything* in sage/rings/arith is exported,
which (to me) suggests moving the innards of this function to methods of
the IntegerModRing class.
- There is already a method
{{{IntegerRing_class.multiplicative_group_is_cyclic()}}} which you can use
to find out if a primitive root exists -- I fixed a bug in it not long
back. Asking for a primitive root and then catching the exception if one
isn't found is a bit ugly, besides being much slower.
- For a prime modulus p, you take a primitive root g, then compute g^k^
for each k in 1...phi(p). It would be more efficient to have a variable
that is initialised to 1 and then multiplied by g (mod p) each time,
avoiding the separate power_mod call.
- The algorithm in the composite case can be *massively* improved using
two simple observations: (1) there are no primitive roots mod n unless n
is < 8, an odd prime power, or twice an odd prime power; and (2) if n is
an odd prime power then g is a primitive root mod p^k^ if and only if it's
a primitive root mod p (and g is a primitive root mod 2 * p^k^ iff g is a
primitive root mod p and g is odd).
(At a rough guess your current algorithm is running in time about N^{3/2}
times a power of log; this observation will speed it up to N * power of
log.)
David
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6467#comment:2>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
