Opened 12 years ago

Closed 8 years ago

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

Reported by: Owned by: mvngu was major sage-5.8 number theory primitive roots kcrisman sage-5.8.beta3 David Roe Julian Rueth, Simon Spicer N/A #12116

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

comment:1 Changed 10 years ago by kcrisman

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

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.