primes_of_degree_one iterator for NumberField_generic

[93749b3a-c0a4-47a7-b178-004ba08b0b97]

It would be useful, for multimodular algorithms (and more!) to be able to find degree one primes in a number field.

For posterity, the following IRC transcript, copied from #903, is relevant:

ncalexan-827: wstein-1606: is there a good way to find degree 1 primes in a number field.
ncalexan-827: ?
wstein-1606: theoretically or in sage right now?
ncalexan-827: wstein-1606: right now, but also in theory.
wstein-1606: for all but finitely many primes you factor the defining poly of the field and see if it splits completely.
dmharvey left the chat room.
wstein-1606: you can do that more quickly by taking the gcd mod p with x^p - x
ncalexan-827: Right.
wstein-1606: or something like that.
wstein-1606: I bet you get the idea.
ncalexan-827: Doesn't this only work if your ring of integers is generated by a single element?
wstein-1606: nick -- that's why I said "all but finitely many".
wstein-1606: For all but a couple primes the ring of integers is monogenic.
wstein-1606: just avoid primes dividing the discriminant.
wstein-1606: for those do the usual factorization algorithm.
ncalexan-827: wstein-1606: sure.  It sounds like a degree_one_primes() generator would be handy for multi modular algorithms, then.
wstein-1606: yep!
wstein-1606: But beware -- it is very very very hard to find any degree one primes if the field isn't cyclotomic.
wstein-1606: For a galois S_n extension of degree n, only 1/n! of the primes split completely (by cebo.)
ncalexan-827: Hmm.  So it's not even worth it?
wstein-1606: Well it's very worth it in the cyclotomic case.
wstein-1606: more generally, in the abelian case.
wstein-1606: E.g., for quadratic fields.
wstein-1606: and even 1/n! isn't bad if n is small, which it often is.

CC: @ncalexan

Component: number theory

Keywords: degree one prime number field norm

Issue created by migration from https://trac.sagemath.org/ticket/2835

[93749b3a-c0a4-47a7-b178-004ba08b0b97]

comment:1

The attached patch implements a simple iterator for finding primes of number fields of small prime norm. It is very possible this won't work for large fields; I would appreciate feedback. It certainly works well for my examples, which are of degree less than or equal to 40.

[JohnCremona]

comment:2

Attachment: 2835-ncalexan-primes-of-degree-one-1.patch.gz

It's an interesting idea to do it this way. When I had to do something similar I just looped over primes p and computed x^p mod (p,f(x)). But I wanted p for which f split completely, which is a lot stronger than what you need.

As this is a function which will not be used all that much, I suggest putting it in and seeing how it fares in actual use.

[aghitza]

comment:4

Nick,

I agree with John on this. I looked at your patch and it looks good to me, but I've only played around with it a little bit. The real test will come when somebody actually uses it in a nontrivial way -- but that is not likely to happen if it isn't in Sage. It is extra functionality so it won't break anything that's already there.

I would prefer it if you changed the last line of next() to

return self._field.fractional_ideal([p, x - n])

for the reasons that are stated in http://groups.google.com/group/sage-devel/t/b01d58d8c3565c2 (but this is something that we can also change later on).

[85eec1a4-3d04-4b4d-b711-d4db03337c41]

comment:5

Merged in Sage 3.0.alpha3