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

[Laël Cellier <lael.cellier@laposte.net>]

Merci,

Where can I find the source code of polrootsmod please ? I’m meaning in 
which file and which line ?
Is there a Pari/ɢᴘ version or only C is available ? Anyway, I’d take the 
later if this is the only option…

Sincerely,

Le 18/01/2025 à 19:50, Bill Allombert a écrit :
> 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.