James Wanless on Sun, 13 Mar 2011 16:04:43 +0100

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

Re: Polroots/mod suggestion

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