Abstract. Primality proving... Cryptography... As soon as we want to build an elliptic curve with a known order over a Z/p field using the so-called complex multiplication, we have to find a root of a class polynomial. Depending on the degree of this polynomial (and on the size of the prime p), this operation might be very lengthy. More concretely, suppose we have to find a root of H[-12932920](x) (the degree of this polynomial is 832). Suppose now we can compute a factor of degree 13 more quickly than we can compute the whole polynomial H[-D](x) itself. Of course, it would make the task easier...