Opened 9 years ago

Last modified 4 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)

trac_6467.patch (7.2 KB) - added by mvngu 9 years ago.
based on Sage 4.1.rc0

Download all attachments as: .zip

Change History (9)

comment:1 Changed 9 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 9 years ago by mvngu

based on Sage 4.1.rc0

comment:2 Changed 9 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 9 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 7 years ago by kcrisman

  • Cc kcrisman added
  • Report Upstream set to N/A

comment:5 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 4 years ago by vbraun_spam

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