Getting bit length of exponentiation result before computation

riordant

10/26/23, 11:35 AM

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.

1 + 2

bitslicing

fgrieu

10/26/23, 11:38 AM

If you are content with an approximation, hint: $\log_2(a^b)=b\log_2 a$

riordant

10/26/23, 11:40 AM

thanks. the only requirement is that the approximation be >= the real bit length.

Score:1

Crypto

fgrieu

10/26/23, 11:41 AM

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

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Getting bit length of exponentiation result before computation

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.