#include "euclid.h"

void ExtendedEuclid (Integer b, Integer n, Integer * common, 
		     Integer *binvmodn){
    Integer n0 = n, b0 = b, t0 = 0, t =1;
    Integer q = n0/b0, r = n0-q*b0;
    Integer temp;
    while (r>0) {
	temp = t0-q*t;
	if (temp >= 0) temp = temp % n;
	else temp = n - (( -temp) % n);
	t0 = t;
	t = temp;
	n0 = b0;
	b0 = r;
	q = n0/b0;
	r = n0 - q * b0;
    }
    *common = b0;
    *binvmodn = t;
}

Integer ModularExp(Integer x, Integer b, Integer n){
    Integer z = 1;
    long el = lg (b) + 1;
    for (long i = el - 1; i >= 0; i--){
        pow (z, 2, z);
        mod (z, n, z);

        if (testbit(b, i)){
            mul (z, x, z);
            mod (z, n, z);
        }
    }
    return z;
}