Bill Allombert on Sun, 19 Jan 2025 11:23:18 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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

On Sun, Jan 19, 2025 at 11:09:32AM +0100, Laël Cellier wrote:
> Nice !
> 
> but this implementation doesn’t always work :
> rootmod(10495044247693684635563346133510683185530563225100398940710110145105795122967339234377677245252772197706555370592225458614264149435970901536210505988826121290760438030447613971477796603470073771090674598247995429411206087834031488640531845483210456376624365673,22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458341);

It works fine but it takes a polynomial as input, and you forgot to add 'x^2 -' before the number.
Beside this is not a square anyway, so it returns []:

?  rootmod(x^2-10495044247693684635563346133510683185530563225100398940710110145105795122967339234377677245252772197706555370592225458614264149435970901536210505988826121290760438030447613971477796603470073771090674598247995429411206087834031488640531845483210456376624365673,22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458341)
%3 = []

? issquare(Mod(10495044247693684635563346133510683185530563225100398940710110145105795122967339234377677245252772197706555370592225458614264149435970901536210505988826121290760438030447613971477796603470073771090674598247995429411206087834031488640531845483210456376624365673,22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458341))
%4 = 0

Cheers,
Bill.