dh.c

// The 202020202th prime
#define P 4267031897ul
#define G 5

#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdlib.h>

static inline uint32_t
modp(uint32_t a, uint32_t b) {
	uint64_t t = (uint64_t)a * b;
	return (uint32_t)(t % P);
}

static uint32_t
_powmodp(uint32_t a, uint32_t b) {
	if (b==1) {
		return a;
	}
	uint32_t t = _powmodp(a, b/2);
	t = modp(t,t);
	if (b % 2 == 1) {
		t = modp(t, a);
	}
	return t;
}

// calc a^b % p
uint32_t
powmodp(uint32_t a, uint32_t b) {
	if (a > P)
		a%=P;
	return _powmodp(a,b);
}

uint32_t
randomint32() {
	uint32_t a = rand();
	uint32_t b = rand();
	return a << 16 | b;
}

int
main() {
	int a = randomint32();
	int b = randomint32();
	uint32_t A = powmodp(G, a);
	uint32_t B = powmodp(G, b);
	uint32_t secret1 = powmodp(B,a);
	uint32_t secret2 = powmodp(A,b);
	assert(secret1 == secret2);
	printf("a=%u b=%u s=%u\n", a,b,secret1);

	return 0;
}