Bigmod

bigmod.c

/*
 * bigmod: caculate ( base ^ power ) mod modular
 * usage: bigmod ( base, power, modular);
 *
 * input: base, power, modular
 * output: return value
 *
 * example: print value of ( 2374859 ^ 3029382 ) % 36123
 *          output 13195
 */
#include <stdio.h>

typedef long long unsigned int uint64_t;

const uint64_t ONE = (uint64_t)1;

uint64_t bigmod(uint64_t base, uint64_t power, uint64_t modular)
{
	uint64_t ans, mask;
	for(ans=ONE, mask=ONE<<63, base %= modular ;mask;mask>>=1){
		ans = ( ans * ans ) % modular;
		if( power & mask ){
			ans *= base;
			if( ans > modular )
				ans %= modular;
		}
	}
	return ans;
}

int bigmod_simp(int b, int p, int m)
{
	int ans, msk;
	for(ans=1, b%=m,msk=1<<30;msk;msk>>=1){
		ans = ( ans * ans ) % m;
		if( msk & p )
			ans = ( ans * b ) % m;
	}
	return ans;
}

int main()
{
	printf("%llu\n", bigmod(2374859L,3029382L,36123L));
	return 0;
}