Ticket #4218 (closed defect: fixed)

Opened 3 months ago

Last modified 3 weeks ago

[with patch, with positive review] Extensions of Finite Fields don't work well

Reported by: justin Assigned to: AlexGhitza
Priority: major Milestone: sage-3.2.3
Component: algebra Keywords:
Cc:

Description

The following sage snippets show (some of) the problems. First, we set the stage: 

sage: F1.<a> = GF(2^7)
sage: P1.<x>=PolynomialRing(F1)
sage: f=x^2+x+F1(1)
sage: F2=F1.extension(f,'u')
sage: F2
Univariate Quotient Polynomial Ring in u over Finite Field in a of size 2^7 with modulus u^2 + u + 1
sage: a in F2
True

First problem: 

sage: for i in xrange(100):
   ....:         r = F2.random_element()
   ....:     if r != F2(0) and r != F2(1):
   ....:             print "Yoicks! r=%s"%r
   ....: 
sage:

No output means that 100 random elements of F2 are either 0 or 1, which seems somehow incorrect.

The next oddity is 

sage: F1.order()
128
sage: F2.order()
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)

/SandBox/Justin/sb/sage-3.1.1/<ipython console> in <module>()

/SandBox/Justin/sb/sage-3.1.1/ring.pyx in sage.rings.ring.Ring.order (sage/rings/ring.c:4108)()

NotImplementedError:

Shouldn't .order() work for extensions as well as those directly defined?

Attachments

trac_4218.patch (2.6 kB) - added by AlexGhitza on 12/20/2008 10:21:36 AM.

Change History

10/01/2008 08:41:14 PM changed by mabshoff

  • milestone set to sage-3.2.

Justin,

please remember to assign a milestone to tickets you open :)

Cheers,

Michael

10/04/2008 03:21:55 AM changed by AlexGhitza

  • owner changed from tbd to AlexGhitza.

10/04/2008 03:22:05 AM changed by AlexGhitza

  • status changed from new to assigned.

12/20/2008 10:20:04 AM changed by AlexGhitza

  • summary changed from Extensions of Finite Fields don't work well to [with patch, needs review] Extensions of Finite Fields don't work well.

The attached patch resolves the issues reported above, by implementing methods random_element() and order() for quotients of polynomial rings.

12/20/2008 10:21:36 AM changed by AlexGhitza

  • attachment trac_4218.patch added.

12/21/2008 10:08:33 AM changed by cremona

  • summary changed from [with patch, needs review] Extensions of Finite Fields don't work well to [with patch, with positive review] Extensions of Finite Fields don't work well.

Positive review. Patch applies cleanly to 3.2.2 and doctests in sage/rings/polynomial pass.

I did notice while testing that this does not work: 

sage: R.<x>=ZZ[]
sage: S=ZZ.extension(x^3-2,'a')
sage: S.order()
---------------------------------------------------------------------------
NotImplementedError

and also that S.random_element() gives a random integer (I think). Another ticket perhaps?

12/21/2008 02:39:46 PM changed by mabshoff

  • status changed from assigned to closed.
  • resolution set to fixed.
  • milestone changed from sage-3.4 to sage-3.2.3.

Merged in Sage 3.2.3.alpha0