Re: Query about factorpadic

[Nigel Smart <nsma@hplb.hpl.hp.com>]

> 
> [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: nsma@hplb.hpl.hp.com
Hewlett-Packard Laboratories          |  talk: +44 (0) 117 922 9338
Filton Road, Stoke Gifford            |  fax:  +44 (0) 117 922 9285
Bristol BS34 8QZ, U.K.