Opened 6 years ago

Closed 6 years ago

#16540 closed defect (fixed)

Regression in Pari finite field interface

Reported by: defeo Owned by:
Priority: major Milestone: sage-6.4
Component: finite rings Keywords: finite_field regression pari
Cc: pbruin Merged in:
Authors: Peter Bruin Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: 5f6810f (Commits) Commit: 5f6810f1e072c91accac55c5983fb8abd85fdc64
Dependencies: Stopgaps:

Description

In Sage 6.2

sage: GF(11^23, 'a').gen()^Zmod(11)(1)
1

In 5.9 this used to give

sage: GF(11^23, 'a').gen()^Zmod(11)(1)
a

Change History (10)

comment:1 follow-up: Changed 6 years ago by jdemeyer

Do you agree that the correct behaviour is a ValueError?

comment:2 Changed 6 years ago by jdemeyer

  • Cc pbruin added

comment:3 Changed 6 years ago by pbruin

PARI's FF_pow requires the exponent to be a t_INT, but does not check the type, and FiniteFieldElement_pari_ffelt.__pow__() does not enforce this either. (Actually it also assumes the exponent to be an integer, since it checks if it is negative.) We could simply convert the exponent into an Integer; the only drawback is that we would have to do a separate check for IntegerMod with an incorrect modulus if we want to raise a ValueError in that case.

comment:4 in reply to: ↑ 1 Changed 6 years ago by defeo

Replying to jdemeyer:

Do you agree that the correct behaviour is a ValueError?

I agree that mathematically the operation does not make sense, unless the modulus is equal to the order of the element (but computing it would be overkill in my opinion) or a multiple (the only reasonable one being cardinality - 1).

Now, if we want to raise a ValueError, this is not a Pari issue anymore: it is a huge issue in basically any component of Sage!

sage: 3^Zmod(3)(2)
9
sage: GF(101)(2)^Zmod(3)(2)
4
sage: QQ['x'].gen()^Zmod(3)(2)
x^2
sage: i^Zmod(3)(2)
-1
sage: AbelianGroup([10])[1]^Zmod(3)(2)
f^2

etc...

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 6 years ago by pbruin

  • Authors set to Peter Bruin
  • Branch set to u/pbruin/16540-finite_field_exponentiation
  • Commit set to 5f6810f1e072c91accac55c5983fb8abd85fdc64
  • Status changed from new to needs_review

Here is a branch to make FiniteFieldElement_pari_ffelt.__pow__() always convert the exponent to an integer. This fixes the following mathematically wrong answer to return a:

sage: q = 11^23
sage: F.<a> = FiniteField(q)
sage: a^Mod(1, q - 1)
1

The new code actually seems to be marginally faster than the old one (about 10% on this example). It also adds a warning to the documentation that we do not check for well-definedness before converting the exponent to an integer.

comment:7 Changed 6 years ago by jdemeyer

  • Created changed from 06/25/14 16:21:12 to 06/25/14 16:21:12
  • Modified changed from 08/13/14 22:25:38 to 08/13/14 22:25:38
  • Status changed from needs_review to positive_review

comment:8 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name

comment:9 Changed 6 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_work to positive_review

comment:10 Changed 6 years ago by vbraun

  • Branch changed from u/pbruin/16540-finite_field_exponentiation to 5f6810f1e072c91accac55c5983fb8abd85fdc64
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.