Алгоритм Диффи-Хеллмана, Проблемы с математикой (( Опции

[SeregaR1Val]

В принципе реализация алгоритма понятна, проблемы с нахождением первообразного корня по модулю m

http://ru.wikipedia.org/wiki/Первообразный..._(теория_чисел)

И понятия не имею как это запрограммировать, если можете, помогите пожалуйста.

В методичке есть реализация на C++, а обучение на Delphi, поэтому непонятно вообще ...


Реализация

Функция powmod() выполняет бинарное возведение в степень по модулю, а функция generator (int p) - находит первообразный корень по простому модулю (факторизация числа здесь осуществлена простейшим алгоритмом за ). Чтобы адаптировать эту функцию для произвольных , достаточно добавить вычисление функции Эйлера в переменной phi.

int powmod (int a, int b, int p) {
	int res = 1;
	while (b)
		if (b & 1)
			res = int (res * 1ll * a % p),  --b;
		else
			a = int (a * 1ll * a % p),  b >>= 1;
	return res;
}
 
int generator (int p) {
	vector<int> fact;
	int phi = p-1,  n = phi;
	for (int i=2; i*i<=n; ++i)
		if (n % i == 0) {
			fact.push_back (i);
			while (n % i == 0)
				n /= i;
		}
	if (n > 1)
		fact.push_back (n);
 
	for (int res=2; res<=p; ++res) {
		bool ok = true;
		for (size_t i=0; i<fact.size() && ok; ++i)
			ok &= powmod (res, phi / fact[i], p) != 1;
		if (ok)  return res;
	}
	return -1;
}

Сообщение отредактировано: SeregaR1Val - 27.04.2010 0:15