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

[sagetrac-mvngu]

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 attachment: 6567_2.patch

Depends on #12116

CC: @kcrisman

Component: number theory

Keywords: primitive roots

Author: David Roe

Reviewer: Julian Rueth, Simon Spicer

Merged: sage-5.8.beta3

Issue created by migration from https://trac.sagemath.org/ticket/6567

[roed314]

comment:2

Review anyone?

[roed314]

Author: David Roe

[saraedum]

comment:3

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)):'

[saraedum]

Reviewer: Julian Rueth

[roed314]

comment:4

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

[roed314]

Dependencies: #12116

[kcrisman]

comment:5

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

[roed314]

Attachment: 6567.patch.gz

[roed314]

comment:6

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.

[haikona]

Attachment: 6567_2.patch.gz

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

[haikona]

Changed reviewer from Julian Rueth to Julian Rueth, Simon Spicer

[haikona]

comment:7

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.

[roed314]

comment:8

Fine with me.

[jdemeyer]

comment:9

Please clarify which patch(es) must be applied.

[jdemeyer]

Merged: sage-5.8.beta3