Complex multiplication in cryptography

Algorithms going under the name `complex multiplication' typically have a run time that is exponential in the size of the input data. We will show that nevertheless such algorithms may sometimes be profitably used in cryptographic settings.