#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 kcrisman):
From some correspondence with myself, William, and the Pari team, where it
becomes clear that their implementation has the rather useful virtue of
being very very fast:
{{{
> Compare :
>
> (23:07) gp > p = 10^50 + 151;
> (23:07) gp > for(i=1,10^2, isprime(p))
> time = 1,324 ms.
> (23:07) gp > for(i=1,10^2, ispseudoprime(p))
> time = 32 ms.
> (23:07) gp > for(i=1,10^2, znprimroot(p))
> time = 112 ms.
>
> For simple inputs (where factoring p-1 is not a problem), it's orders of
> magnitude faster to find a plausible primitive root than to guarantee
> that the question makes sense (primality proof). In fact, already trying
> to weed out most composites [ ispseudoprime vs. isprime ] takes a
> non-negligible amount of time.
>
> As p increases, I can produce (contrived but) legitimate prime inputs
> where isprime() takes an arbitrary amount of time whereas znprimroot()
> remains essentially instantaneous. For random large p, factoring p-1
will
> dominate the running time, hiding all this. (In fact, znprimroot won't
> even stand a chance of finishing.)
}}}
So we will keep using their very fast function and wrap it with something
that checks for sensible input, but adding documentation like
{{{
sage: b = pari(11)
sage: b.znprimroot()
}}}
to the documentation for our `primitive_root` function for those needing
direct access to the speed, warning of 'undefined' input. William, does
that sound right?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10836#comment:4>
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.
