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: |
Description (last modified by )
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)
Change History (13)
comment:1 Changed 10 years ago by
- Cc kcrisman added
- Report Upstream set to N/A
comment:2 Changed 8 years ago by
- Status changed from new to needs_review
comment:3 Changed 8 years ago by
- 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
- 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
# 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
comment:6 Changed 8 years ago by
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
Fixes single line in self.is_primitive_root() to make compatible with new 12116.patch
comment:7 Changed 8 years ago by
- 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:9 Changed 8 years ago by
Please clarify which patch(es) must be applied.
comment:10 Changed 8 years ago by
- Description modified (diff)
comment:11 Changed 8 years ago by
- Merged in set to sage-5.8.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
Review anyone?