James Wanless on Sat, 02 Apr 2011 16:14:19 +0200

 Re: Polroots/mod suggestion

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

```

• Index(es):