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 )
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.
Attachments (2)
Change History (17)
comment:1 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
- Description modified (diff)
comment:4 Changed 6 years ago by
- Description modified (diff)
comment:5 Changed 6 years ago by
- Description modified (diff)
comment:6 Changed 6 years ago by
- Description modified (diff)
comment:7 Changed 6 years ago by
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
comment:8 Changed 6 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:9 follow-up: ↓ 10 Changed 6 years ago by
- 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
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
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.
comment:12 Changed 6 years ago by
- 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
- Status changed from needs_review to positive_review
comment:14 Changed 6 years ago by
- Branch set to u/vbraun/ff_division_by_zero
comment:15 Changed 6 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
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.