Opened 11 years ago

Closed 11 years ago

Last modified 11 years ago

#11611 closed defect (fixed)

Equal PARI integers have different hashes

Reported by: jdemeyer Owned by: jdemeyer
Priority: critical Milestone: sage-4.7.2
Component: number fields Keywords: pari cgetg integer ideal hnf
Cc: Merged in: sage-4.7.2.alpha1
Authors: Jeroen Demeyer Reviewers: William Stein
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Attachments (1)

11611.patch (9.9 KB) - added by jdemeyer 11 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 11 years ago by jdemeyer

  • Keywords pari ideal hnf added

comment:2 Changed 11 years ago by jdemeyer

  • Owner changed from davidloeffler to jdemeyer

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

comment:3 Changed 11 years ago by jdemeyer

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

comment:4 Changed 11 years ago by jdemeyer

  • Description modified (diff)
  • Keywords integer added
  • Summary changed from Equal ideals have different hashes to Equal PARI integers have different hashes

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

comment:5 Changed 11 years ago by jdemeyer

  • Description modified (diff)
  • Keywords cgetg added

comment:6 Changed 11 years ago by jdemeyer

  • Priority changed from major to critical

Changed 11 years ago by jdemeyer

comment:7 Changed 11 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Status changed from new to needs_review

comment:8 Changed 11 years ago by was

  • Status changed from needs_review to positive_review

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.

comment:9 follow-up: Changed 11 years ago by tornaria

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.

comment:10 Changed 11 years ago by jdemeyer

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__().

comment:11 in reply to: ↑ 9 Changed 11 years ago by jdemeyer

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.

comment:12 Changed 11 years ago by jdemeyer

  • Merged in set to sage-4.7.2.alpha1
  • Resolution set to fixed
  • Reviewers set to William Stein
  • Status changed from positive_review to closed

comment:13 Changed 11 years ago by jdemeyer

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

Note: See TracTickets for help on using tickets.