Re: [flint-devel] Function Interface Updates

[<D.C...@wa...>]

Hi,

My plan for finding nth roots was to consider p-adic nth roots as roots of
a polynomial of the form f(x) = x^n - a and then basically applying
Hensel's Lemma. So if S is a root of x^n - a and S = s0 + s1p + s2p^2 +
... then if we have already calculated s0, s1,...,s(n-1) and want to
calculate sn, we write sn = s(n-1) + (bn)*p^n where

(bn)*p^n = - f(b(n-1))/f'(b(n-1)) mod p^(n+1).

Of course we will have to find the formal derivative of f, but in this
specific case this is always easy. This method is quite easy to do by hand
and should be easy to implement; I didn't find anything better during my
research, do you think this method is worth pursuing?




Daniel Ellam



>Perhaps n-th roots can be thought of as roots of a polynomial, i.e. roots
of >x^n-1. So maybe we don't even need that separately. It would be worth
it if >there is an algorithm out there which is definitely faster than
something generic.