Opened 10 years ago
Last modified 5 years ago
#6467 needs_work enhancement
[with patch, needs work] all primitive roots modulo n
Reported by: | mvngu | Owned by: | was |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | number theory | Keywords: | primitive roots, generators mod n |
Cc: | kcrisman | Merged in: | |
Authors: | Minh Van Nguyen | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
For a fixed positive integer n, compute a list of all the primitive roots modulo n. Sage currently can compute one primitive root modulo n, but not all of them.
Attachments (1)
Change History (9)
comment:1 Changed 10 years ago by
- Milestone set to sage-4.1.1
- Summary changed from all primitive roots modulo n to [with patch, needs review] all primitive roots modulo n
comment:2 Changed 10 years ago by
- Summary changed from [with patch, needs review] all primitive roots modulo n to [with patch, needs work] all primitive roots modulo n
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
comment:3 Changed 10 years ago by
Oops, by IntegerRing_class.multiplicative_group_is_cyclic()
I meant IntegerModRing_generic.multiplicative_group_is_cyclic()
, in sage.rings.integer_mod_ring
. Sorry.
comment:4 Changed 9 years ago by
- Cc kcrisman added
- Report Upstream set to N/A
comment:5 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:6 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:7 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:8 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
Note: See
TracTickets for help on using
tickets.
The patch
trac_6467.patch
adds two functions tosage/rings/arith.py
for calculating all the primitive roots modulo a fixed integer n:primitive_roots()
--- Return all the generators for the multiplicative group of integers modulo a positive integer n. Where n is a positive composite integer, the function uses a naive method that is inefficient, since I do not know of a better method. If n is a positive prime integer, then use the functionprimitive_roots_prime()
.primitive_roots_prime()
--- Return all the generators for the multiplicative group of integers modulo a positive prime p. Again, this uses an inefficient method since I'm not aware of a better way.