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 09:59:27PM +0100, Laël Cellier wrote:
> Merci,
> 
> Where can I find the source code of polrootsmod please ? I’m meaning in
> which file and which line ?

src/basemath/FpX_factor.c line 252 for example.

https://pari.math.u-bordeaux.fr/cgi-bin/sgitweb.cgi?p=pari.git;a=blob;f=src/basemath/FpX_factor.c;h=6492b724e655d4a3daf2b5da3b8f69b549df302c;hb=HEAD#l252

> Is there a Pari/ɢᴘ version or only C is available ? Anyway, I’d take the
> later if this is the only option…

This is in C.

But this is enough to do in GP:
(this version returns only one root).

rootmod(F,p)=
{ 
  F = F*Mod(1,p);
  F = gcd(F,liftpol(Mod(x,F)^p-x));
  if (poldegree(F)<=0,return([]));
  while(poldegree(F)>1,
    my(G=gcd(F,liftpol(Mod(x-random(p),F)^((p-1)/2))-1));
    my(d=poldegree(G));
    if (d<=0, next);
    if (d<poldegree(F)-d,F=G,F\=G));
  -polcoef(F,0)/polcoef(F,1);
}

? rootmod(x^2-13,nextprime(2^1000))
%9 = Mod(6379310556240012429311478707645917563709750378608021873668848098249376586762722469082459556753012826585180459784577026521419292860806283780859063202392283995938255376634928395704317795768580058270006054861789044483907645080613123632155559069974735771589968378627096079956063004254846772065157023862340,10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069673)
? %^2
%10 = Mod(13,10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069673)

Cheers,
Bill.