You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
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.
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.
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
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:
CC: @ncalexan
Component: number theory
Keywords: degree one prime number field norm
Issue created by migration from https://trac.sagemath.org/ticket/2835
The text was updated successfully, but these errors were encountered: