#8212: arithmetic on GF(2^n) might be improved
--------------------------------+-------------------------------------------
Reporter: zimmerma | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: minor | Milestone: sage-4.3.3
Component: basic arithmetic | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
The default polynomials chosen by Sage to perform arithmetic over
GF(2**n) have sometimes Hamming weight 7 or more, which is not optimal.
Consider for example:
{{{
sage: T.<a> = GF(2^211)
sage: T.modulus()
x^211 + x^9 + x^6 + x^5 + x^3 + x + 1
def bar(n):
f = a
for i in range(n):
f = f^2
return f
sage: %timeit bar(10000)
5 loops, best of 3: 88.5 ms per loop
}}}
With the following pentanomial, we get a nice speedup:
{{{
sage: R.<x> = PolynomialRing(GF(2))
sage: T.<a> = GF(2^211,name='a',modulus=x^211 + x^11 + x^10 + x^8 + 1)
sage: %timeit bar(10000)
5 loops, best of 3: 57.3 ms per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8212>
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.
