#19929: GF(16) (without explicit variable name)
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: positive_review
Type: | Milestone: sage-duplicate/invalid/wontfix
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
number fields | Work issues:
Keywords: | Commit:
Authors: | e0259bf16f00e08b86e5bb743cf1df76b578e1aa
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
public/19929 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by was):
Replying to [comment:13 roed]:
> Replying to [comment:11 ncohen]:
> > > Did anybody write up how Fpbar works somewhere? (I'm teaching
computational number theory and it would be fun to talk about this.)
> >
> > I don't want to ruin the fun but this is a trac ticket in
`needs_review`, not a forum.
>
> I e-mailed William offline. #17569 now needs review.
For anybody who finds this via a google search, here's what David said,
which is very relevant for understanding the tradeoffs in this very ticket
and why one should expect constructing `GF(p^n)` via what is at #175569 to
be potentially significantly slower than just `GF(p^n,'a')`: " don't think
any of us wrote up pseudo-Conway polynomials in particular, since most of
the actual algorithms are simple modifications of the ones for Conway
polynomials. For details, see
sage/rings/finite_rings/conway_polynomials.py
especially the docstrings for PseudoConwayLattice,
PseudoConwayLattice.polynomial. _frobenius_shift is also needed, but a
bit fiddly."
First this -- for me it takes over 20 times longer to make the algebraic
closure version:
{{{
p = next_prime(10^12)
%time GF(p^6, 'a')
%time GF(p).algebraic_closure().subfield(6)
}}}
Increasing 6 quickly makes it take an arbitrarily large factor longer.
This is precisely the sort of thing that will seriously piss off some
cryptographers someday. And they will yell at me personally.
Next this -- it takes infinitely longer to make the algebraic closure
version (due to a bug):
{{{
p = next_prime(10^12)
%time GF(p^6, 'a')
%time GF(p).algebraic_closure().subfield(6)
}}}
I'm using sage-6.9.
For anybody curious about the benchmark issues I mentioned, I was
benchmarking arithmetic, say "a + b", where a and b are generators of
GF(9) and GF(27), respectively, using timeit. Using Fpbar this takes
about 30 times as long as doing exactly the same computation after
defining explicit field homomorphisms between non-Fpbar finite fields.
So probably Fpbar doesn't cache some sort of basic information about
embeddings. This is another motivation to support K.embeddings(G) for
any fields K and G, since though it's not quite as simple, in practice it
can be much faster.
--
Ticket URL: <http://trac.sagemath.org/ticket/19929#comment:16>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
