regression: `tate_pairing` fail on certain curves, caused by bb3583c

[Jemmy1228]

Steps To Reproduce

This piece of code will work in SageMath 9.5, but fails in 10.0+

Due to the regression caused by bb3583c

p = 886368969471450739924935101400677
a = 26392827536965106777121445123290
b = 372325368096095544195525883520589
n = 886368969471450710152985728350703

K = GF(p)
Kx.<x> = K[]
K3.<u> = K.extension(Kx([4, 1, 0, 1]))
K3y.<y> = K3[]
K6.<t> = K3.extension(K3y([2, 0, 1]))

E = EllipticCurve(K, [a, b])
E6 = EllipticCurve(K6, [a, b])

xs =  [
    365236101742748463929673543888206,
    858097895593939865996182272259769,
    148438159087534462792506738986740
]

ys = [
    776418047571862972603801173382237,
    873677028107508092012208744232957,
    622138327043805563266794621920098
]

G6 = E6(K3(xs) * t^-2, K3(ys) * t^-3)
G = E6((260732037218904468999251391282274, 269397224242388526901257227817926))

G6.tate_pairing(G, n, 6, q=p)

Expected Behavior

In SageMath 9.5

(265866953933808765410855411775197*u^2 + 70840727177606736287176107019990*u + 564974538044254187432914971954649)*t + 277110391100948289129710841920822*u^2 + 854033999039359627943594217781184*u + 866734209507928074923908713252876

Actual Behavior

In SageMath 10.7

sage: G6.tate_pairing(G, n, 6, q=p)
---------------------------------------------------------------------------
PariError                                 Traceback (most recent call last)
Cell In[50], line 1
----> 1 G6.tate_pairing(G, n, Integer(6), q=p)

File ~/sage/src/sage/schemes/elliptic_curves/ell_point.py:2399, in EllipticCurvePoint_field.tate_pairing(self, Q, n, k, q)
   2394     raise ValueError("The point P must be n-torsion")
   2396 # NOTE: Pari returns the non-reduced Tate pairing, so we
   2397 # must perform the exponentiation ourselves using the supplied
   2398 # k value
-> 2399 ePQ = pari.elltatepairing(E, P, Q, n)
   2400 exp = Integer((q**k - 1)/n)
   2401 return K(ePQ**exp)

File cypari2/auto_instance.pxi:11331, in cypari2.pari_instance.Pari_auto.elltatepairing()

File ~/sage/local/var/lib/sage/venv-python3.12.5/lib/python3.12/site-packages/cypari2/handle_error.pyx:211, in cypari2.handle_error._pari_err_handle()
    209     pari_error_string = s.decode('ascii') + ": " + pari_error_string
    210
--> 211 raise PariError(errnum, pari_error_string, clone_gen_noclear(E))
    212
    213

PariError: incorrect type in checkell over Fq (t_VEC)

Additional Information

Regression caused by commit bb3583c

That commit assumes that curves defined over finite fields would be supported by PARI/GP, and therefore directly uses pari.elltatepairing for Tate pairing.

If PARI indeed supports the algebraic structure in my example code

The issue might originate from cypari2:
Before performing the pairing, PARI performs a series of checks:
elltatepairing -> checkell_Fq -> ell_over_Fq

Among them, ell_get_type checks the 1st element of the 14th subelement of the GEN, which is expected to be either t_ELL_Fp (= 3) or t_ELL_Fq (= 4).

However, using pari(E6).debug() reveals that this value is 0 (this behavior is the same as v9.5, however v9.5 is not using PARI so not affected)

14th component = [&=00007311eb03a6a8] VECSMALL(lg=2):2c00000000000002 000000000000000

meaning that cypari2 might not have constructed the correct PARI GEN object corresponding to E6. (I’m not entirely sure how this conversion is implemented; perhaps there’s a missing step to inform cypari2 that it should set it as t_ELL_Fq?)

If PARI does not support it

Should we consider reverting to the previous implementation? Or perhaps adjust the implementation to choose whether to use PARI based on the type of algebraic structure?

Environment

OS: Latest Arch Linux in WSL
Sage Version: 10.7

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[orlitzky]

One thing you could try (to either condemn or rule out cypari) is to run the computation directly in PARI/GP. Sage still has an old CLI interface to GP -- just use gp instead of pari in the sage shell. By mimicking what tate_pairing() is doing, you should eventually be able to determine if the problem is in PARI or cypari/sage.

[Jemmy1228]

One thing you could try (to either condemn or rule out cypari) is to run the computation directly in PARI/GP. Sage still has an old CLI interface to GP -- just use gp instead of pari in the sage shell. By mimicking what tate_pairing() is doing, you should eventually be able to determine if the problem is in PARI or cypari/sage.

Do you mean that I should directly launch the gp command-line program to open the PARI/GP CLI and use PARI/GP's syntax to mimic what I’m doing in Sage? I tried doing this, but I found myself unfamiliar with PARI/GP's syntax and functions, so I wasn’t able to successfully translate the example code to run it in PARI/GP.

I also attempted to directly use gp.elltatepairing() in SageMath, but since ell_get_type() returns 0, the curve is not supported by elltatepairing. This seems to be the root cause of the error.

[Jemmy1228]

Hi @GiacomoPope , sorry to ping you directly—I realize it might not be ideal to tag you. The issue I opened describes a regression that seems connected to the changes from PR #36994 /commit bb3583c. It hasn’t received much attention for a while, so I wanted to kindly bring it to your radar.

I'm not familiar with PARI/GP so I cannot figure out which is the right way to solve this problem. If you have a moment, could you take a look or let me know which is the correct approach to fix it? Totally understand if you’re busy—thank you for your time, and sorry again for the interruption.

[GiacomoPope]

So i tried working with pari/gp a little but I can't get a tower extension like this working so either it is not supported by PARI or I am not familiar enough with PARI.

I think we probably need to swap the is_finite check on the field to something smarter which checks if PARI supports the field we pick. This probably means using ell_get_type() and when this is zero we fall back to the previous implementation.

@Jemmy1228 are you happy to contribute this change, or do you need help?

[Jemmy1228]

@Jemmy1228 are you happy to contribute this change, or do you need help?

Thanks so much for taking the time to look into this!

I had the same experience: I couldn’t get this kind of tower extension to work in PARI/GP either. I’m not sure whether it’s a limitation of PARI or just my lack of familiarity with the syntax, but given that neither of us found a workable approach, adding a smarter capability check and falling back to the previous implementation sounds like the right path for now.

I’m happy to take this on. I’ll try swapping the is_finite check for something else and fallback if not supported by PARI/GP.

[GiacomoPope]

Feel free to tag me for review when you are finished :)

[orlitzky]

Do you mean that I should directly launch the gp command-line program to open the PARI/GP CLI and use PARI/GP's syntax to mimic what I’m doing in Sage? I tried doing this, but I found myself unfamiliar with PARI/GP's syntax and functions, so I wasn’t able to successfully translate the example code to run it in PARI/GP.

Most places you would use pari(foo) in sage, you can do gp(foo) instead. The latter passes the object to an instance of gp on the CLI. This is slower (and not typically recommended), but it does avoid cypari.

It looks like you already have everything figured out though!

[Jemmy1228]

Most places you would use pari(foo) in sage, you can do gp(foo) instead. The latter passes the object to an instance of gp on the CLI. This is slower (and not typically recommended), but it does avoid cypari.

Thanks for the detailed explanation!

I tried your approach in Sage, and I’m a bit unsure about one thing: should pari(x) and gp(x) produce equivalent PARI GENs? When I apply both to E6, the printed output looks quite different. Could this indicate an issue (or at least a mismatch) in how cypari2 constructs the GEN versus what gp receives on the CLI?

sage: gp(E6)
[0, 0, 0, 26392827536965106777121445123290, 372325368096095544195525883520589, 0, 52785655073930213554242890246580, 1489301472384382176782103534082356, -696581345395983624741713614423408196578936307990630923300424100, -1266855721774325125301829365917920, -321689118035026550184934363361788896, -1176624084128212403977358587117332692214445050944357564582924480217222257294801284085235130285872, 522944037390316623989937149803309414476442336409329852856467337093176993863942605896072171776000/302629651267544342586769183929355116310299653020668097886554650261631239016152593643321792769, Vecsmall([1]), [Vecsmall([128, -1])], [0, 0, 0, 0, 0, 0, 0, 0]]
sage: pari(E6)
[0, 0, 0, Mod(26392827536965106777121445123290, t^2 + 2), Mod(372325368096095544195525883520589, t^2 + 2), 0, Mod(52785655073930213554242890246580, t^2 + 2), Mod(602932502912931436857168432681679, t^2 + 2), Mod(878347278904060420100617514595240, t^2 + 2), Mod(505882217168576354548040836883434, t^2 + 2), Mod(62817883110068407817078446656855, t^2 + 2), Mod(19300432447343139286966825450179, t^2 + 2), Mod(533844503731258735717217294533630, t^2 + 2), Vecsmall([0]), [Vecsmall([64, 0])], [0, 0, 0, 0]]

It looks like you already have everything figured out though!

Ah yes, I dug a bit deeper and it seems likely that PARI’s elltatepairing doesn’t support this kind of algebraic structure (i.e., it’s not classified as t_ELL_Fp or t_ELL_Fq). I’m not 100% certain, though.

However, If the discrepancy between pari(E6) and gp(E6) is the root cause, then fixing it in cypari2 would be the more robust long-term solution.

[orlitzky]

They don't need to print the same, but ideally the underlying objects would be equivalent.

When you run gp(x), sage takes the sage object x and converts it to a string representation that is suitable for PARI/GP, and passes it to gp. Then gp prints a response, and sage converts the response back in to a sage object. So, for example, gp(3) gives you a sage.interfaces.gp.GpElement representing the number three.

Running pari(3) does something similar, but with library calls rather than a text pipe. In that case, you get back a cypari2.gen.Gen that represents the number three. Those two classes are different, though, so the two objects may not behave the same. There aren't many ways to print a "3", but for more complicated structures, methods such as _repr_ will differ between GpElement and Gen.

The main reason I suggested gp() was so that you could invoke PARI's Tate pairing function without having to learn PARI/GP syntax, to rule out cypari as the culprit. I think you did exactly that.

[JamesRickards-Canada]

I'm pretty sure this is the translation to PARI/GP:

p = 886368969471450739924935101400677
K = ffgen(p); /* Make the finite field F_p */
K3 = ffextend(K, x^3 + x + 4, 'u)[1];/* Extends the field. The return includes a root of the polynomial and the map from base to extension, but we don't need the map */
u = ffgen(K3);/* Saves the defining variable as u */
[K6, m2] = ffextend(K3, x^2 + 2, 't);/* Next extension, and save the map. */
t = ffgen(K6);

a = 26392827536965106777121445123290
b = 372325368096095544195525883520589
E6 = ellinit([a, b], K6);

xpt = ffmap(m2, 148438159087534462792506738986740*u^2 + 858097895593939865996182272259769 * u + 365236101742748463929673543888206) * t^(-2);
ypt = ffmap(m2, 622138327043805563266794621920098*u^2 + 873677028107508092012208744232957 * u + 776418047571862972603801173382237) * t^(-3);
G6 = [xpt, ypt];
G = [260732037218904468999251391282274, 269397224242388526901257227817926];

n = 886368969471450710152985728350703;
elltatepairing(E6, G, G6, n)

This code produces no issues, so I don't think the issue will be on the PARI/GP end.

[Jemmy1228]

They don't need to print the same, but ideally the underlying objects would be equivalent.
There aren't many ways to print a "3", but for more complicated structures, methods such as _repr_ will differ between GpElement and Gen.

I thought the printed result is some internal structure in PARI, i.e. the GEN object in simple form. However, the returned structure is completely different, the type (to be returned by ell_get_type()) is not the same. pari(E6) returns an elliptic curve of type t_ELL_Q = 1, gp(E6) returns an elliptic curve of type t_ELL_Rg = 0.

[JamesRickards-Canada]

Okay, I think you have found the issue. To explain a little bit of internal PARI/GP structure, every object is of C type "GEN" (which is just a long*). The first codeword stores the "internal type number" (among other things), which says what type of object it is. For example, t_INT (integer), t_FRAC (rational number), etc. There are actually only 21 implemented PARI/GP types; pretty much any complicated structure is stored as a t_VEC (vector).

In particular, an elliptic curve is just stored as a vector, it does not have its own special type (there is no t_ELL). How does a PARI/GP function know that you passed an elliptic curve? Well, because you, the user told it so. So yes, you could define an elliptic curve, then pass this curve to a number field method, since a number field is also stored as a t_VEC. However, this will produce an error: there are some basic checks that PARI functions to do make sure the user is doing normal things. The most basic one is just checking the length of the input, and those differ for elliptic curves and number fields.

Now, when it comes to elliptic curves, we want to know what field it is defined over, so the t_VEC structure also stores that, simply as a single entry from 0 to 5. This can be seen in paridecl.h:
enum { t_ELL_Rg = 0, t_ELL_Q, t_ELL_Qp, t_ELL_Fp, t_ELL_Fq, t_ELL_NF };
(to be specific, the 14th entry is a t_VECSMALL containing this entry).

If you use the code I put above, you will find that E6[14]=Vecsmall([4]), representing t_ELL_Fq, i.e. an elliptic curve over a finite prime power field, exactly as we expect. Based on your findings, using pari(E6) gives t_ELL_Q, an elliptic curve over $\mathbb{Q}$, which is definitely an error. The output of gp(E6) gives t_ELL_Rg, which is code for a generic commutative ring. While this is more correct, it still is an issue, as some methods will work for finite fields but not general commutative rings.

To summarize, your original diagnosis of

meaning that cypari2 might not have constructed the correct PARI GEN object corresponding to E6. (I’m not entirely sure how this conversion is implemented; perhaps there’s a missing step to inform cypari2 that it should set it as t_ELL_Fq?)

is correct. I'll try to investigate more

[JamesRickards-Canada]

More investigation:

p=11; K = GF(p); E = EllipticCurve(K, [2, 1]); parE = pari(E); gpE = gp(E);
print(E); print(parE[13]); print(gpE[14]);

Kx.<x> = K[]; K3.<u> = K.extension(Kx([-2, 0, 1])); E2 = EllipticCurve(K3, [2, 1]); parE2 = pari(E2); gpE2 = gp(E2);
print(E2); print(parE2[13]); print(gpE2[14]);

Produces

Elliptic Curve defined by y^2 = x^3 + 2*x + 1 over Finite Field of size 11
Vecsmall([3])
Vecsmall([3])
Elliptic Curve defined by y^2 = x^3 + 2*x + 1 over Finite Field in u of size 11^2
Vecsmall([4])
Vecsmall([0])

In particular, pari(E) is working here, and gp(E) is working (over the prime finite field), but gp(E2) is not (over the prime power finite field).

However, in your example, there is an even more fundamental issue. This code:

p = 886368969471450739924935101400677
K = GF(p)
Kx.<x> = K[]
K3.<u> = K.extension(Kx([4, 1, 0, 1]))
K3y.<y> = K3[]
K6.<t> = K3.extension(K3y([2, 0, 1]))
print(K); print(K3); print(K6);

produces

Finite Field of size 886368969471450739924935101400677
Finite Field in u of size 886368969471450739924935101400677^3
Univariate Quotient Polynomial Ring in t over Finite Field in u of size 886368969471450739924935101400677^3 with modulus t^2 + 2

So it looks like K6 is not recognized as a finite field. According to https://doc.sagemath.org/html/en/reference/finite_rings/sage/rings/finite_rings/finite_field_base.html,

Extensions of non-prime finite fields by polynomials are not yet supported: we fall back to generic code:

Thus, when you pipe this over to PARI/GP, you are not working with a finite field, hence the type is indeed t_ELL_Rg. In fact, you aren't working with a finite field in Sage either.

There are a few fixes to this.

1. Update your code so that K6 is in fact a finite field. If you take the compositum of the polynomials and define it from K it should be doable. The annoying thing will be if you want to pass between K3 and K6. I'm not really a Sage user so I don't know how easy/hard it will be.
2. Implement extensions of non-prime finite fields by polynomial
3. Switch to PARI/GP! As you see in the code above, they support extensions of non-prime finite fields by polynomials.

The only potential bug I see is with gp(E2). However, I actually don't think there is a bug. Passing a string representation to PARI/GP is not a good idea with finite fields, as just from a printed string PARI/GP cannot distinguish between a polynomial and a finite field element. gp(E) might only work because for a prime finite field, you don't need a variable, they can be represented with 0, 1, ..., p-1. As soon as you have a non-prime finite field, you need a variable, and this will be a problem. So, perhaps gp(E2) was implemented this was as it's the only possibility using that setup.