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

[Denis Simon <denis.simon@unicaen.fr>]

Hi Laël,

nfroots() is adapated if you are working over a number field.
In your case, you are instead working over a finite field.

The function factor() works over the ring/field containing the coefficients.
For example, in order to find the square root of -1 mod 17, you can write :
factor( (x^2+1)*Mod(1,17))

You can also use the function polrootsmod, which is dedicated to root finding over finite fields.
Again, you can write :
polrootsmod(x^2+1,17)

But the simplest is to write
sqrt(Mod(-1,17))
or
Mod(-1,17)^(1/2)

Sincerely,
Denis SIMON.



----- Mail original -----
> De: "Laël Cellier" <lael.cellier@laposte.net>
> À: "pari-users" <pari-users@pari.math.u-bordeaux.fr>
> Envoyé: Samedi 18 Janvier 2025 14:47:18
> Objet: Some questions on how to improve Berlekamp‑Rabin algorithm’s implementation

> 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() ?
> 
> And at the end use polcoeff() ?
> 
> Though in reality I admit I don't understand how to perform some steps
> by hand…
> 
> Cordialement,