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


Easy and Fast Key-dependent Affine Transformation of Square S-Boxes
Abstract. Substitution boxes (S-boxes) are generally the only non-linear part of a block cipher. Using key-dependent S-boxes rather than static ones might increase the security of a block cipher but it would take too much time to build a good key-dependent S-box from scratch just before ciphering or deciphering. What we can do is to transform an existing S-box, assuming
1) the relevant cryptographic properties of the S-box are preserved;
2) the execution of the transformation is sufficiently fast.