Ask Your Question

Why is SageMath fail to generate elements in finite field $GF(3^{15})$

asked 2020-04-03 07:11:09 +0200

updated 2020-04-03 07:12:33 +0200

I would like to generate elements of finite filed $GF(3^{15})$. To do so I have used the following code :

F.<x> = GF(3^15)
for i in range(3^15):
    print i,"=>", F.fetch_int(i)

But this code failed to generate elements, occurring errors. On there hand the above code works fine for $GF(3^{2})$ given below:

F.<x> = GF(3^2)
for i in range(3^2):
    print i,"=>", F.fetch_int(i)


0 => 0
1 => 1
2 => 2
3 => x
4 => x + 1
5 => x + 2
6 => 2*x
7 => 2*x + 1
8 => 2*x + 2.

Where is the problem?

edit retag flag offensive close merge delete


You may just iterate on F directly:

sage: F.<x> = GF(3^15)
sage: for a in F:
....:     print(a)
Sébastien gravatar imageSébastien ( 2020-04-03 11:31:35 +0200 )edit

1 Answer

Sort by » oldest newest most voted

answered 2020-04-03 10:44:56 +0200

rburing gravatar image

See the documentation of GF; the different implementations depending on the size are the first thing mentioned.

In particular, $\log_3(2^{16}) \approx 10.09$ means GF(3^2), ..., GF(3^10) use the Givaro implementation while GF(3^11), GF(3^12), ... use the PARI implementation. The fetch_int method is not available in the PARI implementation, which explains the error.

Note that the mapping you are interested in is very simple: for example $7$ is $2\cdot 3 + 1$, so its ternary (base 3) digits are 21, and the corresponding element of F.<x> = GF(3^k) is 2*x + 1 ($3$ is replaced by $x$).

Since F is a vector space over GF(3) with basis 1, x, x^2, ..., x^(k-1), a vector (or list) of elements of GF(3) can be converted into F. For example, F([1,2]) yields 2*x + 1; the reason for the "reversal" is that the "digits" are interpreted in little endian order. This is convenient because the output of e.g. 7.digits(3) is also in little endian order, yielding [1,2]. We can put this together:

F.<x> = GF(3^15)
for i in srange(F.cardinality()):
    print(i, '=>', F(i.digits(3)))

Though it is kind of pointless to print that gigantic list when you already understand the mapping.

Also, I suppose that a fetch_int method could be added to the PARI implementation for convenience.

edit flag offensive delete link more


@rburing tank you very much for your solution.

BSFU gravatar imageBSFU ( 2020-04-03 10:55:28 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower


Asked: 2020-04-03 07:11:09 +0200

Seen: 326 times

Last updated: Apr 03 '20