Kevin Buzzard on Fri, 15 Apr 2016 17:22:26 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
factoring in non-maximal orders. |
Say f(x) is a polynomial in one variable, monic, with integer coefficients, and of reasonable degree (<=20 or so) but its discriminant is not prime and is furthermore far too large to be factored into primes using known methods. Say K is the number field Q[x]/(f) and say I have an element t in K which I know is an algebraic integer (e.g. because it is in Z[x]). Say p is a small prime number (<= 100) and I'm interested in the reductions of t modulo the primes above p in the integers of K. I can't compute the integers of K though, because of a global issue (can't factorise the discriminant) which is of no relevance to the question. What I propose to do (or rather what I just told a PhD student to do ;-) ) is this: n=nfinit([f,[p]]); X=idealfactor(n,p); P1=nfmodprinit(n,X[1,1]) nfeltreducemodpr(n,t,P1) The first line is something I'd never seen before. It is a special input format for nfinit and in the manual (second page of what you get if you type ??nfinit) it explains that n will now be a number field with an order which is definitely maximal at p but might not be maximal at other primes. We now factor p in n, equipped with its possibly incorrect belief about what the maximal order is, take a prime ideal in the factorization and reduce t modulo that prime. Now abstractly knowing an order which is maximal at p is enough global information to perform the now local problem of factoring p (if R is the maximal order and S is my order then maybe S is a proper subset of R but S tensor Z_p = R tensor Z_p and this ring contains all the information I need e.g. residue field sizes plus map from S to this residue field), so my code above *could* in theory work. However whether or not it provably does work depends on what is actually going on in the idealfactor command. For example perhaps there's some clever tweak where you can get idealfactor to run more quickly in practice if you do some other crazy algorithm which needs the order to be maximal at other primes (for example at 2!). Whilst the manual told me about this special input format for nfinit, it doesn't give me a complete list of health warnings if I try to push my luck. Is this code likely to work? Kevin