Opened 10 years ago

Closed 8 years ago

# symbolic arithmetic errors

Reported by: Owned by: llpamies burcin major sage-6.2 symbolics pynac segfault Burcin Erocal Jean-Pierre Flori N/A e0d15a9 e0d15a9bf67e292d23ff306e2a8e632a280debea #13729, #13736

### Description (last modified by kcrisman)

Consider the following code:

```ff.<z> = GF(2**8, 'z')
poly.<c1,c2,c3> = PolynomialRing(ff, 3, 'c')
r1,r2 = var('r1,r2')
expression = -(c1*r2 - c2*r1)/c3
print expression.substitute(r1=z, r2=z)
```

This produces a TypeError?: unsupported operand parent(s) for '*': 'Finite Field in z of size 2pow8' and 'Rational Field'. I know that 'expression' is not an element of the ring 'poly', but using a PolynomialRing? is the only way I found to achieve symbolic arithmetic on finite fields.

However, the interesting story is that if I replace the expression by

```expression = -(r2 - c2*r1)/c3
```

it work perfectly well, but if instead the expression is

```expression = -(c1 + r2 - c2*r1)/c3
```

then I get a segmentation fault.

To make things a little bit more interesting I can rename r1 and r2 to a and b:

```ff.<z> = GF(2**8, 'z')
poly.<c1,c2,c3> = PolynomialRing(ff, 3, 'c')
a,b = var('a,b')
expression = -(c1*b - c2*a)/c3
print expression.substitute(a=z, b=z)
```

Then it works fine, but produces a segmentation fault for,

```expression = -(c1 + b - c2*a)/c3
```

so you can think that it might be a problem with the use of the names r1 and r2. But this is not the case, if I rename the PolynomialRing? variables instead, from c's to x's:

```ff.<z> = GF(2**8, 'z')
poly.<x1,x2,x3> = PolynomialRing(ff, 3, 'x')
r1,r2 = var('r1,r2')
expression = -(x1*r2 - x2*r1)/x3
print expression.substitute(r1=z, r2=z)
```

Then it works again for the first two expressions but produces a segmentation fault for the third too.

Any idea of what is going wrong here?

### comment:1 Changed 10 years ago by llpamies

• Component changed from PLEASE CHANGE to symbolics
• Owner changed from tbd to burcin

### comment:2 Changed 10 years ago by burcin

I can confirm the segfaults. The following three examples lead to a crash:

```ff.<z> = GF(2**8, 'z')
poly.<c1,c2,c3> = PolynomialRing(ff, 3, 'c')
r1,r2 = var('r1,r2')
expression = -(c1 + r2 - c2*r1)/c3
expression.substitute(r1=z, r2=z)
<boom>

a,b = var('a,b')
expression = -(c1 + b - c2*a)/c3
expression.substitute(a=z, b=z)
<boom>

poly.<x1,x2,x3> = PolynomialRing(ff, 3, 'x')
r1,r2 = var('r1,r2')
expression = -(x1 + r2 - x2*r1)/x3
expression.substitute(r1=z, r2=z)
<boom>
```

The fact that this depends on variable names made me think of ordering issues like #9880, but the examples above still lead to a segfault with patches from that ticket. I am now suspecting a coercion problem.

BTW, the backtrace looks like this:

```#0  import_submodule (mod=0xe0ea98, subname=0x7fffff8000e0 "sage",
fullname=0x7fffff8000d0 "sage.categories.sage") at Python/import.c:2556
#1  0x00007ffff7b06184 in load_next (mod=0xe0ea98, altmod=0x7ffff7da4af0,
p_name=<optimized out>, buf=0x7fffff8000d0 "sage.categories.sage",
p_buflen=0x7fffff8010e0) at Python/import.c:2415
#2  0x00007ffff7b067d0 in import_module_level (
name=0xbac1d9 "rings.integer_ring", globals=<optimized out>,
fromlist=0xf91890, level=<optimized out>, locals=<optimized out>)
at Python/import.c:2136
#3  0x00007ffff7b06d9a in PyImport_ImportModuleLevel (
name=0xbac1d4 "sage.rings.integer_ring", globals=0xfd7390,
locals=<optimized out>, fromlist=0xf91890, level=-1)
at Python/import.c:2188
#4  0x00007ffff7ae53ef in builtin___import__ (self=<optimized out>,
args=<optimized out>, kwds=<optimized out>) at Python/bltinmodule.c:49
#5  0x00007ffff7a408d3 in PyObject_Call (func=0x7ffff7fe2dd0,
arg=<optimized out>, kw=<optimized out>) at Objects/abstract.c:2529
#6  0x00007ffff7ae6cd7 in PyEval_CallObjectWithKeywords (func=0x7ffff7fe2dd0,
arg=0xb07af8, kw=<optimized out>) at Python/ceval.c:3890
#7  0x00007ffff7ae9622 in PyEval_EvalFrameEx (f=<optimized out>,
throwflag=<optimized out>) at Python/ceval.c:2333
#8  0x00007ffff7aee7bd in PyEval_EvalCodeEx (co=0xf90eb0,
globals=<optimized out>, locals=<optimized out>, args=<optimized out>,
argcount=2, kws=0x7ffff7fba068, kwcount=0, defs=0x0, defcount=0,
closure=0x0) at Python/ceval.c:3253
#9  0x00007ffff7a6cb5b in function_call (func=0xf970c8, arg=0x4b26488,
kw=0x4c7e300) at Objects/funcobject.c:526
#10 0x00007ffff7a408d3 in PyObject_Call (func=0xf970c8, arg=<optimized out>,
kw=<optimized out>) at Objects/abstract.c:2529
#11 0x00007ffff7aeb62a in ext_do_call (nk=78800008, na=2,
flags=<optimized out>, pp_stack=0x7fffff801610, func=0xf970c8)
at Python/ceval.c:4334
#12 PyEval_EvalFrameEx (f=<optimized out>, throwflag=<optimized out>)
at Python/ceval.c:2705
#13 0x00007ffff7aee7bd in PyEval_EvalCodeEx (co=0x13a7430,
globals=<optimized out>, locals=<optimized out>, args=<optimized out>,
argcount=2, kws=0x0, kwcount=0, defs=0x13b7ae8, defcount=1, closure=0x0)
at Python/ceval.c:3253
#14 0x00007ffff7a6ca52 in function_call (func=0x13be6e0, arg=0x4b26560,
kw=0x0) at Objects/funcobject.c:526
#15 0x00007ffff7a408d3 in PyObject_Call (func=0x13be6e0, arg=<optimized out>,
kw=<optimized out>) at Objects/abstract.c:2529
#16 0x00007fffd47c86ba in py_gcd (__pyx_v_n=0x4b10d60, __pyx_v_k=0x4a9b6c0)
at sage/symbolic/pynac.cpp:7096
#17 0x00007fffd44d4cf4 in GiNaC::gcd(GiNaC::numeric const&, GiNaC::numeric const&) () from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#18 0x00007fffd44b2bc9 in GiNaC::add::integer_content() const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#19 0x00007fffd44b2a7c in GiNaC::ex::integer_content() const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#20 0x00007fffd44a29c0 in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#21 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#22 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#23 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#24 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#25 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#26 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#27 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#28 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#29 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#30 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#31 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#32 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#33 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#34 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#35 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#36 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#37 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#38 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#39 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#40 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#41 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#42 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#43 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#44 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#45 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#46 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#47 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#48 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#49 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#50 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#51 0x00007fffd440c1fc in GiNaC::ex::construct_from_basic(GiNaC::basic const&)
() from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#52 0x00007fffd43c8897 in GiNaC::ex::ex(GiNaC::basic const&) ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
#53 0x00007fffd44a2fca in GiNaC::mul::eval(int) const ()
from /home/burcin/sage/sage-5.2/local/lib/libpynac.so.4
<mul::eval(), ex::ex(), ex::construct_from_basic() repeated ad nauseam>
```

### comment:3 Changed 10 years ago by burcin

I opened a ticket on the Pynac issue tracker. I'll come up with a patch soon.

Last edited 10 years ago by burcin (previous) (diff)

### comment:4 Changed 10 years ago by burcin

• Authors set to Burcin Erocal
• Dependencies set to #13729
• Keywords pynac segfault added
• Status changed from new to needs_review

Pynac 0.2.6 contains a fix for this. Updating the spkg is #13729.

### comment:5 Changed 10 years ago by jpflori

Would it be possible to give a little more details in the doctests introducing text? like explaining that depending on the name/ordering of the variables, the bug was/ was not triggered, whence the different tests made.

And putting expression or ex everywhere rather than changing the name in the middle?

With this I'll happily give positive review.

### Changed 10 years ago by burcin

apply only this patch

### comment:6 Changed 10 years ago by burcin

• Dependencies changed from #13729 to #13729, #13736
• Description modified (diff)
• Reviewers set to Jean-Pierre Flori

I uploaded a new patch with some text trac_13609-gf2_content.take2.patch. To demonstrate the content of the expressions involved, I wrapped GiNaC's `content()` method in #13736. This ticket now depends on the patch there.

Note that multiplying the numerator I give in the doctests by the content gives

```sage: -num.content(c1)*num
c1 + z*c2 + z
```

which changes the original leading coefficient `-1` by coercing it to `GF(2^8)`.

This does not happen during normalization, since `numeric::div_dyn()` is used directly to modify the coefficients. There is a shortcut in that function to do nothing if we are dividing by `1`. Perhaps I should back out the current fix in Pynac and change `numeric::div_dyn()` to disable the shortcut if the characteristic is not 0.

Comments?

### comment:7 Changed 9 years ago by vbraun

Fuzz 2 on top of sage-5.10.beta2, so needs to be rebased.

Apply only this

### comment:8 Changed 9 years ago by kcrisman

• Description modified (diff)

### comment:9 Changed 9 years ago by kcrisman

Perhaps I should back out the current fix in Pynac and change numeric::div_dyn() to disable the shortcut if the characteristic is not 0.

I think it is reasonable to have different behavior outside char 0.

### comment:10 Changed 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:11 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:12 Changed 8 years ago by mmezzarobba

• Branch set to u/mmezzarobba/ticket/13609
• Commit set to e0d15a9bf67e292d23ff306e2a8e632a280debea

The fix has been in Sage's version of Pynac for one year. The patch attached to this ticket (which just adds new tests) applies cleanly to sage-6.2.beta4, and the new tests pass. Is there any reason this ticket still needs review?

New commits:

 ​e0d15a9 `Trac 13609: fix symbolic expression auto evaluation when content is in GF(2^k)`

### comment:13 Changed 8 years ago by jpflori

I don't really remember, but if you feel happy with the changes let's merge this.

### comment:14 Changed 8 years ago by mmezzarobba

• Status changed from needs_review to positive_review

### comment:15 follow-up: ↓ 16 Changed 8 years ago by kcrisman

If there is no mathematical problem it's okay; I think that Burcin's point was that sometimes plus and minus one can replace each other with this code sometimes in characteristic two. Which is ... true, they can. It just doesn't "look" the same. Or at least I think that was the point of his comment and doctest along those lines?

### comment:16 in reply to: ↑ 15 Changed 8 years ago by mmezzarobba

Replying to kcrisman:

If there is no mathematical problem it's okay; I think that Burcin's point was that sometimes plus and minus one can replace each other with this code sometimes in characteristic two. Which is ... true, they can. It just doesn't "look" the same. Or at least I think that was the point of his comment and doctest along those lines?

In any case, the patch in this ticket only documents the currently implemented behaviour. I'd say any changes to address the behaviour noted in Burcin's comment belong in another ticket.

### comment:17 Changed 8 years ago by vbraun

• Branch changed from u/mmezzarobba/ticket/13609 to e0d15a9bf67e292d23ff306e2a8e632a280debea
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.