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

[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 - 26.04.2010 20:15

[SeregaR1Val]

Спасибо. теперь работает лучше, помогите пожалуйста еще с одной деталькой этого алгоритма - создание случайного простого числа ...

function TForm1.Arrayes:integer;
var
 k,i,j,d:integer;
begin
k:=1;
PArray[1]:=2;                                 //Массив простых чисел. Для начала первое простое число - 2
for i:=3 to 150 do                            // Просматриваем чисда 3-150
  begin
  d:=0;    
  for j:=1 to k do                            // Пытаемся разделить число на число из массива простых чисел
  if ((i mod PArray[j])<>0) then       // Если не делится нацело увеличиваем счетчик
    begin
    inc(d);
    if (d=k) then                             // Если не делится нацело ни на одно из целых - значит целое
       begin
        inc(k);
        PArray[k]:=j;                        //Записываем его в массив простых чисел
       end;
    end;
  end;
  Randomize;
result:=PArray[Random(k)];           //Результат - случайное простое число из массива
end;

Сам перебираю, вроде все нормально, а в итоге он находит только одно число - 3

Добавлено через 6 мин.
Извините, глупая ошибка была ... нашел!