#8335: Finite Field lattices
------------------------------------------------+---------------------------
Reporter: roed | Owner: AlexGhitza
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-5.11
Component: algebra | Resolution:
Keywords: days49 | Work issues:
Report Upstream: N/A | Reviewers: Jean-Pierre
Flori, Luca De Feo
Authors: David Roe, Jean-Pierre Flori | Merged in:
Dependencies: #13894 | Stopgaps:
------------------------------------------------+---------------------------
Comment (by jpflori):
Replying to [comment:49 defeo]:
> Hi,
>
> The doc in `constructor.py` says
>
> {{{
> - ``modulus`` - blabla
> - 'default': a Conway polynomial is used if in the database.
Otherwise
> a sparse polynomial is used for binary fields and a
> random polynomial is used for other characteristics.
> }}}
>
> but I got the impression that the default is to use pseudo-conway. By
the way, is it reasonable to use pseudo-conway as default ? It is utterly
slow !
It is and is expected to be.
>
> {{{
> sage: %time k = GF(next_prime(100000)^2)
> CPU times: user 16.41 s, sys: 0.05 s, total: 16.45 s
> Wall time: 16.18 s
> sage: %time l = GF(next_prime(100000)^3)
> CPU times: user 60.19 s, sys: 0.07 s, total: 60.26 s
> Wall time: 59.97 s
> sage: %time (k.gen() + l.gen()).parent()
> CPU times: user 0.08 s, sys: 0.00 s, total: 0.09 s
> Wall time: 0.07 s
> Finite Field in z6 of size 100003^6
> }}}
>
> Compare this with Magma
>
> {{{
> > time k := GF(NextPrime(100000)^2);
> Time: 0.000
> > time l := GF(NextPrime(100000)^3);
> Time: 0.000
>
> > time CommonOverfield(l, k);
> Time: 0.030
> }}}
>
I think the rationale is that Sage did not support finite fields with
unnamed generator before this patch.
So IIRC you could simply not do the above.
If you do something which used to work like
{{{
K.<a> = GF(182918291829182918291892819)
}}}
(assuming the random typing is some prime power)
I think it still picks up a random modulus as before (and is fast enough).
I agree it's kind of a bad thing to provide a new (but still natural,
especially for Magma's users) way to create finite fields which is
horribly slow.
So we might want to fix this.
Also note that this ticket only provides lattices for finite fields
created with pseudo-conway polynomials.
The goal is not to provide (compatible) embeddings for all finite fields
(as Magma is capable of).
> Wouldn't it be better to keep using ``random`` as default, and give
error messages suggesting to use ``conway`` when the user tries to
add/multiply/whatever two elements in different fields?
>
>
> On another note, I get the following messages (I suppressed them from
the output above for readability).
>
> {{{
> sage: k = GF(next_prime(10000)^11)
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> *** Warning: Mod(a,b)^n with n >> b : wasteful.
> }}}
>
> Any ideas on these?
No idea, I'll check tomorrow.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8335#comment:50>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
