compute power modulo n

powmod.cpp

#include <iostream>
#include <CppUTest/CommandLineTestRunner.h>
#include <CppUTest/TestHarness.h>
#include <numeric>

using namespace std;

// (x^p)%n
unsigned powMod(unsigned x, unsigned p, unsigned n)
{
    const int numBits = sizeof(p) * 8;
    x %= n;
    unsigned res = 1;
    for(int i=numBits-1; i >= 0; i--)
    {
        bool one = (1U << (unsigned)i) & p;
        res *= res; res %= n;
        res *= one ? x : 1; res %= n;
    }
    return res;
}

u_int64_t powModLong(u_int64_t x, u_int64_t p, u_int64_t n)
{
    const int numBits = sizeof(p) * 8;
    x %= n;
    u_int64_t res = 1;
    for(int i=numBits-1; i >= 0; i--)
    {
        bool one = (1UL << (u_int64_t)i) & p;
        res *= res; res %= n;
        res *= one ? x : 1; res %= n;
    }
    return res;
}

int main(int ac, char** av)
{
    return RUN_ALL_TESTS(ac, av);
}

TEST_GROUP(TG)
{

};

TEST(TG, a1)
{
    CHECK_EQUAL(24, powMod(2, 10, 1000));
    CHECK_EQUAL(5, powMod(5, 30, 10));
    CHECK_EQUAL(12219, powMod(423, 324, 34134));
    CHECK_EQUAL(7509, powMod(423, 324231, 34134));
    CHECK_EQUAL(24661, powMod(9874, 3747641, 34131));
}