I'm trying to implement the algorithm for factoring polynomials over number fields on page 145 of Henri Cohen's A Course on Computational Algebraic Number Theory, but I'm not sure how the application of the sub-resultant GCD algorithm in the first step is supposed to work.

The sub-resultant algorithm is presented as being for polynomials over UFD's. I'm aware that fields are UFD's, but given that the algorithm calls for taking GCD's between coefficients of the polynomials, it seems like it only makes sense for UFD's that aren't also fields.

Isn't every nonzero element of a field a GCD of every other, and wouldn't that render all such GCD calculations in the algorithm pointless?

My first thought is that applying the sub-resultant algorithm to polynomials over number fields is to be analogous to applying it to polynomials over the rationals, though before I pursue that too far I want to make sure I understand that case correctly as well. To apply it to polynomials over the rationals, you multiply each by the lcm of the denominators of its coefficients in order to get an integer polynomial, and apply it to those instead.

If that's right, is the equivalent for polynomials over number fields multiplying each polynomial by an element of the field such that the coefficients all end up in the field's ring of integers?

I'm not sure how to do that. For what it's worth, I have the minimal polynomial of a primitive element of the number field on hand, and am representing elements of the field as rational polynomials in terms of the primitive element. I understand that the reason to use the sub-resultant algorithm rather than the basic Euclidean algorithm for rational polynomials is that being able to restrict the coefficients to the integers saves the work of having to reduce fractions every time one operates on them. In the number field case, on the other hand, if algebraic integers are more efficient to operate on than arbitrary field elements, I'm not clear on the concrete reason why, unless it happens that each coefficient can be represented using an integer polynomial rather than a rational one.

Edit: Multiplying the polynomials by field elements that bring the coefficients into the field's ring of integers can't be the intention, because the sub-resultant algorithm is for polynomials with coefficients over a UFD, while the ring of integers of a number field is not always a UFD.

  • $\begingroup$ As you correctly noticed, gcds in a field are trivial ($0$ when all the arguments are $0$, and $1$ otherwise), but this only makes Algorithm 3.3.1 a bit simpler (of course, you can just as well use the regular Euclidean algorithm instead). You can probably take gcds "strategically" to minimize denominators, but I don't see a real method to this. $\endgroup$ – darij grinberg Jul 17 '19 at 11:36
  • $\begingroup$ @darijgrinberg Do you know what the advantage to using algorithm 3.3.1 over using algorithm 3.2.1 is? I would think that unless the former allows for replacing operations on field elements with more efficient operations on UFD elements, there's no reason to prefer it over the latter. $\endgroup$ – Alex Kindel Jul 17 '19 at 11:47
  • $\begingroup$ I don't know anything about efficiency, sorry. My impression is that Cohen cares about efficiency in §3.3, but not in §3.6.2. $\endgroup$ – darij grinberg Jul 17 '19 at 12:31

In a field $K$, for all $a,b\in K$, with $a,b$ not both zero, we have $\gcd(a,b)=1$. So for $R=K$, finding a $gcd$ in $R$ is easy.

Other than that, apply the sub-resultant algorithm as given, to get $\gcd(A,A')$.

Altermatively, since $A,A'\in K[x]$, to get $\gcd(A,A')$, you could use the ordinary Euclidean algorithm for univariate polynomials over a field.

| cite | improve this answer | |
  • $\begingroup$ I assume that the reason it suggests the sub-resultant algorithm is to be more efficient than using the ordinary Euclidean algorithm would be. I guess what I don't know is how to use it over a number field in such a way that an efficiency gain actually manifests. Taking $gcd(a, b) = 1$ when $K$ is the rationals would work out to be no better than the Euclidean algorithm, so that can't be the idea. $\endgroup$ – Alex Kindel Jul 17 '19 at 9:45
  • $\begingroup$ I think the main idea of the sub-resultant algorithm is that it works over $R[x]$, when $R$ is a UFD, not necessarily a field. $\endgroup$ – quasi Jul 17 '19 at 9:50
  • $\begingroup$ Why would the book recommend it in the context of an algorithm that is specifically for fields? Page 114 discusses how the ordinary Euclidean algorithm suffers from coefficient explosion for polynomials with rational coefficients, and works up to the sub-resultant algorithm a few pages later as a way of addressing that problem. $\endgroup$ – Alex Kindel Jul 17 '19 at 10:04
  • $\begingroup$ I think it may be a non-issue since computing $\gcd(A,A')$ only applies to step $1$, which is done only once. $\endgroup$ – quasi Jul 17 '19 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.