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,


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 P. Smart                        |  mail:
Hewlett-Packard Laboratories          |  talk: +44 (0) 117 922 9338
Filton Road, Stoke Gifford            |  fax:  +44 (0) 117 922 9285
Bristol BS34 8QZ, U.K.