Opened 8 years ago

Closed 6 years ago

#12217 closed defect (fixed)

Finite field polynomials allow division by zero

Reported by: johanbosman Owned by: AlexGhitza
Priority: major Milestone: sage-6.1
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Peter Bruin Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: u/vbraun/ff_division_by_zero (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by pbruin)

For prime finite fields, the following causes Sage to crash:

sage: P.<x> = GF(5)[]
sage: x/0
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Sage will now terminate.
------------------------------------------------------------------------

The cause is a missing check for a zero denominator. This leads to normalize in devel/sage/sage/rings/fraction_field_FpT.pyx calling nmod_poly_leading(denom) to get the leading coefficient of the denominator. This crashes, since the zero polynomial doesn't have a leading coefficient.

And non-prime finite fields don't complain at all:

sage: P.<x> = GF(25,'a')[]
sage: x/5
x

This is due to a missing check for division by zero in the __invert__() method of Givaro finite field elements. Inserting this check broke conversion of the finite field element 0 from Givaro to Gap, so this is also fixed.

Apply: 12217-zero_division-v2.patch

Attachments (2)

12217-zero_division.patch (3.7 KB) - added by pbruin 6 years ago.
correctly handle division by zero
12217-zero_division-v2.patch (4.8 KB) - added by pbruin 6 years ago.
correctly handle division by zero, now with better error messages

Download all attachments as: .zip

Change History (17)

comment:1 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 6 years ago by pbruin

It has gotten worse: the first example causes Sage (5.13.beta3) to crash, and when attaching GDB to do the autopsy, GDB crashes too!

The second example still behaves in the same way.

comment:3 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:4 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:5 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:6 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:7 Changed 6 years ago by pbruin

I fixed both bugs; a patch is coming soon. The second one is actually a bug in the Givaro interface:

sage: F=GF(25,'a')
sage: type(F)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
sage: z=F(0)
sage: ~z
1

Changed 6 years ago by pbruin

correctly handle division by zero

comment:8 Changed 6 years ago by pbruin

  • Authors set to Peter Bruin
  • Description modified (diff)
  • Status changed from new to needs_review

comment:9 follow-up: Changed 6 years ago by jdemeyer

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

Patch seems to work as advertised.

I think you should add an error message though: I prefer

ZeroDivisionError: fraction field element division by zero

or

ZeroDivisionError: division by zero in finite field

or even

ZeroDivisionError: division by zero in Finite Field in a of size 5^2

to

ZeroDivisionError

comment:10 in reply to: ↑ 9 Changed 6 years ago by pbruin

Replying to jdemeyer:

I think you should add an error message

Hmm. For the finite field inversion I really like

ZeroDivisionError: division by zero in Finite Field in a of size 5^2

so I'll add this.

As for the error message when trying to do x/0, what fails here is strictly speaking not a division inside the fraction field, but trying to construct a fraction (from two elements of the polynomial ring) whose denominator is 0. This is basically an implementation detail, though.

In any case, the existing "fraction field element division by zero" sounds awkward to me. At the moment I'm undecided between three possibilities:

ZeroDivisionError: fraction has denominator 0
ZeroDivisionError: division by zero in Univariate Polynomial Ring over Finite Field in a of size 5^2
ZeroDivisionError: division by zero in Fraction Field of Univariate Polynomial Ring over Finite Field in a of size 5^2

comment:11 Changed 6 years ago by pbruin

Something else that bothers me is the implementation of PolynomialElement.__div__(). When computing x/y, it first tries to coerce y to the base ring and multiply the polynomial x by ~y. This can fail either because the coercion fails or because y = 0. In both cases, the computation is retried, but this is useless if y = 0; after all, we will certainly get a ZeroDivisionError again. New patch now testing.

Changed 6 years ago by pbruin

correctly handle division by zero, now with better error messages

comment:12 Changed 6 years ago by pbruin

  • Description modified (diff)
  • Status changed from needs_work to needs_review

For division by 0 in the polynomial ring, I decided for 'fraction has denominator 0', but because of a different change in polynomial_element.pyx (see comment:11), you will only see this message when trying to construct fraction field elements by coercing a pair of elements of the polynomial ring into the fraction field; see the new doctest in fraction_field_FpT.pyx.

comment:13 Changed 6 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:14 Changed 6 years ago by vbraun

  • Branch set to u/vbraun/ff_division_by_zero

comment:15 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.