Fast ideal cubing in imaginary quadratic number and function fields
Laurent Imbert, Michael J. Jacobson, Arthur Schmidt · Advances in Mathematics of Communications · 2010
We present algorithms for computing the cube of an ideal in animaginary quadratic number field or function field. In addition to a version that computes a non-reduced output, we present a variation based on Shanks' NUCOMP algorithm that computes a reduced output and keeps the sizes of the intermediate operands small. Extensive numerical results are included demonstrating that in many cases our formulas, when combined with double base chains using binary and ternary exponents, lead to faster exponentiation.