James Wanless on Sat, 02 Apr 2011 16:14:19 +0200

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

Re: Polroots/mod suggestion

This would necessitate the introduction/evaluation of "Wanlessians",
defined recursively s.t. W[n] = sqrt(-W[n-1]).
So for instance, W[0]=1, W[1]=i, W[2]=(-1+i)/(sqrt(2)), ...
[in the mod p case, W[n] = sqrt(-W[n-1]) mod p]
If this works, and you can successfully implement it in code, I

I would be quite surprised if it worked.

Am I correct in saying that every polynomial (/mod p) of degree d will have exactly d (including multiple) roots? If so, then the current implementation in PARI (and mine :), using Berlekamp, doesn't always find them all.
This was a suggestion for improvement...

Hmmmm... interesting!
It would appear that in the _modular_ case, at least, this is not correct and a degree d polynomial will not necessarily have d roots (or even any). For example the polynomial x^4+x^3-2x^2-3x-35, over the field F_59, definitely has no roots (I checked, by evaluating for all possible solutions one-by-one).
[So perhaps one can do no better than Berlekamp after all...]