Implement finding square roots in FiniteFields category

[vincentmacri]

Problem Description

Algorithms exist to compute square roots in arbitrary finite fields. For instance, see chapter 7 of volume 1 of Algorithmic Number Theory by Erich Bach and Jeffrey Shallit. It would be useful if Sage implemented some of these, as well as algorithms for related computations (nth roots, checking if an element is a square, etc.).

Proposed Solution

These algorithms should be implemented in the FiniteField category.

Alternatives Considered

Only implement square roots and related functions for more specific types of finite fields (for example, quotient ring by an irreducible polynomial). I think doing that would be good to especially if it's more efficient than the general algorithm. But it would still be good to generically be able to take square roots in any finite field.

Additional Information

No response

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

[vincentmacri]

If anyone wants to implement this, feel free. I'd be happy to review it. Otherwise, I might try to implement this myself when I have the time.

[kevinpaul468]

hey, ill do it # new contributing to sage, but i am somewhat familiar with the language and the concept

should these functions be methods of a FiniteField or just functions which take a element and FiniteField as input ?

[user202729]

We can already do that?

sage: GF(4).0.sqrt()
z2 + 1

There are only so many finite fields right?

Or do you mean like

sage: R.<x> = GF(2)[]
sage: S.<y> = R.quotient(x^2+x+1)
sage: y.sqrt()

( @kevinpaul468 if you want to implement this, I suppose it suffices if the code above works and the method is implemented in the FiniteFields category. See https://doc-pr-39549--sagemath.netlify.app/html/en/reference/categories/sage/categories/finite_fields#sage.categories.finite_fields.FiniteFields.ElementMethods )

In that case we should definitely reuse the existing algorithm (it's easy to determine the structure by (prime field, degree over prime field, minimal polynomial of generator)) instead of reimplementing it from scratch.

How about this?

sage: R.<x> = ZZ[]
sage: S.<y> = R.quotient((2, x^2+x+1))
sage: y.sqrt()

… actually in this case the current framework doesn't even know S is finite, let alone a field.

Would also be interesting to implement this for tensor product of finite fields (in this case the most specific class we can work with is finite dimensional algebra over its prime field https://doc.sagemath.org/html/en/reference//algebras/sage/algebras/finite_dimensional_algebras/finite_dimensional_algebra.html I guess). Just check the algebra is commutative, then decompose it into a product of finite fields. But then before that we need to implement tensor product and decomposition into tensor product…

[kevinpaul468]

sage: GF(4).0.sqrt()
z2 + 1

is think this isnt about finding roots of the elements but about finding the square root of generators of finite fields
like in this case 4 has Z^2 as a genator so Z^2 + 1 is the output

i think what @vincentmacri wants is the roots of the elements in a arbitary finite field

like

F = GF(11)
roots(3,F)
should check if 3 has a sqrt , if it does, then compute is

the output in this case should be 5,6

as 5*2 mod 11 = 3 and 6^2 mod 11 = 3

correct me if i am wrong, these things are a bit new for me

[vincentmacri]

This is a bit confusing to write about since Sage has a FiniteField constructor but also a category called FiniteFields, so please bear with me.

Or do you mean like

sage: R.<x> = GF(2)[]
sage: S.<y> = R.quotient(x^2+x+1)
sage: y.sqrt()

Yes, something like this is what I meant. The quotient group of polynomials over a finite field modulo an irreducible polynomial is a field, and the current Sage framework knows this. If you do S in FiniteFields() you'll get True. This was exactly the type of case that motivated me opening this issue, but I'm sure there are other ways to construct objects in Sage that are members of the FiniteFields category that could also benefit from a square root function.

Right now FiniteField(p^n) (or alternatively GF(p^n)) has a square root method, and that works fine. But you can construct objects in Sage that are members of the FiniteFields category (like S above) but not an instance of FiniteField.

This feature request is to implement a square root (and possibly related methods like is_square or nth_root depending on how difficult and whether they are needed anyway, I think we'll need is_square for the square root algorithms in the source I mentioned) for the FiniteFields category. Only if the generic square root algorithm is as efficient as the one we have in FiniteField should we remove the sqrt function from FiniteField. If the generic square root algorithm for FiniteFields isn't as efficient, we should leave both in place, so Sage will use the fastest algorithm available for whatever finite field you're working over.

[vincentmacri]

Right now this example gives a NotImplementedError, saying that is_square isn't implemented for S:

sage: R.<x> = GF(2)[]
sage: S.<y> = R.quotient(x^2+x+1)
sage: y.sqrt()

What I would like is to have is this:

sage: R.<x> = GF(2)[]
sage: S.<y> = R.quotient(x^2+x+1)
sage: root = y.sqrt()
sage: root in S
True
sage: root^2 == y
True

[vincentmacri]

I may be overestimating how generally finite field square root algorithms work in practice, in which case I will satisfied if we only implement square roots for the case of polynomial rings over a finite field quotiented by an irreducible polynomial.

[kevinpaul468]

I'm not mathematically sure how to implement this, but i think i know what you want
Ill try researching upon it and try to implement it (don't hope much)

[user202729]

Only if the generic square root algorithm is as efficient as the one we have in FiniteField should we remove the sqrt function from FiniteField. If the generic square root algorithm for FiniteFields isn't as efficient, we should leave both in place, so Sage will use the fastest algorithm available for whatever finite field you're working over.

That's not what I mean.

What I want to say is, this should be implemented by finding an isomorphism from whatever field it originally is to the canonical GF(p^e), square root there, then port back. (same thing for discrete logarithm and such.)

[vincentmacri]

I'm not mathematically sure how to implement this, but i think i know what you want Ill try researching upon it and try to implement it (don't hope much)

If you can get your hands on a copy of Algorithmic Number Theory by Erich Bach and Jeffrey Shallit, I think all the relevant algorithms are described in that book.