Opened 8 years ago

Closed 8 years ago

#15220 closed defect (fixed)

Vector_modn_dense used for too large a modulus?

Reported by: mmezzarobba Owned by:
Priority: blocker Milestone: sage-5.12
Component: linear algebra Keywords:
Cc: Merged in: sage-5.12.rc0
Authors: Volker Braun Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

sage.rings.finite_rings.integer_mod? says that IntegerMod_int64 "is used if the modulus is less than 2^{31}-1".

Consider however a vector of elements of GF(p) with p between 231 and 232:

sage: K = GF(3037000493)
sage: v = vector(K, [42])
sage: type(v)
<type 'sage.modules.vector_modn_dense.Vector_modn_dense'>

Then:

sage: type(v[0])
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int64'>

which breaks some operations:

sage: ~v[0]
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-5-43d86000256e> in <module>()
----> 1 ~v[Integer(0)]

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod.so in sage.rings.finite_rings.integer_mod.IntegerMod_int64.__invert__ (sage/rings/finite_rings/integer_mod.c:29992)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod.so in sage.rings.finite_rings.integer_mod.mod_inverse_int64 (sage/rings/finite_rings/integer_mod.c:30920)()

ZeroDivisionError: Inverse does not exist.

This does not happens with modular integers themselves:

sage: type(K(42))
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
sage: ~K(42)
2241595602

Matrices do not seem affected either.

Things work fine with sage-5.8 on the same machine. This makes me suspect that the issue might have been introduced in aa83d6e996d552dfa871f510b1bc9af6f1127076 (#14627)—but I didn't check.

Attachments (1)

trac_15220_max_modulus.patch​ (2.2 KB) - added by vbraun 8 years ago.
Initial patch

Download all attachments as: .zip

Change History (5)

Changed 8 years ago by vbraun

Initial patch

comment:1 Changed 8 years ago by vbraun

  • Authors set to Volker Braun
  • Priority changed from major to blocker
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by vbraun

Yes, this is from #14627. Would have been nice if there would have been doctests...

I think its pretty trivial fix so we should get that into the next Sage release.

comment:3 Changed 8 years ago by mmezzarobba

  • Reviewers set to Marc Mezzarobba
  • Status changed from needs_review to positive_review

Looks good to me--and solves my problem. Thanks!

comment:4 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.12.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.