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 
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 ![[a,b]](https://s0.wp.com/latex.php?latex=%5Ba%2Cb%5D&bg=ffffff&fg=333333&s=0&c=20201002)
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.
Combinatorics and more 
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”?
Dear guest, No, I meant NP-hard. Note that it is about “factor” not “prime factor.”
I see, thanks for the answer and sorry for the dumb question (I thought that was a typo).
GK: your question, guest, was good, not dumb at all.
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.
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
where 
is an algebraic integer with minimal polynomial 
(this is a monic polynomial with rational integer coefficients). The degree 
of 
is also the degree ![[K:\mathbb{Q}]](https://s0.wp.com/latex.php?latex=%5BK%3A%5Cmathbb%7BQ%7D%5D&bg=ffffff&fg=333333&s=0&c=20201002)
. Now 
is a 
-basis for 
, and algebraic integers have coordinates in this basis whose denominators are a-priori bounded (they must divide the discriminant of 
). So every integer can be described by 
rational integers. In particular (
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 
-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
, expressed using 
rational integers, each of length at most 
.
(0) A finite precomutation factors every rational prime dividing the discriminant of
into primes of 
.
(1) You can calculate the absolute norm
— 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 
is linear in that of 
.
(2) Factor
using the best known factorization algorithm. Get O(N) primes each of length O(N).
(3) For each rational prime
dividing 
, find the factorization of 
in the ring of integers. Generically (if 
does not divide the discriminant of 
) this can be done by factoring the polynomial 
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
.
(4) For each prime
of 
obtained in step (3), find the number of times 
divides 
(the “P-adic valuation of x”). This can be done in polynomial time (at worst, the exponent is O(N) and we can try 
for every e — note that the multiplications here do not cause the coefficients of 
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
be a finite Abelian group. Call a non-empty multiset of elements of 
“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
be the order of the group, Note that by the pigeon-hole principle every multiset of cardinality at least 
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.
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.
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
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.
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
where the minimal polynomial 
of the algebraic integer 
is known. We do the same precomputation, computing all ideals of 
that lie above rational primes dividing the discriminant of 
.
Now given a prime ideal
consider the ideal 
. It is possible to efficiently compute a generator 
for this ideal, and it will have size polynomial in the size of generators of 
. Apply AKS to decide if 
is prime. If it is composite we know 
is not prime. Otherwise, compute the prime ideals of 
lying above 
as described above and check if 
is one of them (equality of ideals is easy to check).
Remark 1: this reduction depends on the algorithm in
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”.