# large finite fields with modulus='primitive' do not satisfy equality

I found the following discrepancy

>>> q=2**152; GF(q) == GF(q), GF(q,'a',modulus='primitive') == GF(q,'a',modulus='primitive')
(True, False)
>>> q=2**151; GF(q) == GF(q), GF(q,'a',modulus='primitive') == GF(q,'a',modulus='primitive')
(True, True)


Is this intentional? and if yes why? It seems to happen within the same library:

>>> type(GF(2**152))
<class 'sage.rings.finite_rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e_with_category'>
>>> type(GF(2**151))
<class 'sage.rings.finite_rings.finite_field_ntl_gf2e.FiniteField_ntl_gf2e_with_category'>


(tested on SageMath version 9.0, Release Date: 2020-01-01 on Kubuntu 20.04 and SageMath version 9.2, Release Date: 2020-10-24 on Arch linux with kernel 5.11.2-arch1-1)

edit retag close merge delete

Sort by » oldest newest most voted

That's a bug. I've created https://trac.sagemath.org/ticket/31547 (needs review).

more You instruct SageMath twice to create a finite field with $2^{n}$ elements with a primitive modulus. Effectively, each time this will call GF(2)['x'].irreducible_element(n, algorithm="primitive") to get such a modulus. This uses the Conway polynomial if available, and otherwise calls the ffprimroot function from PARI.

sage: exists_conway_polynomial(2, 151)
True
sage: exists_conway_polynomial(2, 152)
False


When you try out ffprimroot in PARI, you will see it is not deterministic; it returns a random primitive modulus. In total there are

sage: euler_phi(2^152 - 1)/152
18714123470861456900112662172997843377192960


different primitive moduli, so indeed you have a high probability of the comparison returning False.

more