// ExEuclide.cpp: розширений бінарний алгоритм Евкліда
// Обернене значення за модулем n
// Приклад: 5^(-1) mod 14 = 3, 2^(-1) mod 14 не існує

#include <iostream>
using namespace std;

#define isEven(x)  ((x & 0x01) == 0)
#define isOdd(x)   (x & 0x01)
#define swap(x, y) (x^=y, y^=x, x^=y)

void ExtBinEuclid(int* u, int* v, int* u1, int* u2, int* u3)
{
	// Якщо u < v, то u і v будуть переставлені

	int k, t1, t2, t3;
	if (*u < *v) swap(*u, *v);
	for (k = 0; isEven(*u) && isEven(*v); ++k)
	{
		*u >>= 1;
		*v >>= 1;
	}

	*u1 = 1;
	*u2 = 0;
	*u3 = *u;
	t1 = *v;
	t2 = *u - 1;
	t3 = *v;
	do {
		do {
			if (isEven(*u3)) {
				if (isOdd(*u1) || isOdd(*u2)) {
					*u1 += *v;
					*u2 += *u;
				}
				*u1 >>= 1;
				*u2 >>= 1;
				*u3 >>= 1;
			}
			if (isEven(t3) || *u3 < t3)
			{
				swap(*u1, t1);
				swap(*u2, t2);
				swap(*u3, t3);
			}
		} while (isEven(*u3));

		while (*u1 < t1 || *u2 < t2)
		{
			*u1 += *v;
			*u2 += *u;
		}
		*u1 -= t1;
		*u2 -= t2;
		*u3 -= t3;
	} while (t3 > 0);
	while (*u1 >= *v && *u2 >= *u)
	{
		*u1 -= *v;
		*u2 -= *u;
	}
	*u1 <<= k;
	*u2 <<= k;
	*u3 <<= k;
}


int main(int argc, char* argv[])
{
	setlocale(LC_CTYPE, "ukr");
	int a, b, gcd, u, v;
	cout << "u = ";	cin >> u;
	cout << "v = ";	cin >> v;
	if (u <= 0 || v <= 0)
	{
		cout << "Аргументи повинні буди додатними!" << endl;
		return -2;
	}

	ExtBinEuclid(&u, &v, &a, &b, &gcd);

	cout << a << " * " << u << " + (-" << b << ")"
		<< v << " = " << gcd << endl;
	if (gcd == 1)
		cout << "Обернене значення " << v << " mod " << u << " = "
		<< u - b << endl;
	else
		cout << "Оберненого значення не існує!" << endl;
	system("pause");

	//Обернена конгруентна послідовність
	int A[100];
	int* B = new int[100]; int* p = B;
	B[0] = 1;  // B[i], *(p+i)
	int m = 65537;
	for (int i = 1; i < 100; i++) {
		int t = m;
		ExtBinEuclid(&B[i-1], &t, &a, &b, &gcd);
		int inv = a;
		if (a < 0) 	a += m;
		B[i] = (2053 * inv + 7013)%m;
		cout << B[i] << " ";
	}
	delete[] B;
	return 0;
}