|Nigel Smart on Wed, 15 Jul 1998 15:29:09 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Query about factorpadic|
> > [PS regardless of whether factorpadic can be trusted in general, I have > solved my problem for the cases in hand---I use factorpadic with > a low precision to find (or should this be "guess"?) some roots mod p^r > in finite extensions of Q_p but *then* if r is large enough (say, a bit larger > than the valuation of the root), I can use Hensel to very quickly > both verify that these are roots and to find them mod p^N for > very large N very quickly. Even though the valuation of the disc is large, > this is, in my examples, because the valuations of some of the roots are > large, and I can find the roots with small valuation without too much trouble! > In fact this seems to give me a pseudoalgorithm which works rather well.] Now this is different. Hensel to lift a FACTORIZATION requires a precision of the valuation of the discriminant, whilst to lift a ROOT requires a precision of the valuation of the derivative of f at that root. Two completely different things. So you need to determine the valuation of the derivative of f at some possible root (perhaps this can be done using say factoring mod p and differentiation mod p, should cope with all but the really tedious cases). [Gerhard is this last bit true or will there in general be lots of tedious cases ?]. Then run factorpadic with this precision and then lift the possible roots. Lets look at Kevin latest example f=x^2 + 2*x - 1023 + 65536, v_2(poldisc(f))=12 f'(x) = 2 x + 2 Hence since every root, alpha, of f is = 1 mod 2 we see that v_2(f'(alpha)) = 1. Hence to lift a root all we need do is find an element which is =1 mod 2 and s.t. v_2(f(alpha))> 3. Any number alpha=3 mod 4 will do, which is why factorpadic with precision 2 will work. Nigel -- Nigel P. Smart | mail: firstname.lastname@example.org Hewlett-Packard Laboratories | talk: +44 (0) 117 922 9338 Filton Road, Stoke Gifford | fax: +44 (0) 117 922 9285 Bristol BS34 8QZ, U.K.