Dear Misja, What I had in mind was something like this. Given some monstrous number field K with enormous discriminant, and some small prime p, you can ask Sage for a p-maximal order and it'll find one reasonably quickly, as you know.
All I was saying is that if the resulting order O is of the form Z[X] / (f), for some polynomial f in Z[X] -- i.e. if "O.ring_generators()" is a list of length 1 -- then you can quickly compute all possible maps O --> Fp-bar by just factoring f modulo p. (Sage really ought to have this coded up already; sadly it doesn't, but it's trivial to implement.) Maybe this isn't a terribly helpful remark; I don't know how likely it is that the orders you work with have this form. David On 17 March 2016 at 16:33, Misja <[email protected]> wrote: > Hi David, > > Thank you very much for this helpful reply! You're right, of course: my > example was silly. Here's an example with a 104 digit discriminant that my > code just got stuck on (for a bit). > > x=polygen(QQ); > K=NumberField(x^5 + 16255223088*(x^4) - 330681713908949415936*(x^3) - > 5058938091171222191449571328000*(x^2) - > 2907488578277274989701398473183198183424*x + > 76587534178613500902724649685949865805676749520896,'a'); > fact=K.factor(5); > print K.residue_field(fact[0][0]); > > What I am trying to do is to calculate reductions of modular forms modulo > some prime ideal P. However, the coefficients of such a modular form may > lie in a number field with a 1000 digit discriminant and I want to avoid > trying to factor this if I can, hence my trying to use p-maximal orders. > > Could you explain a bit more what you mean in the monogenic case? Could > you do something like EquationOrder(K.defining_polynomial(),'alpha'), take > a p-maximal order there and then do what you are suggesting? Although, > actually, I don't know if sage can calculate a p-maximal order of a given > order. > > Misja > > > > On Thursday, 17 March 2016 15:50:59 UTC, David Loeffler wrote: >> >> There are two reasons why people work with non-maximal orders: because >> they're actually interested in their arithmetic; or (more often) because >> they're working with examples where the discriminant is too large to >> efficiently factor. Which is the case in your problem? In the example you >> give, you're letting PARI choose the order for you, but the discriminant is >> small enough that one can find a maximal order in a few milliseconds anyway >> (and Sage is perfectly happy to work with residue fields of maximal >> orders). >> >> If you genuinely don't want to factor the discriminant, but the orders >> you're interested in are "monogenic" (generated by a single element over >> Z), then you can just factor the characteristic polynomial of the generator >> over Fp and that gives you the factorisation, and the reduction maps, >> immediately. >> >> Can you give an example of a case you'd be interested in where the >> maximal order is really too big to easily find? >> >> Regards, David >> >> On 11 March 2016 at 14:42, Misja <[email protected]> wrote: >> >>> For a number field N I am trying to factor an integral prime p in a >>> p-maximal order Op. In the end I would like a map from the quotient of the >>> p-maximal order Op/P (for P|p) to some finite field in Sage's standard >>> finite field form, but I can't quite figure out how to do it. >>> >>> Firstly, Sage doesn't have ideals or residue fields of non-maximal >>> orders implemented, so I am trying to compute the factorisation of p in Op >>> via the PARI/GP interface with sage. I think this can be done, for example, >>> in the following way, in which we compute a 7-maximal order of the number >>> field defined by x^8+x^3-13*x+26 and compute all primes above 7 in this >>> order. >>> >>> x=polygen(QQ); >>> >>> nf=gp.nfinit([x^8 + x^3 - 13*x + 26,[7]]); #Note the [7] at the end, >>> indicating a 7-maximal order only. >>> nf; >>> >>> fact=gp.idealprimedec(nf,7); >>> fact; >>> >>> res_field_sizes=[]; >>> for i in fact: >>> res_field_sizes.append(i[1]**i[4]); >>> >>> res_field_sizes; >>> >>> Now, for each element fact[i] of fact, I would like to compute a >>> homomorphism Op->Op/fact[i]->GF(res_field_sizes[i-1],'gen') - note that >>> we're using a vector in pari/gp and a list in sage hence fact[i] >>> corresponds to res_field_sizes[i-1]. I can't quite get this to work. >>> >>> I feel like there are two options: >>> >>> 1. Translate the p-maximal order and prime factorisation back to >>> sage. Take a poly quotient or something. Map this to a finite field. >>> 2. Keep on working in pari/gp and use, for example, nfeltreducemodpr >>> to reduce elts of Op to the residue field (does this really calculate >>> Op/P >>> if the nf.zk is a non-maximal Z-basis?). Map this to a finite field >>> somehow. Translate back to Sage. >>> >>> I can't really get either approach to work at the moment. But I wouldn't >>> call myself a big Sage or PARI/GP expert, so it is very possible that I am >>> missing something. >>> >>> Any suggestions would be much appreciated! >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "sage-support" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> To post to this group, send email to [email protected]. >>> Visit this group at https://groups.google.com/group/sage-support. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> -- > You received this message because you are subscribed to the Google Groups > "sage-support" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at https://groups.google.com/group/sage-support. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
