Gerhard Niklasch on Wed, 15 Jul 1998 17:07:02 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Query about factorpadic |
In further response to our little thread: > Date: Wed, 15 Jul 1998 15:39:52 +0100 > Message-Id: <647.199807151439@omega.ex.ac.uk.maths.exeter.ac.uk> > From: "John Cremona (Maths)" <cremona@maths.ex.ac.uk> [rearranging...] > I think that this discussion should probably not be going on via the > pari users' list...? Why not? It's about how to use PARI/GP to do one's mathematics. > Nigel is wrong: when x is odd, the valuation of 2x+2 can be anything > positive, even infinite (x=-1). For a quadratic there cannot be any > distinction between lifting a root and lifting a factorization. (The valuation of the discriminant can be computed in terms of the valuations of f'(alpha) at each root alpha -- indeed, since the discriminant of f, up to sign, is the resultant of f and f', it is also the product of the f'(alpha), up to a constant which shouldn't matter if f was monic to start with. Everything with a pinch of salt about normalizations of valuations etc when the roots do not lie in Q_p itself but in an extension.) > It seems that factorpadic(f,p,r) is not the same as factoring f mod > p^r in (Z/p^r)[X], but rather the mod p^r approximation to the ACTUAL > p-adic factorization. Yes. Let's have a glance at a chunk of code from factorpadic4() in src/basemath/polarit1.c: ---8<--- poly=squarefree(f,&ex); nbpoly=lg(poly)-1; res=cgetg(3,t_MAT); res[1]=lgetg(n+1,t_COL); res[2]=lgetg(n+1,t_COL); for (j=1,i=1; i<=nbpoly; i++) { long av1 = avma; fx=(GEN)poly[i]; mfx=ggval(discsr(fx),p); m = (r<=mfx)?mfx+1:r; w = factmod(fx,p); g = bestnu((GEN)w[1]); if (lg(w[1])==2) resint = nilordpadic(p,m,fx,mfx,g); else resint = Decomppadic(p,m,fx,mfx,polx[v],fx,g); --->8--- We begin with squarefree factorization (so Kevin's polynomial was already squarefree) followed by a loop over the factors obtained at this first stage. Then m is set as large as necessary based on the input precision r as well as the valuation of the discriminant of the current factor (discsr is the subresultant algorithm), the factor is factored mod p, and each piece is processed further at precision m... In other words, the round4 implementation of factorpadic() (selected by default) knows about the precision required in the worst case. Gerhard