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

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)


Produces:

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

You may just iterate on F directly:

sage: F.<x> = GF(3^15)
sage: for a in F:
....:     print(a)
....:
[...]

( 2020-04-03 11:31:35 +0100 )edit

Sort by » oldest newest most voted

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.

more

@rburing tank you very much for your solution.

( 2020-04-03 10:55:28 +0100 )edit