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

Nice !

but this implementation doesn’t always work :
rootmod(10495044247693684635563346133510683185530563225100398940710110145105795122967339234377677245252772197706555370592225458614264149435970901536210505988826121290760438030447613971477796603470073771090674598247995429411206087834031488640531845483210456376624365673,22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458341);
   ***   at top-level: rootmod(10495044247693684635563346133510683185
   *** ^----------------------------------------------
   ***   in function rootmod: 
...Mod(1,p);F=gcd(F,liftpol(Mod(x,F)^p-x));if(pol
   *** ^---------------------
   *** Mod: forbidden division t_POL % t_INTMOD.
   ***   Break loop: type 'break' to go back to GP prompt
break>

This is just an example, I know there’s an other more direct way to get 
the solution.

Cordialement,

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