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

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.