Ask Your Question
1

Crash with polynomial over "Givaro" finite field

asked 2020-10-01 18:48:21 -0500

MKS gravatar image

updated 2020-10-03 13:15:42 -0500

tmonteil gravatar image

I would like to solve a system of equations in a finite field of prime order $p$ (illustrated below with $p = 229$).

The system consists in four equations and has four unknowns $a_0$, $a_1$, $a_2$, $a_3$.

It depends on parameters $\alpha_i$, $b_i$, all in $F(p)$, for $i = 1, 2, 3, 4$.

The four equations are

$$a_0 + a_1 \alpha_1 + a_2 \alpha_1^2 + a_3 \alpha_1^3 = b_1$$ $$a_0 + a_1 \alpha_2 + a_2 \alpha_2^2 + a_3 \alpha_2^3 = b_2$$ $$a_0 + a_1 \alpha_3 + a_2 \alpha_3^2 + a_3 \alpha_3^3 = b_3$$ $$a_0 + a_1 \alpha_4 + a_2 \alpha_4^2 + a_3 \alpha_4^3 = b_4$$

To do this I have tried with the following examples:

pm = 229
bp = 229
F.<x> = GF(pm, impl='givaro')
R.<a0, a1, a2, a3> = PolynomialRing(F)

def NP(a):
    return F(ZZ(a).digits(bp))  # integer to polynomial

eqns = [a0 + a1*NP(2) + a2*NP(2)^2 + a3*NP(2)^3 - NP(78),
        a0 + a1*NP(3) + a2*NP(3)^2 + a3*NP(3)^3 - NP(136),
        a0 + a1*NP(4) + a2*NP(4)^2 + a3*NP(4)^3 - NP(179),
        a0 + a1*NP(5) + a2*NP(5)^2 + a3*NP(5)^3 - NP(166)]
A = matrix(F, [[eqn.coefficient(b) for b in R.gens()] for eqn in eqns])
b = vector(F, [-eqn.constant_coefficient() for eqn in eqns])
X = A.solve_right(b)
print(X)

But it shows erros:

Unhandled SIGSEGV: A segmentation fault occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
------------------------------------------------------------------------
/usr/share/sagemath/bin/sage-python: line 2:  7655 Segmentation fault      (core dumped) sage -python "$@"

How can I fix this?

edit retag flag offensive close merge delete

Comments

This looks indeed like a bug, could you please try to isolate the problem and provide a minimal example ?

tmonteil gravatar imagetmonteil ( 2020-10-02 10:38:47 -0500 )edit

Minimal example posted as an answer.

I get the crash with Sage 8.2, Sage 9.1, Sage 9.2.beta13.

slelievre gravatar imageslelievre ( 2020-10-03 08:03:29 -0500 )edit

2 answers

Sort by ยป oldest newest most voted
1

answered 2020-10-03 09:47:03 -0500

tmonteil gravatar image

This is definitely a bug, thanks for reporting, it is now trac ticket 30702.

As for tracking a minimal example, it seems that when a finite field uses givaro as a backend, it is possible to deal with polynomial rings in a single variable (generic Sage implementation) :

sage: F = GF(3, impl='givaro')
sage: F
Finite Field of size 3
sage: type(F)                                                                                                                                                                                                
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>

sage: R.<a0> = PolynomialRing(F)
sage: type(R)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_finite_field_with_category'>                                                                                                                                                                           
sage: F(R(2))
2

But dealing with multivariate polynomial ring (whose implementation relies on libsingular) leads to segfaults:

sage: R.<a0,a1> = PolynomialRing(F)
sage: type(R)
<class 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular'>
sage: F(R(2))
....
Segmentation fault
edit flag offensive delete link more

Comments

@ tmonteil Is there any package instead of "givaro" which has no bug?

MKS gravatar imageMKS ( 2020-10-30 06:02:16 -0500 )edit
0

answered 2020-10-02 18:49:10 -0500

slelievre gravatar image

updated 2020-10-03 08:02:29 -0500

Multivariate polynomials over Givaro finite fields seem very fragile.

Their dict and __getitem__ methods crash easily. It seems the crash

  • occurs for any odd prime p (tried 3, 31, 229)
  • does not occur without impl='givaro'

Here are a few simple reproducers for the crash, with Sage 9.2.beta13.

sage: R.<a, b> = GF(3, impl='givaro')[]
sage: f, g, h = a, 2*a, -a

sage: g.dict()
<CRASH>

sage: g[a]
<CRASH>

sage: h.dict()
<CRASH>

sage: h[a]
<CRASH>

where <CRASH> is:

------------------------------------------------------------------------
(no backtrace available)
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
------------------------------------------------------------------------
.../bin/sage-python: line 2: ... Segmentation fault: ... sage -python "$@"

By contrast, these commands work:

sage: f.dict()
{(1, 0): 1}

sage: f[a]
a

sage: f[b], g[b], h[b]
(0, 0, 0)

The crash thus seems connected to scalars other than 0 and 1.

Not sure if this is related: the finite field list is ordered differently in the Givaro implementation:

sage: GF(3).list()
[0, 1, 2]

sage: GF(3, impl='givaro').list()
[0, 2, 1]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-10-01 18:48:21 -0500

Seen: 109 times

Last updated: Oct 03