Opened 5 years ago

Closed 5 years ago

#16934 closed defect (fixed)

Fix factory keys for finite fields to avoid repeated construction

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-6.4
Component: finite rings Keywords:
Cc: Merged in:
Authors: Peter Bruin Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: 9cbdcde (Commits) Commit: 9cbdcde41b4783e7adf3f56451b9dedd36842f1d
Dependencies: #16930 Stopgaps:

Description (last modified by pbruin)

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 5 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:3 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:4 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:5 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:6 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:7 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:8 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:9 Changed 5 years ago by pbruin

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.

comment:10 follow-up: Changed 5 years ago by pbruin

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): 
    202202        cdef Integer xi
    203203
    204204        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:
    206206                pari_catch_sig_on()
    207207                self.construct((<FiniteFieldElement_pari_ffelt>x).val)
    208208            else:

After #16855, this change effectively does nothing.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 5 years ago by jdemeyer

Replying to pbruin:

  • src/sage/rings/finite_rings/element_pari_ffelt.pyx

    a b cdef class FiniteFieldElement_pari_ffelt(FinitePolyExtElement): 
    202202        cdef Integer xi
    203203
    204204        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:
    206206                pari_catch_sig_on()
    207207                self.construct((<FiniteFieldElement_pari_ffelt>x).val)
    208208            else:

Would you propose to make the above change, or simply to close as ticket as dupe of #16855?

comment:12 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:13 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:14 in reply to: ↑ 11 Changed 5 years ago by pbruin

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:15 Changed 5 years ago by jdemeyer

OK, let's wait and see what happens with #16855 then...

comment:16 Changed 5 years ago by pbruin

The construction of the non-identical 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 5 years ago by pbruin

  • Authors set to Peter Bruin
  • Branch set to u/pbruin/16934-FiniteField_factory_key
  • Commit set to c33a718235e86d268b025a01561a2f14b7dc5937
  • Component changed from coercion to finite rings
  • Dependencies set to #16930
  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from Finite fields coercion bug to Fix factory keys for finite fields to avoid repeated construction

This branch depends on #16930 to avoid merge conflicts. It merges with, and works independently of, #16855.

comment:18 Changed 5 years ago by git

  • Commit changed from c33a718235e86d268b025a01561a2f14b7dc5937 to ffb74fa8116d1a60e255300370ca4467e3b36732

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8923777Trac 16934: remove method FiniteFieldFactory.other_keys()
5e2681eTrac 16934: more cleaning up
ffb74faTrac 16934: add doctest

comment:20 Changed 5 years ago by jdemeyer

  • Branch changed from u/pbruin/16934-FiniteField_factory_key to u/jdemeyer/ticket/16934
  • Created changed from 09/04/14 14:44:21 to 09/04/14 14:44:21
  • Modified changed from 09/05/14 13:56:24 to 09/05/14 13:56:24

comment:21 Changed 5 years ago by jdemeyer

  • Commit changed from ffb74fa8116d1a60e255300370ca4467e3b36732 to 33c86ef572ea686782d5167d58c29a7e0b2d1f6c
  • Status changed from needs_review to 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=x-2, 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:

33c86efMerge remote-tracking branch 'origin/develop' into ticket/16934

comment:22 follow-up: Changed 5 years ago by pbruin

  • Branch changed from u/jdemeyer/ticket/16934 to u/pbruin/16934-FiniteField_factory_key
  • Commit changed from 33c86ef572ea686782d5167d58c29a7e0b2d1f6c to bf36ec118ee0c97dbfae0aed177c1014430b7a07
  • Status changed from needs_work to 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 non-modn implementations.

comment:23 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work
sage: GF(7, impl="givaro", modulus="primitive")
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-2-c6a1d2461111> in <module>()
----> 1 GF(Integer(7), impl="givaro", modulus="primitive")

/usr/local/src/sage-git/local/lib/python2.7/site-packages/sage/structure/factory.so in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:1160)()
                                                                                                                                                                        
/usr/local/src/sage-git/local/lib/python2.7/site-packages/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 in reply to: ↑ 22 ; follow-ups: Changed 5 years ago by 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 non-modn 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/16930 for details.")
Last edited 5 years ago by jdemeyer (previous) (diff)

comment:25 Changed 5 years ago by git

  • Commit changed from bf36ec118ee0c97dbfae0aed177c1014430b7a07 to 9cbdcde41b4783e7adf3f56451b9dedd36842f1d

Branch pushed to git repo; I updated commit sha1. New commits:

9cbdcdeTrac 16934: fix warning about ignored 'modulus' argument

comment:26 Changed 5 years ago by pbruin

  • Status changed from needs_work to needs_review

comment:27 Changed 5 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to positive_review

comment:28 in reply to: ↑ 24 ; follow-up: Changed 5 years ago by nbruin

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 non-modn 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 in reply to: ↑ 28 Changed 5 years ago by jdemeyer

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 construct GF(7) as quotient of ZZ by 7ZZ.

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 in reply to: ↑ 24 Changed 5 years ago by jdemeyer

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')

By the way, this is now implemented at #16983.

comment:31 Changed 5 years ago by vbraun

  • Branch changed from u/pbruin/16934-FiniteField_factory_key to 9cbdcde41b4783e7adf3f56451b9dedd36842f1d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.