James Wanless on Sun, 13 Mar 2011 13:55:22 +0100

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

Polroots/mod suggestion

(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++ 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 reserve the right to pinch that code back for polrootsmod use in my GMP-ECPP! :)