Find factors of a Mersenne number

On RosettaCode I found this C++ version of modPow (compute 2ᵖ mod n) to find the factors of a Mersenne number.

#include <iostream>
#include <cstdint>

typedef uint64_t integer;

integer bit_count(integer n) {
integer count = 0;
for (; n > 0; count++)
n >>= 1;
return count;
}

integer mod_pow(integer p, integer n) {
integer square = 1;
for (integer bits = bit_count(p); bits > 0; square %= n) {
square *= square;
if (p & (1 << --bits))
square <<= 1;
}
return square;
}


Do you think this modified version could be faster?

const int b=5;

integer mod_2_pow(integer p, integer d) {
std::vector<int> Residue_p;
while (p >= 1<<b) {
Residue_p.push_back((int)(p&((1<<b) -1)));
p >>= b;
}
int nR=Residue_p.size();
integer mod = 1<<p;
if(nR>0) {
for (int i=nR-1; i >=0; i--) {
for (int j=0; j <b; j++) {
mod *= mod;
mod %= d;
}
mod <<= Residue_p[i];
mod %= d;
}
}
else
mod %= d;
return mod;
}


Explanation

I think the previous code considers b=1 instead

fix b=5 then 2ᵇ=32

P=P%32 +P/32 *32 = P%32 +b1 *32

b1=b1%32 +b1/32 *32 = P%32 +b2 *32 then b2=b1/32

.....

bm =bm%32 +bm/32 *32

continue until bm/32 <32

the remainder must be stored in a vector [P%32, b1%32, ... , bm%32]

then we start from

mod=2^(bm/32)

the product is repeated for b=5 times

mod=(mod*mod)%D

then it is calculated

mod=(mod* 2^(bm%32) )%D

the whole is repeated for all the remainders in the vector.

• Please provide an explanation of what your code is doing. Commented Sep 15, 2022 at 12:59

• I don't think you understand how it works, but it is the same as the previous code the number of iterations are almost equal, it is easily adaptable for larger numbers by increasing b, what is avoided is the use of if. I wanted to understand if this makes the faster the code. Commented Sep 16, 2022 at 6:14