Equal PARI integers have different hashes

[jdemeyer]

In the code below, a5 and b5 are PARI integers equal to 5 but they have different hashes:

sage: pariK=pari("nfinit(x^2-x-1)"); b5 = pari(5); b5.debug(); a5 = pari(5); a5.debug(); print a5.__hash__(), b5.__hash__()
[&=00000000049437b0] INT(lg=3):0200000000000003 (+,lgefint=3):4000000000000003 0000000000000005
[&=000000000493cfe0] INT(lg=3):0200000000000003 (+,lgefint=3):7000000000000003 0000000000000005
-1729382256910270461 -8646911284551352317

This bug was discovered for ideals having different hashes.

The problem is with the initialization of integers in new_gen_from_mpz_t(). The attached patch fixes various instances of bad PARI object initialization.

Component: number fields

Keywords: pari cgetg integer ideal hnf

Author: Jeroen Demeyer

Reviewer: William Stein

Merged: sage-4.7.2.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/11611

[jdemeyer]

Changed keywords from none to pari ideal hnf

[jdemeyer]

comment:2

I have not been able to reproduce this error through the string interface:

sage: K.<a> = NumberField(x^2 - x - 1)
sage: I = K.ideal(2 * a - 1)
sage: pari("K=%s; idealhnf(K, idealfactor(K, %s)[1,1])"%(pari(K),pari(I))).debug()
[&=0000000004998178] MAT(lg=3):2600000000000003 0000000004998160 0000000004998130
  mat(1,1) = [&=0000000004998148] INT(lg=3):0200000000000003 (+,lgefint=3):4000000000000003 0000000000000005
  mat(1,2) = [&=0000000004998118] INT(lg=3):0200000000000003 (+,lgefint=3):4000000000000003 0000000000000002
  mat(2,1) = gen_0
  mat(2,2) = [&=0000000004998100] INT(lg=3):0200000000000003 (+,lgefint=3):4000000000000003 0000000000000001

[jdemeyer]

comment:3

The problem lies with the conversion between PARI and Sage:

sage: K.<a> = NumberField(x^2 - x - 1)
sage: pari_ideal = pari("[5, [2, 1]~, 2, 1, [2, 1]~]")
sage: pari(K.ideal(pari_ideal)).debug()
[&=00000000049f97b8] MAT(lg=3):2600000000000003 00000000049f97a0 00000000049f9770
  mat(1,1) = [&=00000000049f9788] INT(lg=3):0200000000000003 (+,lgefint=3):6600000000000003 0000000000000005
  mat(1,2) = [&=00000000049f9758] INT(lg=3):0200000000000003 (+,lgefint=3):4000000000000003 0000000000000002
  mat(2,1) = gen_0
  mat(2,2) = [&=00000000049f9740] INT(lg=3):0200000000000003 (+,lgefint=3):4000000000000003 0000000000000001

[jdemeyer]

Changed keywords from pari ideal hnf to pari integer ideal hnf

[jdemeyer]

comment:4

The issue is already visible on the level of PARI INTs, see the new ticket description.

[jdemeyer]

Changed keywords from pari integer ideal hnf to pari cgetg integer ideal hnf

[jdemeyer]

Attachment: 11611.patch.gz

[jdemeyer]

Author: Jeroen Demeyer

[williamstein]

comment:8

I read the patch, which is mostly about rewriting Cython code against the PARI library in a way that looks much cleaner and makes sense. I don't quite understand precisely what it is about the code here that fixes the bug though.

All tests pass, and the new code looks and reads well.

[tornaria]

comment:9

As William, I read the ticket description and the patch and I don't understand what is really the cause of the issue and why the patch fixes it.

I'd encourage Jeroen to add a comment explaining this bit and, if possible, to split the patch in two parts: a "fix the issue" part and a "cleanup" part (in the order that is most convenient).

---

I'm also wondering if the hash of a pari integer should match the hash of the corresponding sage or python integers. That is carefully considered in the sage integers/rationals, etc. The principle is that two values that are equivalent (for the purposes of equality comparision) should have the same hash to avoid nastiness in using the values as dictionary keys. The same would be true for some other pari types.

[jdemeyer]

comment:10

The code which is purely about the bug fix is in lines 9005--9007 of the new sage/libs/pari/gen.pyx. The problem is that z[1] was never properly initialized and might contain some random garbage which was on the PARI stack before.

I also rewrote some code which was similar in spirit to the buggy code, even though I could not obviously produce bugs from that code. Then I also did some general cleanup, like getting rid of __set_lvalue__().

[jdemeyer]

comment:11

Replying to @tornaria:

I'm also wondering if the hash of a pari integer should match the hash of the corresponding sage or python integers. That is carefully considered in the sage integers/rationals, etc. The principle is that two values that are equivalent (for the purposes of equality comparision) should have the same hash to avoid nastiness in using the values as dictionary keys. The same would be true for some other pari types.

This looks quite hard. You would really have to rewrite the PARI hash function for this to match the Sage hash functions or the other way around. Also, consider that PARI objects are rarely directly visible in Sage. They usually live in private members of classes, so are unlikely to end up as dictionary keys. And even if they do, it would be even rarer to mix PARI and Sage types.

[jdemeyer]

Merged: sage-4.7.2.alpha1

[jdemeyer]

Reviewer: William Stein

[jdemeyer]

comment:13

See #11854 for a follow-up (it turns out this ticket does not fully fix the problem).