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