Opened 12 years ago

# [with patch, needs work] all primitive roots modulo n

Reported by: Owned by: mvngu was major sage-6.4 number theory primitive roots, generators mod n kcrisman Minh Van Nguyen N/A

### 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.

### comment:1 Changed 12 years ago by mvngu

• Authors set to Minh Van Nguyen
• 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

The patch `trac_6467.patch` adds two functions to `sage/rings/arith.py` for calculating all the primitive roots modulo a fixed integer n:

1. `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 function `primitive_roots_prime()`.
2. `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.

### Changed 12 years ago by mvngu

based on Sage 4.1.rc0

### comment:2 Changed 12 years ago by davidloeffler

• 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 gk 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 pk if and only if it's a primitive root mod p (and g is a primitive root mod 2 * pk 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 12 years ago by davidloeffler

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 10 years ago by kcrisman

• Report Upstream set to N/A

### comment:5 Changed 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:6 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:7 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:8 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.