Ask Your Question
1

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

asked 2021-03-24 13:59:29 +0100

dragomang87 gravatar image

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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
1

answered 2021-03-24 16:12:51 +0100

roed gravatar image

updated 2021-03-24 16:44:57 +0100

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

edit flag offensive delete link more
1

answered 2021-03-24 16:34:53 +0100

rburing gravatar image

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2021-03-24 13:52:27 +0100

Seen: 304 times

Last updated: Mar 24 '21