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

Valid XHTML 1.0 Strict