`GF` on a large prime power (`GF(2^93)`, `GF(3^58)`, `GF(5^32)` etc.) crash Sage

[maxale]

Steps To Reproduce

Call GF(5^32).

Expected Behavior

It should create a field with 5^32 elements.

Actual Behavior

Sage crashes.

Additional Information

It works fine in Sagecell, which runs Sage 10.2

Environment

- **OS**: Ubuntu 22.04.4 LTS
- **Sage Version**: 10.4.rc2

Checklist

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

[ytrezq]

Do you have an idea on how to declare an elliptic curve without using GF() ?

[fchapoton]

It is better to use GF((3,58)) to avoid factorisation.

[fchapoton]

Works for me with 10.4rc4 ; ubuntu 22.04 ; intel core i5:

sage: GF((5,32))
Finite Field in z32 of size 5^32

and

sage: GF((5**32))
Finite Field in z32 of size 5^32

[lucasaugustus]

It is better to use GF((3,58)) to avoid factorisation.

Checking for prime-power-ness using the following procedure is not much slower than primality testing:

1. Check for primality. If prime, exit.

2. Check for squareness, then cubeness, then fourth-power-ness, etc. If you get a hit, then proceed to 3. If you do not get a hit before the nth root of your number falls below 2, then you do not have a power, so exit.

3. You now know that your number is an nth power. Take the nth root of your number and restart the procedure on that.

No factorization is needed.

[fredrik-johansson]

If we look at the example posted on reddit https://old.reddit.com/r/math/comments/1e5115x/in_sagemath_how_to_use_gf_on_a_very_large_finite/

GF(21888242871839275222246405745257275088696311157297823662689037894645226208583, 12)

is indeed fast while

GF(21888242871839275222246405745257275088696311157297823662689037894645226208583^12)

is slow, but this has nothing to do with factoring p^e which is instant.

The issue is apparently the way Sage attempts to construct a "pseudo-Conway polynomial". In this example, this leads to the computation of a g-th root of 3 in

GF(21888242871839275222246405745257275088696311157297823662689037894645226208583^3)

where

g = 479095176016622842441988045216678740799252316531100822436447802254070093686400125690712891094660118376933489589901796572993553457802275986541038249076473

and this leads to factoring this integer g which takes forever.

The surprising thing here is that Sage apparently uses different code paths to construct an irreducible polynomial for GF(p, e) and GF(p^e).

Edit: apparently providing a variable name triggers the fast construction:

sage: GF(21888242871839275222246405745257275088696311157297823662689037894645226208583^12, "a")
Finite Field in a of size 21888242871839275222246405745257275088696311157297823662689037894645226208583^12

Related issue: https://github.com/sagemath/sage/issues/31434

[maxale]

GF((5,32)) crashes my Sage equally well. I attach the trace log. I'm not sure if that's a real cause but at the end it says:

#89 0x000055c0e19bd935 in _start ()
No symbol table info available.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
[Inferior 1 (process 892445) detached]
30  ../sysdeps/unix/sysv/linux/wait4.c: No such file or directory.
Traceback (most recent call last):
  File "<string>", line 25, in <module>
ModuleNotFoundError: No module named 'Cython'
Error while executing Python code.

Full log: crash_mnrq5c92.log

[vincentmacri]

I also can't reproduce this.

ModuleNotFoundError: No module named 'Cython'

This makes me wonder if there's an issue with your installation. Can you run ./sage --testall? It will take a while (a few hours maybe) but if Sage is installed correctly you should see few if any failing tests. If you get a lot of failed tests, then there might be something wrong with your Sage installation itself.

[videlec]

@fredrik-johansson The code path for GF(p, n) does not quite exist

sage: GF(5, 2)
Finite Field of size 5

The second argument seems to be the generator name (when the first argument is not a prime)

sage: GF((5, 2), 'x')
Finite Field in x of size 5^2
sage: GF((5, 2), 'x').gen()
x

I think that GF(5, 2) should raise an error equally to

sage: GF(5^2, 2)
Traceback (most recent call last):
...
ValueError: variable name '2' does not start with a letter

[videlec]

As I answered in ask question 78280, one could build "manually" a finite field not relying on pseudo-Conway by providing an explicit irreducible polynomial for the modulus

sage: p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
sage: A = GF(p)
sage: B = A['x']
sage: poly = B.random_element(12, monic=True)
sage: while not poly.is_irreducible():
....:      poly = B.random_element(12, monic=True)
sage: C = A.extension(poly, 'u')
sage: C
Finite Field in u of size 21888242871839275222246405745257275088696311157297823662689037894645226208583^12

Beyond a certain range, it would be desirable for the above code to be the default code path.

[user202729]

That would be backwards incompatible since they're documented in the library and user-observed behavior

• name -- string, optional. Note that there can be a substantial speed penalty (in creating extension fields) when omitting the variable name, since doing so triggers the computation of pseudo-Conway polynomials in order to define a coherent lattice of extensions of the prime field. The speed penalty grows with the size of extension degree and with the number of factors of the extension degree.

A reasonable thing to do may be to raise a warning to the user if p is large however.

[maxale]

I suspect the crash may be related to my Sage being linked to a locally installed libntl.a (see also #38255). In the crash log I see

/usr/local/sage/sage/src/sage/libs/ntl/ntl_ZZ_p.cpython-312-x86_64-linux-gnu.so(_ZN3NTLrsERSiRNS_4ZZ_pE+0x65)[0x729cdccc9255]
/usr/local/sage/sage/src/sage/libs/ntl/ntl_ZZ_p.cpython-312-x86_64-linux-gnu.so(+0x22f44)[0x729cdccbaf44]

which shows Sage is using NTL's object files from its own distribution. It may be an indication that Sage messes up linking with the NTL library installed "outside".

[dimpase]

such things are not easy to sandbox.

Always using an external library is certainly the preferred setup, assuming it is new enough.