Opened 11 years ago

Closed 11 years ago

# Equal PARI integers have different hashes

Reported by: Owned by: jdemeyer jdemeyer critical sage-4.7.2 number fields pari cgetg integer ideal hnf sage-4.7.2.alpha1 Jeroen Demeyer William Stein N/A

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.

### 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)
• 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 `INT`s, see the new ticket description.

### comment:5 Changed 11 years ago by jdemeyer

• Description modified (diff)

### comment:6 Changed 11 years ago by jdemeyer

• Priority changed from major to critical

### 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: ↓ 11 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

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.