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, II 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...] J