In other words is there such an algorithm for :
// powmod(m,e,n) = m^e % n
unsigned long long powmod(unsigned long m, unsigned long e, unsigned long long n)
that it doesn't overflow for let's say where m = 2^32 - 1, e = 3, n = 2^64 - 1 without gmp or such libraries used?
Yes, you can do this. Go code below since there's a builtin
Exp
to test against; translation to C should be very straightforward, since the only library use is confined to tests.C translation of above code with edge testing values in main function: