Module small_primes_of_degree_one

Iterator for finding several primes of absolute degree one of a number
field of *small* prime norm.

ALGORITHM:
    Let $P$ denote the product of the some set of prime numbers.  (In
    practice, we use the product of the first 10000 primes, because
    Pari computes this many by default.)

    Let $K$ be a number field and let $f(x)$ be a polynomial defining
    $K$ over the rational field.  Let $\alpha$ be a root of $f$ in
    $K$.

    We know that $ [ O_K : Z[\alpha] ]^2 = | \Delta(f(x)) /
    \Delta(O_K) |$, where $\Delta$ denotes the discriminant (see, for
    example, Proposition 4.4.4, p165 of [C]).  Therefore, after
    discarding primes dividing $\Delta(f(x))$ (this includes all
    ramified primes), any integer $n$ such that $\gcd(f(n), P) > 0$
    yields a prime $p | P$ such that $f(x)$ has a root modulo $p$.  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 $(p, \alpha - n)$ is prime and of degree one.

    [C] H. Cohen. A Course in Computational Algebraic Number
    Theory. Springer-Verlag, 1993.

WARNING:
    It is possible that there are no primes of $K$ of absolute degree
    one of small prime norm, and it possible that this algorithm will
    not find any primes of small norm.

TODO:
    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

    In the next two examples, relative residue class degrees are not yet
    implemented, but we can check that the absolute norms are in fact prime.

    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.norm().norm() for P in Ps ] # random
    [17, 23, 31]
    sage: all(ZZ(P.norm().norm()).is_prime() for P in Ps)
    True
    sage: all(P.residue_class_degree() == 1 for P in Ps)
    Traceback (most recent call last):
    ...
    NotImplementedError...

    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.norm().norm().norm() for P in Ps ] # random
    [17, 31, 41]
    sage: all(ZZ(P.norm().norm().norm()).is_prime() for P in Ps)
    True
    sage: all(P.residue_class_degree() == 1 for P in Ps)
    Traceback (most recent call last):
    ...
    NotImplementedError...

AUTHOR:
    -- Nick Alexander