Re: Some questions on how to improve Berlekamp‑Rabin algorithm’s implementation

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Jan 18, 2025 at 02:47:18PM +0100, Laël Cellier wrote:
> Bonjour,
> 
> the https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Rabin_algorithm is an
> algorithm for computing square roots on prime numbers or prime powers.
> It's description makes it mostly trivial to implement using Mod() operations
> but I was wondering if it was possible to use more higher level functions
> like factor() or even nfroots() ?

Berlekamp algorithm is implemented in the GP function polrootsmod.

Now if you want to reimplement it in GP, this is rather easy using
POLMOD of INTMOD, soing something like Mod(x-random(p),F)^((p-1)/2)
(the advice of replacing F by F(x+z) is not a good idea).

Cheers,
Bill.