Opened 12 years ago

Closed 8 years ago

#6567 closed enhancement (fixed)

function to test whether or not some integer is a primitive root modulo n

Reported by: mvngu Owned by: was
Priority: major Milestone: sage-5.8
Component: number theory Keywords: primitive roots
Cc: kcrisman Merged in: sage-5.8.beta3
Authors: David Roe Reviewers: Julian Rueth, Simon Spicer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12116 Stopgaps:

Status badges

Description (last modified by roed)

Currently, the function primitive_root() finds a primitive root modulo n. Ticket #6467 proposes to find all primitive roots modulo a fixed n. We should also implement a function to determine whether or not some integer is a primitive root modulo n. A good way is to do this without first having to generate all primitive roots mod n.

Apply 6567_2.patch

Attachments (2)

6567.patch (7.2 KB) - added by roed 8 years ago.
6567_2.patch (7.2 KB) - added by spice 8 years ago.
Fixes single line in self.is_primitive_root() to make compatible with new 12116.patch

Download all attachments as: .zip

Change History (13)

comment:1 Changed 10 years ago by kcrisman

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

comment:2 Changed 8 years ago by roed

  • Authors set to David Roe
  • Status changed from new to needs_review

Review anyone?

comment:3 Changed 8 years ago by saraedum

  • Reviewers set to Julian Rueth
  • Status changed from needs_review to needs_work

There is a problem in the docstring:

Traceback (most recent call last):
  File "/dev/shm/sage_testdir/integer_mod_10415.py", line 3096, in <module>
    runner=runner)
  File "/dev/shm/sage/local/bin/sagedoctest.py", line 54, in testmod_returning_runner
    runner=runner)
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 1819, in testmod_returning_runner
    for test in finder.find(m, name, globs=globs, extraglobs=extraglobs):
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 839, in find
    self._find(tests, obj, name, module, source_lines, globs, {})
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 893, in _find
    globs, seen)
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 881, in _find
    test = self._get_test(obj, name, module, globs, source_lines)
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 965, in _get_test
    filename, lineno)
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 594, in get_doctest
    return DocTest(self.get_examples(string, name), globs,
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 608, in get_examples
    return [x for x in self.parse(string, name)
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 570, in parse
    self._parse_example(m, name, lineno)
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 628, in _parse_example
    self._check_prompt_blank(source_lines, indent, name, lineno)
  File "/dev/shm/sage/local/bin/ncadoctest.py", line 715, in _check_prompt_blank
    line[indent:indent+3], line))
ValueError: line 27 of the docstring for __main__.example_32 lacks blank after ...: '            ....:     for k in range(Integer(1),Integer(4)):'

comment:4 Changed 8 years ago by roed

  • Dependencies set to #12116
  • Status changed from needs_work to needs_review

The doctesting error was due to depending on syntax only valid after #12415. Since I don't want to wait on that, I've updated the doctest (and also marked the dependency correctly).

comment:5 Changed 8 years ago by kcrisman

# self**(p**k*(p-1)//q) = 1 for some q 

Should that be k-1? I'd also put it "# now self..." just to make it clear

Everything else looks nice. I feel like I want to check the logic for numbers divisible by 2, 3, or 5 but where start > 5 a little more closely (getting late here) but if someone else does that first that is fine.

Changed 8 years ago by roed

comment:6 Changed 8 years ago by roed

I'm not quite sure what you meant by the "# now self..." but I made some change along those lines. I'm also not sure why patchbot was giving me a failure in applying. Hopefully the new patch won't have the same problem.

Changed 8 years ago by spice

Fixes single line in self.is_primitive_root() to make compatible with new 12116.patch

comment:7 Changed 8 years ago by spice

  • Reviewers changed from Julian Rueth to Julian Rueth, Simon Spicer

Patch applies, but with the (proposed) change to #12116 - swapping the order integers returned by perfect_power() so that (a^b).perfect_power() returns (a,b) and not (b,a) - the code breaks on perfect powers or twice perfect powers. A simple single line change fixes this; I've uploaded a new patch with this fix. Line 1485 goes from

k, p = odd.perfect_power() 

to

p, k = odd.perfect_power() 

Everything else is good.

comment:8 Changed 8 years ago by roed

  • Status changed from needs_review to positive_review

Fine with me.

comment:9 Changed 8 years ago by jdemeyer

Please clarify which patch(es) must be applied.

comment:10 Changed 8 years ago by roed

  • Description modified (diff)

comment:11 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.8.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.