Primality and Factoring in Number Fields

Both PRIMALITY – deciding if an integer n is a prime and FACTORING – representing an integer as a product of primes, are algorithmic questions of great interest. I am curious to know what is known about these questions over general number fields. A major difference there is that there is know unique factorization to primes. Let me repeat here a question that I asked over TCS-stackexchange.

What is known about the computational complexity of factoring integers in general number fields? More specifically:

0. Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?

1. Is it known that primality over number fields is in P or BPP?

2. What are the best known algorithms for factoring over number fields? (Do the \exp \sqrt n and the (apparently) \exp n^{1/3} algorithms extend from \mathbb{Z}?) Here, factoring refers to finding some representation of a number (represented by n bits) as a product of primes.

3. What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?

4. Over \mathbb{Z} it is known that deciding if a given number has a factor in an interval [a,b] is NP-hard. Over the ring of integers in number fields, can it be the case that finding if there is a prime factor whose norm is in a certain interval is already NP-hard?

5. Is factoring in number fields in BQP?

Motivation and updates: The question (especially part 5) was motivated by this blog post over GLL (see this remark), and also by an earlier TCSexchange question. Lior Silverman presented in the comment section  below  a thorough answer.

About these ads
This entry was posted in Algebra and Number Theory and tagged , . Bookmark the permalink.

9 Responses to Primality and Factoring in Number Fields

  1. Guest says:

    Sorry, did you mean that over Z it is known that deciding if a given number has a factor in an interval [a,b] is “factoing-hard”?

  2. My first reaction is that there’s a natural polynomial-time reduction to the case of factorization in $\Z$, but I’ll have to check the details. Here’s the idea: factor the norm $N^F_{\Q}(x)$ and then factor each rational prime in the factorization of the norm into primes of $F$.

    For now I’m assuming that the field is constant. If the “input” is a description of both the field and the element then more verification would be required.

    • Gil Kalai says:

      Dear Lior, Very interesting. Assuming that the field is constant is fine. I am eager to know if it works and what it gives.

      • Yes, I believe that you are OK for a fixed number field. Here are my thoughts (for more details ask me to email you a PDF). I could have missed something stupid of course — you should really ask an expert in computational number theory.

        0. This is standard. Let your field be K=\mathbb{Q}(\alpha) where \alpha is an algebraic integer with minimal polynomial f (this is a monic polynomial with rational integer coefficients). The degree n of f is also the degree [K:\mathbb{Q}]. Now \{\alpha^j \}_{j=0}^{n-1} is a \mathbb{Q}-basis for K, and algebraic integers have coordinates in this basis whose denominators are a-priori bounded (they must divide the discriminant of \alpha). So every integer can be described by n rational integers. In particular (n fixed) the length of the description is equivalent to the length of the largest coordinate. Equivalently, you can fix an integral basis (that is, a basis for the field whose \mathbb{Z}-span is exactly the ring of integers. Moving between the two representations requires a bounded number of multiplications by fixed integers and additions, so can be done in polynomial time and only changes the representation length by an additive constant.

        1. I’m fairly certain that AKS will work over number fields. However, this one is not a formal consequence of results for the rationals — so I’d like to reserve it for a summer project for a student — I’ll post here if this project doesn’t materialize.

        2. I have no idea about this, but I will describe a reduction to the problem in the rational integers. It would be surprising if you can do any better.

        3a. Over a number field we need to distinguish between “irreducibles” (algebraic integers which cannot be factored non-trivially as a product of algebraic integers) and “primes” (prime ideals of the ring of integers). The “prime” factorization is much more natural and is unique. I will describe below how to find the prime factorization. From this you can understand all factorizations into irreducibles as a purely combinatorial problem, and I will explain how to find one such factorization. It should be exponential in the worst case to find all factorizations, or even to count them.

        3b. Factoring into primes. You are given an integer x\in K, expressed using n rational integers, each of length at most N.

        (0) A finite precomutation factors every rational prime dividing the discriminant of \alpha into primes of K.

        (1) You can calculate the absolute norm y = N^K_\mathbb{Q} x — this is the determinant of the matrix of multiplication by x, which can be found by Gaussian elimination. Note that the number of bits of y is linear in that of x.

        (2) Factor y using the best known factorization algorithm. Get O(N) primes each of length O(N).

        (3) For each rational prime p dividing y, find the factorization of (p) in the ring of integers. Generically (if p does not divide the discriminant of \alpha) this can be done by factoring the polynomial f above mod p, so takes polynomial time. For the finitely many bad primes see the precomputation.

        We thus have a factorization of the norm into primes of K.

        (4) For each prime P of K obtained in step (3), find the number of times P divides (x) (the “P-adic valuation of x”). This can be done in polynomial time (at worst, the exponent is O(N) and we can try P^e for every e — note that the multiplications here do not cause the coefficients of P^e to grow beyond polynomially).

        This gives the desired factorization.

        3c. Factorization into irreducibles, given the factorization into primes.

        Here’s a purely combinatorial problem:

        Let G be a finite Abelian group. Call a non-empty multiset of elements of G “irreducible” if its product is the trivial element but no non-empty proper subset has this property. Now given a multiset whose product is the identity, your problems are:

        (i) Write the multiset as a union of irreducible subsets.
        (ii) Count all such partitions.
        (iii) Exhibit all of them.

        [For us the group is the classgroup of the field, and the elements are the primes in the factorization of x; in particular the group is fixed].

        To solve (i) let h be the order of the group, Note that by the pigeon-hole principle every multiset of cardinality at least h contains a subset which multiplies to the identity, and hence an irreducible subset. But a multiset of bounded cardinality has boundedly many subsets. It follows that we can find a decomposition into irreducibles by ordering the factors, checking all subsets of the set consisting of the first h factors, “peeling off” an irreducible factor, and continuing.

        I think you can solve (ii),(iii) in the setting of the finite Abelian group since it only has finitely many elements, and the multisets simply tell you how many of each kind there is. Possibly generating functions will be enough. The twist for the field is that different prime ideals correspond to the same ideal class so after determining everything in the classgroup you still have to go back and choose how to allocate the primes in a particular class into the factorizations. This is probably doable, but I’m not sure if it can be done in polynomial time.

        (iii) In any case there will be exponentially many factorizations, so this is exponential time.

        4. I choose to interpret your problem as asking for prime factors (ie prime ideals) not irreducible factors. I don’t know quite how to solve this, but note that by asking whether a rational integer has a prime ideal factor of norm in some range and considering that the size of the rational prime lying about the prime ideal is basically determined by the norm of the ideal, you gain quite a bit of information.

        5. I think so, by reduction to the rational case.

      • Gil Kalai says:

        Dear Lior, great! Many thanks. Regarding primality it will be great to know if AKS extends to determine prime ideals. What about the earlier algorithms by Miller, Rabin, Solovay-Strassen, Killian-Goldwasser… do they extend? In general, my questions were about irreducible integers but the question about prime ideals are also very interesting and as you explained quite related.

        We can ask if for class number greater than 1 the question if an algebraic integer is irreducible is FACTORING-hard.

        Your 3c description may suggest that factoring to irreducible integers may be harder than factoring and perhaps even more so is finding an irreducible factor in a given interval. But this is not clear.

  3. My 3c shows how to efficiently find one factorization into irreducibles, given the prime factorization. So finding one irreducible factorization is no harder than factoring. Similarly, given the prime factorization it is trivial to tell if the integer is irreducible: if there are at least h_K prime factors then no, and otherwise just try all sub-factorizations to see if they multiply to a principal ideal.

    3c also gives an exponential-time algorithm for enumerating all factorizations into irreducibles. Whether you can count the factorizations without enumerating is less obvious.

  4. I just realized that there’s no need to generalize AKS to number fields — the reduction above also works for (deterministic) primality testing of ideals. The case of irreducibles is still open.

    We work in the field K=\mathbb{Q}(\alpha) where the minimal polynomial f of the algebraic integer \alpha is known. We do the same precomputation, computing all ideals of K that lie above rational primes dividing the discriminant of \alpha.

    Now given a prime ideal P consider the ideal P\cap\mathbb{Z}. It is possible to efficiently compute a generator p for this ideal, and it will have size polynomial in the size of generators of P. Apply AKS to decide if p is prime. If it is composite we know P is not prime. Otherwise, compute the prime ideals of K lying above p as described above and check if P is one of them (equality of ideals is easy to check).

    Remark 1: this reduction depends on the algorithm in \mathbb{Z} being deterministic. I think the probabilistic algorithms would need to be generalized, and probably give a more efficient solution.

    Remark 2: I have no idea how to approach “irreducibility testing”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s