On Wednesday 23 April 2008, John Cremona wrote: > There's a serious inefficiency in the construction of finite fields > GF(2^n) in Sage at the moment. > For n<=15 these are constructed of type > sage.rings.finite_field_givaro.FiniteField_givaro, about which I have > nothing to say now; for n>=16 they have type > sage.rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e and are > constructed by wrapping the appropriate NTL class. > > The problem lies with how the defining polynomial for te field is > chosen: any irreducible poly of degree n over GF(2) will do in > principle. > > The code in sage/rings/finite_field_ntl_gf2e.pyx chooses random > polynomials of degree n until it finds an irreducible one, the n > passes it (actually its coefficients) to a wrapped NTL constructor. > Two problems: > (1) The random polynomials have expected number of terms n/2, so even > when one is found whcih is irreducuble it is inefficient to work with > (reduction mod f is faster if f is sparse); > (2) Many many trials may be needed before a polynomial is found, so > the constructor can take for ages (eg 15s for n=500, and 314 s for > n=600) > > Some solutions: > (1) Use sparse polynomials only. These are better to use as defining > polynomials. Shoup says there are no known n for which there is no > known irreducible trinomial (x^n+x^k+1) or 5-term > (x^n+x^k1+x^k2+x^k3+1). > (2) In NTL suitable sparse polys are precomputed for n<2048; we could > copy that list. (It is called GF2X_irred_tab in GF2XFactring.c in > NTL) > (3) We could let NTL get the poly for us, using its > BuildSparseIrred() function. > > I propose that (3) is best; I can try to do that but it will be > harder than (1)+(2). Shall I open a trac for this? I should be able > to put in a patch based on (1)+(2) very easily.
I implemented that (in fact, I copied it from the generic GF(q) constructor) and favour (3) too but only if no conway polynomial is known (which is the case when the random search is triggered only anyway). Later, we could use a sparse polynomial internally but represent everything using Conway polynomials to the user/rest of the library. Btw. a while ago I timed the influence of the moduli for GF(2^n) here: http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl/2007/11/07 Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
