Re: [flint-devel] Function Interface Updates

[Bill H. <goo...@go...>]

I don't know if this looks efficient or not. Isn't there a method
which gives you more than one coefficient at a time.

Also, this looks completely generic in that if I had an algorithm for
finding a root of an arbitrary polynomial, I could just feed it x^n-a
and it would essentially do exactly as you described, and not be any
slower.

So perhaps there is no need to have it implemented separately for this reason.

I'm also unsure that you can expect the solution to always exist in
Zp. Isn't it sometimes in Qp?

Bill.

2008/8/8  <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.
>
>
>
>
>
>
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>