Iterator for finding several primes of absolute degree one of a number field of small prime norm.
Algorithm:
Let denote the product of some set of prime numbers. (In practice, we
use the product of the first 10000 primes, because Pari computes this many by
default.)
Let be a number field and let
be a polynomial defining
over the
rational field. Let
be a root of
in
.
We know that , where
denotes the discriminant (see, for example, Proposition 4.4.4, p165 of
[C]). Therefore, after discarding primes dividing
(this
includes all ramified primes), any integer
such that
yields a prime
such that
has a root modulo
. By the
condition on discriminants, this root is a single root. As is well known (see,
for example Theorem 4.8.13, p199 of [C]), the ideal generated by
is prime and of degree one.
[C] | (1, 2) H. Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1993. |
Warning
It is possible that there are no primes of of absolute degree one of
small prime norm, and it is possible that this algorithm will not find
any primes of small norm.
To do:
There are situations when this will fail. There are questions of finding primes of relative degree one. There are questions of finding primes of exact degree larger than one. In short, if you can contribute, please do!
EXAMPLES:
sage: x = ZZ['x'].gen()
sage: F.<a> = NumberField(x^2 - 2, 'a')
sage: Ps = F.primes_of_degree_one_list(3)
sage: Ps # random
[Fractional ideal (2*a + 1), Fractional ideal (-3*a + 1), Fractional ideal (-a + 5)]
sage: [ P.norm() for P in Ps ] # random
[7, 17, 23]
sage: all(ZZ(P.norm()).is_prime() for P in Ps)
True
sage: all(P.residue_class_degree() == 1 for P in Ps)
True
The next two examples are for relative number fields.:
sage: L.<b> = F.extension(x^3 - a, 'b')
sage: Ps = L.primes_of_degree_one_list(3)
sage: Ps # random
[Fractional ideal (17, b - 5), Fractional ideal (23, b - 4), Fractional ideal (31, b - 2)]
sage: [ P.absolute_norm() for P in Ps ] # random
[17, 23, 31]
sage: all(ZZ(P.absolute_norm()).is_prime() for P in Ps)
True
sage: all(P.residue_class_degree() == 1 for P in Ps)
True
sage: M.<c> = NumberField(x^2 - x*b^2 + b, 'c')
sage: Ps = M.primes_of_degree_one_list(3)
sage: Ps # random
[Fractional ideal (17, c - 2), Fractional ideal (c - 1), Fractional ideal (41, c + 15)]
sage: [ P.absolute_norm() for P in Ps ] # random
[17, 31, 41]
sage: all(ZZ(P.absolute_norm()).is_prime() for P in Ps)
True
sage: all(P.residue_class_degree() == 1 for P in Ps)
True
AUTHORS:
Iterator that finds primes of a number field of absolute degree one and bounded small prime norm.
INPUT:
AUTHOR:
Return a prime of absolute degree one of small prime norm.
Raises StopIteration if such a prime cannot be easily found.
EXAMPLES:
sage: x = QQ['x'].gen()
sage: K.<a> = NumberField(x^2 - 3)
sage: it = K.primes_of_degree_one_iter()
sage: [ it.next() for i in range(3) ] # random
[Fractional ideal (2*a + 1), Fractional ideal (-a + 4), Fractional ideal (3*a + 2)]
We test that #6396 is fixed. Note that the doctest is flagged as random since the string representation of ideals is somewhat unpredictable:
sage: N.<a,b> = NumberField([x^2 + 1, x^2 - 5])
sage: ids = N.primes_of_degree_one_list(10); ids # random
[Fractional ideal ((-1/2*b + 1/2)*a + 2),
Fractional ideal (-b*a + 1/2*b + 1/2),
Fractional ideal ((1/2*b + 3/2)*a - b),
Fractional ideal ((-1/2*b - 3/2)*a + b - 1),
Fractional ideal (-b*a - b + 1),
Fractional ideal (3*a + 1/2*b - 1/2),
Fractional ideal ((-3/2*b + 1/2)*a + 1/2*b - 1/2),
Fractional ideal ((-1/2*b - 5/2)*a - b + 1),
Fractional ideal (2*a - 3/2*b - 1/2),
Fractional ideal (3*a + 1/2*b + 5/2)]
sage: [x.absolute_norm() for x in ids]
[29, 41, 61, 89, 101, 109, 149, 181, 229, 241]
sage: ids[9] == N.ideal(3*a + 1/2*b + 5/2)
True