#13196: GL(n, GF(q)).random_element() is way too slow for what it does
--------------------------------------------------------------+-------------
Reporter: Bouillaguet | Owner:
joyner
Type: enhancement | Status:
needs_work
Priority: trivial | Milestone:
sage-5.2
Component: group theory | Resolution:
Keywords: matrix group, finite field, random element | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Charles Bouillaguet | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------------------+-------------
Comment (by Bouillaguet):
Replying to [comment:4 dimpase]:
> Could you add in the docstring that the probaility to get an invertible
element is about 1/3, and so we expect to get the
> answer in about 3 iterations ?
This is not true. The expected number of iterations is asymptotically `1 +
1/q + 2/q^2 + 3/q^3 + 5/q^4 + 7/q^5 + ....`
For `GF(2)` you have 3.5 expected iterations, but for GF(127) you have
1.008 iterations..... So that asymptotically, the number of iterations is
O(1), and the complexity of the procedure is `O(n^3)`, regardless of the
size of the field.
Is that OK with you ?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13196#comment:5>
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.
