`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().