Binary Exponentiation by Factoring¶
Consider a problem of computing
The algorithm below allows to solve this problem with
Due to the structure of the multiplicative group modulo
where
The core idea of the algorithm is to simplify the computation of
In this article, we will cover the implementation for
mbin_log_32(r, x)
be a function that computesmbin_exp_32(r, x)
be a function that computesmbin_power_odd_32(a, x, y)
be a function that computes
Then mbin_power_odd_32
is implemented as follows:
uint32_t mbin_power_odd_32(uint32_t rem, uint32_t base, uint32_t exp) {
if (base & 2) {
/* divider is considered negative */
base = -base;
/* check if result should be negative */
if (exp & 1) {
rem = -rem;
}
}
return (mbin_exp_32(rem, mbin_log_32(0, base) * exp));
}
Computing 4L(x) from x¶
Let
where
So, if we precompute
For 32-bit integers, we can use the following table:
const uint32_t mbin_log_32_table[32] = {
0x00000000, 0x00000000, 0xd3cfd984, 0x9ee62e18,
0xe83d9070, 0xb59e81e0, 0xa17407c0, 0xce601f80,
0xf4807f00, 0xe701fe00, 0xbe07fc00, 0xfc1ff800,
0xf87ff000, 0xf1ffe000, 0xe7ffc000, 0xdfff8000,
0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
};
On practice, a slightly different approach is used than described above. Rather than finding the factorization for
To do this, we iterate over x = x + (x << n)
. This won't change bits lower than
With all this in mind, the function mbin_log_32(r, x)
is implemented as follows:
uint32_t mbin_log_32(uint32_t r, uint32_t x) {
uint8_t n;
for (n = 2; n < 32; n++) {
if (x & (1 << n)) {
x = x + (x << n);
r -= mbin_log_32_table[n];
}
}
return r;
}
Note that
Computing x from 4L(x)¶
Note that for
from which (by repeated squaring) we can deduce that
Applying this result to
This, in turn, means that
thus
Thus, mbin_exp_32
is implemented as follows:
uint32_t mbin_exp_32(uint32_t r, uint32_t x) {
uint8_t n;
for (n = 2; n < 32; n++) {
if (x & (1 << n)) {
r = r + (r << n);
x -= mbin_log_32_table[n];
}
}
return r;
}
Further optimizations¶
It is possible to halve the number of iterations if you note that
which allows to deduce that
uint32_t mbin_log_32(uint32_t r, uint32_t x) {
uint8_t n;
for (n = 2; n != 16; n++) {
if (x & (1 << n)) {
x = x + (x << n);
r -= mbin_log_32_table[n];
}
}
r -= (x & 0xFFFF0000);
return r;
}
uint32_t mbin_exp_32(uint32_t r, uint32_t x) {
uint8_t n;
for (n = 2; n != 16; n++) {
if (x & (1 << n)) {
r = r + (r << n);
x -= mbin_log_32_table[n];
}
}
r *= 1 - (x & 0xFFFF0000);
return r;
}
Computing logarithm table¶
To compute log-table, one could modify the Pohlig–Hellman algorithm for the case when modulo is a power of
Our main task here is to compute
Squaring both parts
Note that the order of
Multiplying both parts with
Now, squaring both sides