0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.