factoring in non-maximal orders.

[Kevin Buzzard <kevin.m.buzzard@gmail.com>]

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