Opened 11 years ago

Closed 7 years ago

Last modified 18 months ago

#9524 closed defect (fixed)

Nasty bug with polynomial arithmetic and NTL contexts

Reported by: craigcitro Owned by: AlexGhitza
Priority: critical Milestone: sage-6.2
Component: basic arithmetic Keywords:
Cc: roed, robertwb, ylchapuy, jpflori, defeo Merged in:
Authors: Jean-Pierre Flori Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: 9e94ed2 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by jpflori)

I just ran into the following nasty bug:

sage: polygen(GF(49, 'a')) ; polygen(GF(9, 'a'))
x
x
sage: x = polygen(GF(49, 'a'))
sage: -x
2*x
sage: x + 0
x
sage: -x
6*x

This is still present in sage-4.5.

We have to ensure two things before playing with NTL finite field elements:

  • restore the ZZ_p context (characteristic);
  • restore the ZZ_pE context (defining polynomial).

Restoring the latter does not automatically restore the former.

Change History (20)

comment:1 Changed 7 years ago by mmezzarobba

  • Milestone set to sage-6.2

The problem is still present in sage-6.1 (although the last command now returns 2*x).

comment:2 Changed 7 years ago by jpflori

  • Cc jpflori added

comment:3 Changed 7 years ago by jpflori

There is indeed a bunch of PY_NEW all over the place in polynomial_template.pxi.

Anyway IIRC the use of PY_NEW is hackish and one should now use the more proper __new__ (not sure of the underscore pattern) which might be easier to override for NTL specific needs.

comment:4 Changed 7 years ago by jpflori

Or we could just add some celement_new which would except for NTL just call PY_NEW.

comment:5 Changed 7 years ago by jpflori

  • Description modified (diff)

The problem is actually different from what was stated in the original description.

In fact, calling PY_NEw or whatever before restoring context was not the (only) rpoblem. The main problem is that restoring the ZZ_pE context does not restore the "current" prime from the ZZ_p context.

comment:6 Changed 7 years ago by jpflori

Also note, that it is perfectly fine (but maybe not such a good idea) to call PY_NEW without restoring the modulus. With the way things are currently coded, the PY_NEw call just allocates memory, no C++ constructor is called or anything done which could depend on the current context.

comment:7 Changed 7 years ago by jpflori

  • Authors set to Jean-Pierre Flori
  • Branch set to u/jpflori/ticket/9524
  • Commit set to 2aea9cd24a679e2218db1db7395ba9ad91d5a50e
  • Priority changed from major to critical
  • Status changed from new to needs_review

New commits:

c935d41Correctly restore NTL contexts for finite field extensions.
b50eb08Better fix for NTL contexts.
2aea9cdAdd test for correct restoration of NTL contexts.

comment:8 Changed 7 years ago by git

  • Commit changed from 2aea9cd24a679e2218db1db7395ba9ad91d5a50e to 964979fc886e507447a047efd0c471f3e348119e

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

964979fRemove previous changes and fix typo.

comment:9 Changed 7 years ago by jpflori

  • Cc defeo added

It should be possible to define a cpp class storing the two pointers (as the current C struct) with an additional mehod calling the restore method through the two pointers in sage/libs/ntl/whatever.pxd or .h and implement it directly in an additional sage/libs/ntl/whatever.cpp. One would have to include the NTL directly, and maybe hack through the hackish name mangling currently done in Sage (I presume the NTL wrapper was written before Pyrex/Cython? correctly supported C++). Not sure it is worth the trouble doing that in Sage. But this is surely worth a mail to Shoup in case he agrees to add a new method to ZZ_pEContext restoring both the modulus and the characteristic.

comment:10 Changed 7 years ago by jpflori

I've pushed a C++ solution to u/jpflori/ticket/9524cpp which is currently broken for two reasons:

  • It adds an header in src/sage/libs/ntl/ZZ_peContext_ptrs.h which is found by the files needing it in the same folder, but not by files in other folders, e.g. files in the padics folder. As a testing hack, just copy it to local/include.
  • python fails to import/dlopen polynomial_zz_pex.so (just try the ticket description test with the C++ branch) because of an undefined reference to the restore method of the new ZZ_pEContext_ptrs C++ class. Note the symbol is well defined in ntl_ZZ_pEContext_class.so (with the same C++ name mangling stuff, and nm gives a D for it) and can be used from there. I've not coded in C++ for some time, so I must have done somethign wrong. If any better (or just real) C++ coder can give us a clue, that would be very welcome.

Whatsoever, unless someone knows how to easily fix the above two issues, let's get the dirty plain C solution merged.

comment:11 Changed 7 years ago by jpflori

Adding

import ctypes   
flags = sys.getdlopenflags()
sys.setdlopenflags(flags | ctypes.RTLD_GLOBAL)

to src/sage/all.py solves the second issue (which was the more worrying one as far as I'm concerned). Not sure how much this can hurt (this is the default only on OS X IIRC, see http://docs.python.org/2.5/lib/ctypes-loading-shared-libraries.html.

comment:12 Changed 7 years ago by jpflori

We could also link file that needs it to the p/cython generated so file. But I have no idea in which order cython builds the so files. So I think the only proper C++ solution is to build an external so file with what I've put in, and install it in local/ and link to it. Or that such a class is integrated into NTL directly. And I think it's overkill, so I won't follow this path anymore.

comment:13 Changed 7 years ago by git

  • Commit changed from 964979fc886e507447a047efd0c471f3e348119e to c852900ba28231eb3b370b7aad2ca3bc75907ea8

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

b43eed9C++ (broken) solution.
d520b50Dirty hack.
c852900Merge remote-tracking branch 'trac/develop' into ticket/9524

comment:14 Changed 7 years ago by jpflori

  • Status changed from needs_review to needs_work

Groumpf it seems I've switched the branches...

comment:15 Changed 7 years ago by git

  • Commit changed from c852900ba28231eb3b370b7aad2ca3bc75907ea8 to 9e94ed2499088e6753ff7ed46dc305282dcb886c

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

9e94ed2Merge remote-tracking branch 'trac/develop' into ticket/9524

comment:16 Changed 7 years ago by jpflori

  • Status changed from needs_work to needs_review

comment:17 follow-up: Changed 7 years ago by vbraun

  • Reviewers set to Volker Braun

Looks good to me

comment:18 in reply to: ↑ 17 Changed 7 years ago by roed

Replying to vbraun:

Looks good to me

You should probably mark it as positively reviewed.

comment:19 Changed 7 years ago by vbraun

  • Branch changed from u/jpflori/ticket/9524 to 9e94ed2499088e6753ff7ed46dc305282dcb886c
  • Resolution set to fixed
  • Status changed from needs_review to closed

comment:20 Changed 18 months ago by kedlaya

  • Commit 9e94ed2499088e6753ff7ed46dc305282dcb886c deleted

Just spotted this again after a long absence, albeit not reproducibly. This was running 9.0beta9, in the middle of a run of sage -t src/sage/rings/polynomial/.

**********************************************************************
File "src/sage/rings/polynomial/polynomial_zz_pex.pyx", line 103, in sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX.__init__
Failed example:
    5*x
Expected:
    5*x
Got:
    2*x
**********************************************************************
Note: See TracTickets for help on using tickets.