Re: Polroots/mod suggestion

[James Wanless <james@grok.ltd.uk>]

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