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

Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?
Is it known that primality over number fields is in P or BPP?
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.
What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?
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?
Is factoring in number fields in BQP?

Remarks, motivations and updates.
Of course the fact that factorization is not unique over number fields is crucial here. The question (especially part 5) was motivated by this blog post over GLL (see this remark), and also by this earlier TCSexchange question. I presented it also over my blog where Lior Silverman presented a thorough answer.
The following answer was originally posted as a comment on Gil's blog

(1) Let $K=\mathbb{Q}(\alpha)$ be a number field, where we assume $\alpha$ has a monic minimal polynomial $f\in\mathbb{Z}[x]$.  One can then represent elements of the ring of integers $\mathcal{O}_K$ as polynomials in $\alpha$ or in terms of an integral basis -- the two are equivalent.

Now fixing $K$ as in (1) there's a polynomial-time reduction from the problem over $K$ to the problem in $\mathbb{Q}$.  To verify that the computations (e.g. intersecting an ideal with $\mathbb{Z}$ or factoring a polynomial mod $p$) can be done in polynomial time see Cohen's book referred to in the previous answer.

As a precomputation for each rational prime $p$ dividing the discriminant of $\alpha$ (that is the discriminant of $f$) find all primes of $\mathcal{O}_K$ lying above $p$.

(2) For primality testing, given an ideal $\mathfrak{a}\triangleleft\mathcal{O}_K$ let $p\in\mathbb{Z}$ be such that $\mathfrak{a}\cap\mathbb{Z} = p\mathbb{Z}$ (this can be computed in polynomial time and the number of bits of $p$ is polynomial in the input).  Check in polynomial time whether $p$ is prime. If not then $\mathfrak{a}$ is not prime.  If yes then find the primes of $\mathcal{O}_K$ lying above $p$ either from the precomputation or by factoring $f$ mod $p$.  In any case if $\mathfrak{a}$ is prime it must be one of those primes.

(3a),(6a) For factoring into primes, given an ideal $\mathfrak{a}\triangleleft\mathcal{O}_K$ find its norm $y = N^K_\mathbb{Q}(\mathfrak{a}) = [\mathcal{O}_K:\mathfrak{a}]$. Again this can be found in polynomial time and consequently is not too large. Factor $y$ in $\mathbb{Z}$ (either classically or using Shor's algorithm, depending on the reduction you want).  This gives a list of rational primes dividing $y$, and hence as in 2 we can find the list of primes of $\mathcal{O}_K$ dividing $y$.  Since $\mathfrak{a} | y\mathcal{O}_K$ this gives the list of primes dividing $\mathfrak{a}$.  Finally it is easy to determine the exponent to which a prime divides a given ideal.

(3b),(6b) But Gil wants factorization into irreducibles, not into primes. It turns out that given the prime factorization of $x\mathcal{O}_K$ it is possible to efficiently construct one factorization of $x$ into irreducible elements of $\mathcal{O}_K$.  For this let $h_K$ be the class number, and note that it is possible to efficiently compute the ideal class of a given ideal. Now to find an irreducible divisor of $x$ select $h_K$ prime ideals (possibly with repetition) from the factorization of $x$.  By the pigeon-hole principle some subset of those multiplies to the identity in the class group; find a minimal such subset.  Its product is then a principal ideal generated by an irreducible element.  Divide $x$ by this element, remove the relevant ideals from the factorization and repeat.  If the factorization has less than $h_K$ elements then just take a minimal subset of all the factors.

(4) I think it's possible to count the factorizations into irreducibles, but this is a bit of extra combinatorics -- please give me time to work it out.  One the other hand, determining all of them is not interesting in the context of sub-exponential factorization algorithms since there are in general exponentially many such factorizations.

(5) I have no idea.