Opened 8 years ago
Closed 8 years ago
#16934 closed defect (fixed)
Fix factory keys for finite fields to avoid repeated construction
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  finite rings  Keywords:  
Cc:  Merged in:  
Authors:  Peter Bruin  Reviewers:  Jeroen Demeyer 
Report Upstream:  N/A  Work issues:  
Branch:  9cbdcde (Commits, GitHub, GitLab)  Commit:  9cbdcde41b4783e7adf3f56451b9dedd36842f1d 
Dependencies:  #16930  Stopgaps: 
Description (last modified by )
The following sequence of commands somehow breaks the coercion framework. This is on vanilla Sage 6.4.beta1. The problem only occurs if impl="pari_ffelt"
is explicitly given, even though that is the default:
sage: k1.<a> = GF(17^14, impl="pari_ffelt") sage: _ = PolynomialRing(k1, 'x')(a/2) sage: k2.<a> = GF(17^14, impl="pari_ffelt") sage: _ = PolynomialRing(k2, 'x')(a/2) Traceback (most recent call last): ... TypeError: no coercion defined
The underlying reason is:
sage: k1 is k2 False
This double construction of the same finite field is caused by slightly different UniqueFactory
keys arising during the construction of a common parent (for the computation of a/2
) by the coercion system.
Related: #16855
Change History (31)
comment:1 Changed 8 years ago by
Description:  modified (diff) 

comment:2 Changed 8 years ago by
Description:  modified (diff) 

comment:3 Changed 8 years ago by
Description:  modified (diff) 

comment:4 Changed 8 years ago by
Description:  modified (diff) 

comment:5 Changed 8 years ago by
Description:  modified (diff) 

comment:6 Changed 8 years ago by
Description:  modified (diff) 

comment:7 Changed 8 years ago by
Description:  modified (diff) 

comment:8 Changed 8 years ago by
Description:  modified (diff) 

comment:9 Changed 8 years ago by
comment:10 followup: 11 Changed 8 years ago by
This guess is corroborated by the fact that the following change also appears to fix the bug:

src/sage/rings/finite_rings/element_pari_ffelt.pyx
a b cdef class FiniteFieldElement_pari_ffelt(FinitePolyExtElement): 202 202 cdef Integer xi 203 203 204 204 if isinstance(x, FiniteFieldElement_pari_ffelt): 205 if self._parent is(<FiniteFieldElement_pari_ffelt>x)._parent:205 if self._parent == (<FiniteFieldElement_pari_ffelt>x)._parent: 206 206 pari_catch_sig_on() 207 207 self.construct((<FiniteFieldElement_pari_ffelt>x).val) 208 208 else:
After #16855, this change effectively does nothing.
comment:11 followup: 14 Changed 8 years ago by
Replying to pbruin:
src/sage/rings/finite_rings/element_pari_ffelt.pyx
a b cdef class FiniteFieldElement_pari_ffelt(FinitePolyExtElement): 202 202 cdef Integer xi 203 203 204 204 if isinstance(x, FiniteFieldElement_pari_ffelt): 205 if self._parent is(<FiniteFieldElement_pari_ffelt>x)._parent:205 if self._parent == (<FiniteFieldElement_pari_ffelt>x)._parent: 206 206 pari_catch_sig_on() 207 207 self.construct((<FiniteFieldElement_pari_ffelt>x).val) 208 208 else:
Would you propose to make the above change, or simply to close as ticket as dupe of #16855?
comment:12 Changed 8 years ago by
Description:  modified (diff) 

comment:13 Changed 8 years ago by
Description:  modified (diff) 

comment:14 Changed 8 years ago by
Replying to jdemeyer:
Would you propose to make the above change, or simply to close as ticket as dupe of #16855?
I would say either we close this as a duplicate of #16855, or we try to fix the other bug (comment:11:ticket:16855) here:
sage: k1.<a> = GF(17^14, impl="pari_ffelt") sage: _ = a/2 sage: k2.<a> = GF(17^14, impl="pari_ffelt") sage: k1 is k2 False
comment:16 Changed 8 years ago by
The construction of the nonidentical k1
and k2
appears to be due to a subtlety involving the FiniteFieldFactory.other_keys()
method and an intermediate construction of another finite field (defined by the same data but with impl=None
) during the construction of a common parent for the computation of a/2
. The keys returned by other_keys()
only differ in the impl
keyword. I think the best solution is to always set the impl
keyword when constructing the key (as opposed to allowing it to be None
). Then the use of this other_keys()
method, which feels to me somewhat like a hack, can be avoided.
comment:17 Changed 8 years ago by
Authors:  → Peter Bruin 

Branch:  → u/pbruin/16934FiniteField_factory_key 
Commit:  → c33a718235e86d268b025a01561a2f14b7dc5937 
Component:  coercion → finite rings 
Dependencies:  → #16930 
Description:  modified (diff) 
Status:  new → needs_review 
Summary:  Finite fields coercion bug → Fix factory keys for finite fields to avoid repeated construction 
comment:18 Changed 8 years ago by
Commit:  c33a718235e86d268b025a01561a2f14b7dc5937 → ffb74fa8116d1a60e255300370ca4467e3b36732 

comment:19 Changed 8 years ago by
comment:20 Changed 8 years ago by
Branch:  u/pbruin/16934FiniteField_factory_key → u/jdemeyer/ticket/16934 

Created:  Sep 4, 2014, 2:44:21 PM → Sep 4, 2014, 2:44:21 PM 
Modified:  Sep 5, 2014, 1:56:24 PM → Sep 5, 2014, 1:56:24 PM 
comment:21 Changed 8 years ago by
Commit:  ffb74fa8116d1a60e255300370ca4467e3b36732 → 33c86ef572ea686782d5167d58c29a7e0b2d1f6c 

Status:  needs_review → needs_work 
Please restore the warning
warn("the 'modulus' argument is ignored when constructing prime finite fields")
for all prime finite field implementations because the modulus really is ignored:
sage: x = polygen(GF(7)); GF(7, modulus=x2, impl="givaro").modulus() x + 6
Of course we could change that behaviour (perhaps we should), but let's do that on a new ticket.
New commits:
33c86ef  Merge remotetracking branch 'origin/develop' into ticket/16934

comment:22 followup: 24 Changed 8 years ago by
Branch:  u/jdemeyer/ticket/16934 → u/pbruin/16934FiniteField_factory_key 

Commit:  33c86ef572ea686782d5167d58c29a7e0b2d1f6c → bf36ec118ee0c97dbfae0aed177c1014430b7a07 
Status:  needs_work → needs_review 
This commit adds back the warning. Alternatively, it could have been put outside the if impl == 'modn'
, but in this way it is easier to remove again for nonmodn
implementations.
comment:23 Changed 8 years ago by
Status:  needs_review → needs_work 

sage: GF(7, impl="givaro", modulus="primitive")  AttributeError Traceback (most recent call last) <ipythoninput2c6a1d2461111> in <module>() > 1 GF(Integer(7), impl="givaro", modulus="primitive") /usr/local/src/sagegit/local/lib/python2.7/sitepackages/sage/structure/factory.so in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:1160)() /usr/local/src/sagegit/local/lib/python2.7/sitepackages/sage/rings/finite_rings/constructor.pyc in create_key_and_extra_args(self, order, name, modulus, names, impl, proof, check_irreducible, **kwds) 521 if not modulus.is_irreducible(): 522 raise ValueError("finite field modulus must be irreducible but it is not.") > 523 if modulus is not None and modulus.degree() != n: 524 raise ValueError("the degree of the modulus does not equal the degree of the field.") 525 AttributeError: 'str' object has no attribute 'degree'
comment:24 followups: 28 30 Changed 8 years ago by
Replying to pbruin:
This commit adds back the warning. Alternatively, it could have been put outside the
if impl == 'modn'
, but in this way it is easier to remove again for nonmodn
implementations.
I would prefer to have the warning in one place. If we ever allow a custom modulus, we should allow it for all implementations.
My vision for this "modulus" argument is that the following should assign to a
a primitive root:
sage: K.<a> = GF(7, modulus='primitive')
so perhaps we should expand the warning to say
warn("currently, the 'modulus' argument is ignored when constructing prime finite fields. This might change in the future and this will probably also change the output of the .gen() and .modulus() methods on the finite field.\nSee http://trac.sagemath.org/16934 for details.")
comment:25 Changed 8 years ago by
Commit:  bf36ec118ee0c97dbfae0aed177c1014430b7a07 → 9cbdcde41b4783e7adf3f56451b9dedd36842f1d 

Branch pushed to git repo; I updated commit sha1. New commits:
9cbdcde  Trac 16934: fix warning about ignored 'modulus' argument

comment:26 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:27 Changed 8 years ago by
Reviewers:  → Jeroen Demeyer 

Status:  needs_review → positive_review 
comment:28 followup: 29 Changed 8 years ago by
Replying to jdemeyer:
Replying to pbruin:
This commit adds back the warning. Alternatively, it could have been put outside the
if impl == 'modn'
, but in this way it is easier to remove again for nonmodn
implementations.I would prefer to have the warning in one place. If we ever allow a custom modulus, we should allow it for all implementations.
My vision for this "modulus" argument is that the following should assign to
a
a primitive root:sage: K.<a> = GF(7, modulus='primitive')
The word "modulus" here is definitely wrong. If anything is a modulus for GF(7)
, it is 7, because the natural way to construct GF(7)
as quotient of ZZ
by 7ZZ
.
In general, even for field *extensions*, the word modulus is confusing. That only applies if you're making the field as a quotient of a polynomial ring. For the purpose proposed, generator
would cover the notion much better. I see from the doc that we have legacy against us on this one.
comment:29 Changed 8 years ago by
Replying to nbruin:
Replying to jdemeyer:
My vision for this "modulus" argument is that the following should assign to
a
a primitive root:sage: K.<a> = GF(7, modulus='primitive')The word "modulus" here is definitely wrong. If anything is a modulus for
GF(7)
, it is 7, because the natural way to constructGF(7)
as quotient ofZZ
by7ZZ
.
Depends on how you look at it. For me, there is a big philosophical difference between IntegerModRing(p)
and GF(p)
. I see IntegerModRing(m)
as ZZ/(m)
, while GF(p^n)
is IntegerModRing(p)[x]/(f(x))
for an irreducible polynomial f(x)
of degree n
.
For fields GF(p^n)
(n > 1), the word "modulus" for f(x)
is certainly more standard than "generator". For me, the "generator" is the image of x
in GF(p^n) = IntegerModRing(p)[x]/(f(x))
, which is returned by the gen()
method.
comment:30 Changed 8 years ago by
comment:31 Changed 8 years ago by
Branch:  u/pbruin/16934FiniteField_factory_key → 9cbdcde41b4783e7adf3f56451b9dedd36842f1d 

Resolution:  → fixed 
Status:  positive_review → closed 
I don't claim to know what is going on, but it may be caused by equality and identity not being the same for finite fields; #16855 seems to fix this bug.