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. John --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
