Re: Polroots/mod suggestion

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

On 13 Mar 2011, at 14:45, Bill Allombert wrote:

> On Sun, Mar 13, 2011 at 12:53:15PM +0000, James Wanless wrote:
> > (Right, hopefully I really do mean to post to _this_ list this  
> > time :)
> > I wonder if the devs would be interested in the following suggestion
> > for finding roots of a general nth order polynomial, or same mod p:
> > The idea is basically recursive completion of the square ie, solve
> > for roots using the standard quadratic solution formula, but
> > iterated.
> > Each level of iteration would allow equations of up to 2^nth order
> > to be solved, as n++
>
> How this is supposed to work ?

Maybe I should have used the word "nested' rather than 'iterated'...

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

> Cheers,
> Bill.