`Evaluator::exponentiate_inplace()` has suboptimal performance

[FeanorTheElf]

First of all thank you for this amazing library!

When trying to raise a ciphertext to the 128-th power with SEAL, I have noticed that the corresponding function performs a linear amount of multiplications (w.r.t. the exponent), instead of a logarithmic amount, as possible with square-and-multiply approach.

More concretely, the code for exponentiate_inplace() is

void Evaluator::exponentiate_inplace(
        Ciphertext &encrypted, uint64_t exponent, const RelinKeys &relin_keys, MemoryPoolHandle pool) const
    {
        // Verify parameters.
        ...

        // Fast case
        if (exponent == 1)
        {
            return;
        }

        // Create a vector of copies of encrypted
        vector<Ciphertext> exp_vector(static_cast<size_t>(exponent), encrypted);
        multiply_many(exp_vector, relin_keys, encrypted, move(pool));
    }

and thus uses (in my case) 127 multiplications. Since multiply_many() performs a tree-reduction, the noisy growth is optimal, but the runtime is not. As opposed to that, something like

void fast_exponentiate(const Ciphertext& ciphertext, size_t exponent, const Evaluator& evaluator, const RelinKeys& rk, Ciphertext& result) {
    // we let result uninitialized until we have to, this is represented by result_is_one == true
    bool result_is_one = true;

    // a classical square-and-multiply algorithm
    for (int64_t i = std::numeric_limits<size_t>::digits - 1; i >= 0; --i) {
        if (!result_is_one) {
            evaluator.square_inplace(result);
            evaluator.relinearize_inplace(result, rk);
        }
        if (((exponent >> i) & 1) == 1) {
            // multiplying ciphertext to the result here will cause it to be
            // squared exactly i times
            if (!result_is_one) {
                evaluator.multiply_inplace(result, ciphertext);
                evaluator.relinearize_inplace(result, rk);
            }
            else {
                result = ciphertext;
                result_is_one = false;
            }
        }
    }
}

would only execute 7 multiplications.

EDIT There was a small mistake in my implementation of fast_exponentiate().