# Getting bit length of exponentiation result before computation

I'm working in a context where it is cheaper to calculate pow(a,b) via modular exponentiation (modexp(a,b,m)) than to do exponentiation directly. For this I need the minimum modulus value such that the function returns only the exponentiation part of the function call.

Is there an efficient algorithm that exists to calculate the bit-length / highest bit set of a^b, where we just know these values (result not yet calculated)? or if not, an algorithm that approximates it as close as possible? In this case, the only requirement is that the approximation be >= the real bit length.

• If you are content with an approximation, hint: $\log_2(a^b)=b\log_2 a$
– fgrieu
Commented Oct 26, 2022 at 11:38
• thanks. the only requirement is that the approximation be >= the real bit length. Commented Oct 26, 2022 at 11:40

If $$a\in\mathbb N^*$$ has $$\ell$$ bits and $$b\in\mathbb N^*$$, then $$a^b$$ has at most $$b\,\ell$$ bits.
More precisely, $$a^b$$ has exactly $$\lfloor b\log_2(a)\rfloor+1$$ bits.
All this follows from $$\log_2(a^b)=b\log_2 a$$.