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

[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

[volvo]

Ну, а что именно непонятно? У тебя ж есть С++ ный код. Дословно это будет выглядеть так (если приведенный тобой код верен, конечно):

function generator(p: Cardinal): Integer;

  function powmod(a, b: Cardinal): Cardinal;
  begin
    result := 1;
    while b > 0 do
    begin
      if b and $1 > 0 then
      begin
        result := (result * a) mod p; dec(b);
      end
      else
      begin
        a := (a * a) mod p; b := b shr 1;
      end;
    end;
  end;

var
  i, n, phi: integer;
  ok: boolean;
  fact: TList<Integer>;

begin
  fact := TList<Integer>.Create;
  try
    phi := pred(p); n := phi;
    i := 2;
    while sqr(i) <= n do
    begin
      if n mod i = 0 then
      begin
        fact.Add(i);
        while n mod i = 0 do n := n div i
      end;
      inc(i);
    end;

    if n > 1 then fact.Add(n);
    for result := 2 to p do
    begin
      ok := true;
      i := 0;
      while (i < fact.Count) and ok do
      begin
        ok := ok and (PowMod(result, phi div fact[i]) <> 1);
        if ok then exit;
      end;
    end;
  finally
    fact.Free
  end;

  result := -1;
end;