Inverse modulo via the euclidean algorithm

inverse_modulo.d

long inverse_modulo(long a, long n)
{
	auto t0 = 0L;
	auto t1 = 1L;
	auto r0 = n;
	auto r1 = a;

	while (r1 != 0)
	{
		auto q = r0 / r1; 
		
		auto r_new = r0 - q * r1;
		r0 = r1;
		r1 = r_new;

		auto t_new = t0 - q * t1;
		t0 = t1;
		t1 = t_new;
	}
	
	if (r0 != 1)
		return 0;

	if (t0 < 0)
		return t0 + n;

	return t0;
}