Notes and algorithms regarding ECPP
The following notes are aimed at computer scientists, i.e., their main goal is not
to explain why such or such things work but to show how they can be implemented.
Factoring Class Polynomials over the Genus Field

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 socalled 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...



