/***************************************************
* This code is freely usable for OpenAlarm-related *
* works. Sources must remain public.               *
***************************************************/

#include <stdio.h>

// This must fit a long (remember we're just TESTING!
#define DH_BITS 10

// Calcola x=(a*b)mod m
long mulmod(long a, const long b, const long m)
{
    int cnt;
    long x=0;

    for(cnt=0; cnt<DH_BITS; ++cnt) {
	int c;

	c=(b&(1<<cnt))?1:0;	// bit 'cnt' di b
	if(c) {
	    x+=a;
	    while((x-m)>=0) {
		x-=m;
	    }
	}
	a<<=1;
        while((a-m)>0) {
    	    a-=m;
	}
    }
    return x;
}

// Calcola r=(a^b) mod m
long powmod(long a, const long b, const long m)
{
    int cnt;
    long r=1;

    for(cnt=0; cnt<DH_BITS; ++cnt) {
//printf("loop %d: a=%d, b=%d, r=%d\n", cnt, a, b, r);
	if(b&(1<<cnt)) {
	    // Attenzione, qui! mulmod modifica la COPIA di r!
	    // Ma tanto poi r viene sovrascritto con mulmod::x
	    r=mulmod(r, a, m);
	}
	a=mulmod(a, a, m);
    }
    return r;
}

int main(int argc, char *argv[])
{
    long a,b,m, y;

    if(argc != 4) {
	printf("%s a b m\n", argv[0]);
	return(1);
    }

    a=atoi(argv[1]);
    b=atoi(argv[2]);
    m=atoi(argv[3]);

    y=powmod(a,b,m);
    printf("%d^%d = %d (mod %d)\n", a, b, y, m);
    return 0;
}