Первообразный корень по модулю

[Samopal]

Может ли кто нибудь подсказать алгоритм вычисления первообразного корня по модулю?...

в контрольной надо написать систему обмена ключами Диффи-Хеллмана... Всё вроде бы как написал.. осталось только вот этот первообразный корень по модулю вкрутить....

[Пепел Феникса]

тырк
первая ссылка с гугла

[Samopal]

Так то оно да.....
Это я тож нашёл...

но сам алгоритм вычисления первообразного корня по модулю не могу вдуплить... =( как...

[Samopal]

Вот у меня есть код этой штуки нс С++

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;
}

мог бы мне кто помоч переделать это на паскаль?

[Samopal]

народ ну неужели так сложно? =\