Find the power of and than modules large numbers

[Tomstud122]

I am trying to find the power of very large numbers and than the modules

unsigned long long base = 888999000, exponent = 202404606, modulus = 237291793913;


		if ((base < 1) || (exponent < 0) || (modulus < 1)) {
			cout << "Invalid";
		}
		unsigned long long result = 1;
		while (exponent > 0) {
			if ((exponent % 2) == 1) {
				result = (result * base) % modulus;
			}
			base = (base * base) % modulus;
			exponent = floor(exponent / 2);
		}
		cout << result;

Works if i cut the numbers to smaller ones 888999, 202404, 23729179

What other way could i do this?

[Repeater]

I don't understand the question.

Given the input values
base = 888999000, exponent = 202404606, modulus = 237291793913
what are you trying to work out?

If the input was
base = 3, exponent = 4, modulus = 5
what would be the correct answer? Would it be (3 to-the-power-of 4) % 5 ?

[Tomstud122]

Sorry about that

Yes that is exactly what i'm trying to do (3 to-the-power-of 4) % 5

[tpb]

You want to be able to multiply two 64-bit numbers, so you need a 128 bit result. The easiest fix is to use gcc's 128 bit type (presumably MS has something similar). Alternatively, you can use a bignum library (or make your own 128-bit multiply and modulus).

#include <iostream>

uint64_t expmod(uint64_t base, uint64_t exponent, uint64_t modulus) {
    uint64_t result = 1;
    while (exponent > 0) {
        if (exponent & 1)
            result = ((__uint128_t)result * base) % modulus;
        base = ((__uint128_t)base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

int main() {
    uint64_t base     =    888999000,
             exponent =    202404606,
             modulus  = 237291793913;
    std::cout << expmod(base, exponent, modulus) << '\n';  // 202609913015
}

I have no idea if that's the right answer.

[Tomstud122]

Thank you for trying to help i looked at it and the answer is 236031767333

You can check it here
https://www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html

[tpb]

So you trust one random person's code over another random person's code? :-)

Actually, I've checked the answer and my code is correct. Presumably the javascript behind your link is not using 128 bits under the hood.

A more powerful online calculator: https://www.dcode.fr/modular-exponentiation