#10836: primitive root is broken
-----------------------------+----------------------------------------------
Reporter: kcrisman | Owner: was
Type: defect | Status: new
Priority: critical | Milestone:
Component: number theory | Keywords:
Author: | Upstream: Reported upstream. Developers deny
it's a bug.
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Comment(by dsm):
Pretty easy to fix but there are some choices regarding speed and whether
we now believe in pari's ispower function.
{{{
trying: 2
call Integers(n).multiplicative_generator() : 625 loops, best
of 3: 3.97 µs per loop
pari after Integers(n).multiplicative_group_is_cyclic(): 625 loops, best
of 3: 16.1 µs per loop
pari after inline Integers(n).mult.._group_is_cyclic() : 625 loops, best
of 3: 9.53 µs per loop
pari without check: : 625 loops, best
of 3: 8.74 µs per loop
pari trusting that pari.ispower now works : 625 loops, best
of 3: 9.39 µs per loop
I.mul_gen() if prime, trusting pari otherwise: : 625 loops, best
of 3: 29.3 µs per loop
trying: 97
call Integers(n).multiplicative_generator() : 625 loops, best
of 3: 3.93 µs per loop
pari after Integers(n).multiplicative_group_is_cyclic(): 625 loops, best
of 3: 33 µs per loop
pari after inline Integers(n).mult.._group_is_cyclic() : 625 loops, best
of 3: 27.3 µs per loop
pari without check: : 625 loops, best
of 3: 10.8 µs per loop
pari trusting that pari.ispower now works : 625 loops, best
of 3: 19.8 µs per loop
I.mul_gen() if prime, trusting pari otherwise: : 625 loops, best
of 3: 29.4 µs per loop
trying: 10007
call Integers(n).multiplicative_generator() : 625 loops, best
of 3: 3.93 µs per loop
pari after Integers(n).multiplicative_group_is_cyclic(): 625 loops, best
of 3: 34.1 µs per loop
pari after inline Integers(n).mult.._group_is_cyclic() : 625 loops, best
of 3: 28.4 µs per loop
pari without check: : 625 loops, best
of 3: 11.4 µs per loop
pari trusting that pari.ispower now works : 625 loops, best
of 3: 21.3 µs per loop
I.mul_gen() if prime, trusting pari otherwise: : 625 loops, best
of 3: 30 µs per loop
trying: 1000000007
call Integers(n).multiplicative_generator() : 625 loops, best
of 3: 3.86 µs per loop
pari after Integers(n).multiplicative_group_is_cyclic(): 625 loops, best
of 3: 78.6 µs per loop
pari after inline Integers(n).mult.._group_is_cyclic() : 625 loops, best
of 3: 73.6 µs per loop
pari without check: : 625 loops, best
of 3: 53.7 µs per loop
pari trusting that pari.ispower now works : 625 loops, best
of 3: 71.1 µs per loop
I.mul_gen() if prime, trusting pari otherwise: : 625 loops, best
of 3: 31.6 µs per loop
trying: 17^5
call Integers(n).multiplicative_generator() : 625 loops, best
of 3: 79.7 µs per loop
pari after Integers(n).multiplicative_group_is_cyclic(): 625 loops, best
of 3: 57.4 µs per loop
pari after inline Integers(n).mult.._group_is_cyclic() : 625 loops, best
of 3: 51 µs per loop
pari without check: : 625 loops, best
of 3: 10.5 µs per loop
pari trusting that pari.ispower now works : 625 loops, best
of 3: 20.8 µs per loop
I.mul_gen() if prime, trusting pari otherwise: : 625 loops, best
of 3: 46.7 µs per loop
trying: 2 * 109^100
call Integers(n).multiplicative_generator() : 625 loops, best
of 3: 857 µs per loop
pari after Integers(n).multiplicative_group_is_cyclic(): 625 loops, best
of 3: 879 µs per loop
pari after inline Integers(n).mult.._group_is_cyclic() : 625 loops, best
of 3: 869 µs per loop
pari without check: : 625 loops, best
of 3: 49.4 µs per loop
pari trusting that pari.ispower now works : 625 loops, best
of 3: 95.1 µs per loop
I.mul_gen() if prime, trusting pari otherwise: : 625 loops, best
of 3: 123 µs per loop
}}}
Long story short, Integers(n).multiplicative_generator is very fast for
primes, but otherwise slow. Trying to mix the two (using
multiplicative_generator for primes and pari for everything else) winds up
being slower than pari for small primes and faster for large ones; could
branch on size but not sure if the speed benefit would be worth the
complexity. I don't have a good sense for Python overheads at the
microsecond level.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10836#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
