any_root is slow for finite field polynomials

[roed314]

The intention of any_root was to provide a faster method of getting a root when you don't need them all. Unfortunately, the current implementation isn't faster than just factoring (at least in some cases).

sage: k.<a> = GF(3^120)
sage: R.<x> = GF(3)[]
sage: f = R.irreducible_element(60)
sage: %time z = f.any_root()
CPU times: user 22.6 s, sys: 115 ms, total: 22.7 s
Wall time: 22.8 s
sage: %time w = f.roots()[0]
CPU times: user 514 ms, sys: 16.3 ms, total: 531 ms
Wall time: 526 ms

We should test to see where the implementation of any_root should be improved or just switched to f.roots()[0].

Component: finite rings

Keywords: padicBordeaux

Issue created by migration from https://trac.sagemath.org/ticket/28479

[roed314]

Changed keywords from none to padicBordeaux

[DaveWitteMorris]

comment:2

It seems to me that if a polynomial over a finite field is irreducible over its field of definition, then finding one root is computationally equivalent to finding all of the roots. This is because all of the other roots can be obtained by applying powers of the Frobenius automorphism to the root that is known. I think this explains the example that was given.

On the other hand, if a polynomial is reducible, then knowing a root of one irreducible factor does not give any information about the roots of the other irreducible factors. However, I did not look at the algorithm that is used by any_root(), so I do not know whether it does something that gives information about all irreducible factors at once. This might be worth investigating or testing.

[embray]

comment:3

Ticket retargeted after milestone closed

[mkoeppe]

comment:4

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:6

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[remyoudompheng]

I think the issue (as reported in the first message) is no longer valid as of Sage 9.8