Calculating place of large function field F_{2^128}(X)

[Sai Chandhrasekhar]

I am trying to calculate a place of the degree 8 extension field of a rational function field over GF(2^16) in SageMath. However, when I do this, it is taking a very long time and doesn't produce a result even after hours of computation. 

The commands I am running:

sage: F.<x> = FunctionField(GF(2^16))
sage: R.<y> = F[]
sage: f = y^8 + x*y^6 + x^2*y^4 + y^3 + x
sage: K.<z> = F.extension(f)

sage: K.places(8)[:1]

The goal of doing this is to evaluate a basis of the Riemann-Roch space of a divisor of F at a degree 8 place of K, in order to embed a length 8 vector of elements in F_{2^16} into a single element in F_{2^128}. I am running this in SageMath 10.5 on a Ubuntu 22.04 virtual machine using VirtualBox 7.0.14. 

[Nils Bruin]

On Tuesday, 10 December 2024 at 18:29:14 UTC-8 skchandh...@gmail.com wrote:

I am trying to calculate a place of the degree 8 extension field of a rational function field over GF(2^16) in SageMath. However, when I do this, it is taking a very long time and doesn't produce a result even after hours of computation. 

The commands I am running:

sage: F.<x> = FunctionField(GF(2^16))
sage: R.<y> = F[]
sage: f = y^8 + x*y^6 + x^2*y^4 + y^3 + x
sage: K.<z> = F.extension(f)

sage: K.places(8)[:1]

This line produces a list of all places of F of degree 8. So that's a huge list! It wouldn't fit in memory. If you want to get some places to experiment with, you probably want to create them without creating all degree 8 places. Perhaps something like

K(x-1).divisor().support()

gives some usable places.

[Kwankyu]

There is a method F.get_place(8) that returns a place of degree 8, which perhaps suits your purpose. In less than an hour, I got

sage: a = K.get_place(8); a

Place (x^2 + x + z16^11 + z16^2 + z16, z^4 + ((z16^15 + z16^14 + z16^12 + z16^10 + z16^9 + z16^4 + z16^3 + 1)*x + z16^15 + z16^12 + z16^11 + z16^10 + z16^7 + z16^6 + z16^4 + z16^2 + z16 + 1)*z^3 + ((z16^14 + z16^13 + z16^9 + z16^8 + z16^7 + z16^6 + z16^5 + z16^2 + 1)*x + z16^15 + z16^14 + z16^13 + z16^11 + z16^10 + z16^8 + z16^6 + z16^5 + z16^3 + z16^2 + z16 + 1)*z^2 + ((z16^15 + z16^14 + z16^12 + z16^11 + z16^9 + z16^8 + z16^7 + z16^6 + z16^5 + z16^4 + z16^3 + z16^2 + z16)*x + z16^15 + z16^13 + z16^12 + z16^11 + z16^10 + z16^8 + z16^7 + z16^5 + z16^4 + 1)*z + (z16^15 + z16^14 + z16^11 + z16^7 + z16^6 + z16^4 + z16 + 1)*x + z16^14 + z16^13 + z16^10 + z16^8 + z16^7 + z16^6 + z16^5 + z16^4 + z16^3 + 1)

On the other hand, I think the function field machinery needs performance improvement in every aspects.

Addition data:

sage: d = a.divisor()

sage: d.basis_function_space()
[1,
 (1/(x^2 + x + z16^11 + z16^2 + z16))*z^5 + ((z16^13 + z16^10 + z16^9 + z16^7 + z16^6 + z16^5 + z16^3 + z16^2)/(x^2 + x + z16^11 + z16^2 + z16))*z^4 + ((x + z16^14 + z16^13 + z16^11 + z16^10 + z16^7 + z16^3 + z16^2 + 1)/(x^2 + x + z16^11 + z16^2 + z16))*z^3 + (((z16^14 + z16^13 + z16^10 + z16^9 + z16^6 + z16^5 + z16^4 + z16)*x + z16^14 + z16^11 + z16^10 + z16^9 + z16^8 + z16^2 + z16)/(x^2 + x + z16^11 + z16^2 + z16))*z^2 + ((x^2 + (z16^12 + z16^10 + z16^8 + z16^5 + z16^3 + z16^2 + z16)*x + z16^15 + z16^8 + z16^6 + z16^5 + z16^3 + z16^2 + 1)/(x^2 + x + z16^11 + z16^2 + z16))*z + ((z16^14 + z16^11 + z16^9 + z16^8 + z16^7 + z16^5 + z16^4)*x + z16^10)/(x^2 + x + z16^11 + z16^2 + z16),
 ((z16^15 + z16^14 + z16^13 + z16^12 + z16^10 + z16^9 + z16^8 + z16^7 + z16^6 + z16^5 + z16^2 + z16 + 1)/(x^2 + x + z16^11 + z16^2 + z16))*z^6 + ((z16^11 + z16^9 + z16^7 + z16^6 + z16^5 + z16^4 + z16^3 + z16)/(x^2 + x + z16^11 + z16^2 + z16))*z^5 + (((z16^15 + z16^14 + z16^13 + z16^12 + z16^10 + z16^9 + z16^8 + z16^7 + z16^6 + z16^5 + z16^2 + z16 + 1)*x + z16^14 + z16^13 + z16^8 + z16^6 + z16^2 + z16 + 1)/(x^2 + x + z16^11 + z16^2 + z16))*z^4 + (((z16^11 + z16^9 + z16^7 + z16^6 + z16^5 + z16^4 + z16^3 + z16)*x + z16^7 + z16^6 + z16^5 + z16^2 + z16)/(x^2 + x + z16^11 + z16^2 + z16))*z^3 + (((z16^15 + z16^14 + z16^13 + z16^12 + z16^10 + z16^9 + z16^8 + z16^7 + z16^6 + z16^5 + z16^2 + z16 + 1)*x^2 + (z16^14 + z16^13 + z16^12 + z16^11 + z16^10 + z16^9 + z16^7 + z16^6 + z16^5 + z16^4 + z16^2)*x + z16^14 + z16^13 + z16^9 + z16^7 + z16^6 + z16^4 + z16^3 + z16^2 + z16 + 1)/(x^2 + x + z16^11 + z16^2 + z16))*z^2 + (((z16^11 + z16^9 + z16^7 + z16^6 + z16^5 + z16^4 + z16^3 + z16)*x^2 + (z16^15 + z16^13 + z16^12 + z16^11 + z16^10 + z16^9 + z16^6 + z16^5 + z16^3 + 1)*x + z16^9 + z16^7 + z16^3 + z16^2)/(x^2 + x + z16^11 + z16^2 + z16))*z + (z16^12 + z16^11 + z16^10 + z16^7 + z16^6 + z16^3 + z16^2 + z16 + 1)/(x^2 + x + z16^11 + z16^2 + z16),
 (1/(x^2 + x + z16^11 + z16^2 + z16))*z^7 + ((z16^14 + z16^13 + z16^11 + z16^10 + z16^7 + z16^6 + z16^4 + z16^3 + z16^2 + z16)/(x^2 + x + z16^11 + z16^2 + z16))*z^6 + ((x + z16^11 + z16^9 + z16^8 + z16^7 + z16^5 + z16^2 + z16 + 1)/(x^2 + x + z16^11 + z16^2 + z16))*z^5 + (((z16^14 + z16^13 + z16^11 + z16^10 + z16^7 + z16^6 + z16^4 + z16^3 + z16^2 + z16)*x + z16^15 + z16^14 + z16^13 + z16^11 + z16^10 + z16^9 + z16^7)/(x^2 + x + z16^11 + z16^2 + z16))*z^4 + ((x^2 + (z16^11 + z16^9 + z16^8 + z16^7 + z16^5 + z16^2 + z16 + 1)*x + z16^14 + z16^13 + z16^12 + z16^8 + z16^6 + z16^4 + z16 + 1)/(x^2 + x + z16^11 + z16^2 + z16))*z^3 + (((z16^14 + z16^13 + z16^11 + z16^10 + z16^7 + z16^6 + z16^4 + z16^3 + z16^2 + z16)*x^2 + (z16^13 + z16^9 + z16^4 + z16^3 + z16^2 + z16 + 1)*x + z16^8 + z16^3 + 1)/(x^2 + x + z16^11 + z16^2 + z16))*z^2 + (((z16^11 + z16^9 + z16^8 + z16^7 + z16^5 + z16^2 + z16 + 1)*x^2 + (z16^15 + z16^8 + z16^3 + 1)*x + z16^12 + z16^11 + z16^10 + z16^7 + z16^6 + z16^2)/(x^2 + x + z16^11 + z16^2 + z16))*z]

[Kwankyu]

Additional data:

sage: d.dimension()
4

[Sai Chandhrasekhar]

I tried doing this and it still takes a long time. 

[Kwankyu]

On Sat, Dec 14, 2024 at 9:09 AM Sai Chandhrasekhar <skchandh...@gmail.com> wrote:

When I ran it, it took a little over an hour. Is there a way to speed up this calculation? 

No. 

[Nils Bruin]

Well ... it depends on what you want to know. The curve you are describing is already defined over GF(2). It is of genus 5, so its zeta function is determined by the number of places up to degree 5. That gets you the whole zeta function, so if you're interested in the number of places of degree 8 over GF(2^16)  [i.e., the places of degree 19 over GF(2), with some careful inclusion-exclusion counting] then you'd be able to get that info from the zeta function without having to do explicit computations with places.

In fact, to get information about places of degree 8 over GF(2^16), perhaps you can get the information you want already from the corresponding point of degree 1 over GF(2^19).

[Sai Chandhrasekhar]

I want to compute a single place of degree 8 so I can use it as described in the OP. 

[Sai Chandhrasekhar]

Is there a way I can take the place I got and input it into future calculations without having to recalculate it every time I run the code? 

[Nils Bruin]

On Saturday, 14 December 2024 at 09:28:37 UTC-8 skchandh...@gmail.com wrote:

I want to compute a single place of degree 8 so I can use it as described in the OP.

 

 If you want to evaluate a function at a place, you'll just get a value in the residue field. In the case of a degree 8 place, that will be a degree 8 extension of GF(2^16), so indeed in GF(2^128). The value you get will be exactly the value that you get by evaluating the corresponding degree 1 point over GF(2^128). So from what you describe, it would seem you don't need to bother with degree 8 places over GF(2^16) but you can just work with degree 1 points over GF(2^128). The advantage of that is that a lot of the computational complexity gets pushed into the field arithmetic (which is highly optimized), instead of the maximal order machinery of function fields.

It shouldn't be hard to get your hands on a point over GF(2^128). They are as abundant as points over lower degree fields. If you really want to make sure it's really a degree 8 place over GF(2^16) you probably want to check that its Frobenius orbit has the right length for that.

[Kwankyu]

On Monday, December 16, 2024 at 2:21:10 PM UTC+9 skchandh...@gmail.com wrote:

Is there a way I can take the place I got and input it into future calculations without having to recalculate it every time I run the code? 

p.save('file')

saves the object to a file. Later, you can reload the object by p = load('file')

p.prime_ideal().gens()

gives the generators of the prime ideal (of the maximal order) defining the place. You may save the generators instead to reconstruct the place later.  

[Sai Chandhrasekhar]

Can you go into more detail on this? 

[Kwankyu]

I meant

sage:  F.<a> = GF(2)
....:  K.<x> = FunctionField(F)
....:  R.<Y> = PolynomialRing(K)
....:  L.<y> = K.extension(Y^4 + Y - x^5)
sage: g = L.get_place(2)
sage: g
Place (x, y^2 + y + 1)
sage: g.prime_ideal().gens()
(x, y^2 + y + 1)
sage: O = L.maximal_order()
sage: h = O.ideal((x, y^2 + y + 1)).place() # reconstruct the place from the generators
sage: g == h
True