#8373: finite fields constructed with non-primitive defining polynomial
--------------------------------+-------------------------------------------
Reporter: rkirov | Owner: AlexGhitza
Type: defect | Status: new
Priority: minor | Milestone:
Component: basic arithmetic | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by fwclarke):
Replying to [ticket:8373 rkirov]:
In your example, `a` ''is'' a generator; it's an ''algebra generator''.
In fact `a` generates `K` in exactly the same sense in which `x` generates
`R`. What you're looking for is:
{{{
sage: R.<x> = GF(2)[]
sage: K.<a> = GF(16, modulus=x^4+x^3+x^2+x+1)
sage: K.multiplicative_generator()
a + 1
}}}
It would be a mistake to insist on having a primitive generator. Of your
options:
(1) could slow Sage down unnecessarily, and what should it do if a user
wanted to use a non-primitive generator?
(2) yes, if the documentation is confusing, it should be clarified.
(3) I don't quite understand. If you mean ignore a given modulus if it
is not primitive, that would be very confusing.
What ''is'' needed, for non-prime fields of large characteristic, is a
much better way of finding a multiplicative generator:
{{{
sage: p = 65537
sage: K.<a> = GF(p^2)
sage: a.multiplicative_order() == p^2 - 1
False
sage: time K.multiplicative_generator()
CPU times: user 498.03 s, sys: 56.61 s, total: 554.64 s
Wall time: 555.20 s
a + 3
}}}
What's taking the time here is that the current algorithm, after deciding
that `a` isn't a multiplicative generator, pointlessly computes the
multiplicative order of all the non-zero elements in the prime field,
before trying `a` (again), `a + 1`, `a + 2`, and succeeding with `a + 3`.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8373#comment:1>
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.
