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

[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]

Терзают сомнения, что алгоритм описанный в методе то, что должно быть )) Ну да ладно ...

procedure TForm1.Button1Click(Sender: TObject);
var
a,b,p,g,i:integer;
A1,B1,K1,K2:longint;
begin
  Randomize;
  a:=random(10)+1;
  b:=random(10)+1;
  i:=random(10)+1;
  p:=PArray[i];
  g:=p+5;
  edit1.text:=inttostr(a);
  edit2.text:=inttostr(b);
  edit3.text:=inttostr(p);
  edit4.text:=inttostr(g);
  A1:=modes(g,a,p);
  B1:=modes(g,b,p);
  edit5.text:=inttostr(A1);
  edit6.text:=inttostr(B1);
  K1:=modes(B1,a,p);
  K2:=modes(A1,b,p);
  edit7.text:=inttostr(K1);
  edit8.text:=inttostr(K2);
  if (K1=k2) then
    label3.Caption:='Соединение установлено' else
    label3.Caption:='Неудача, кэп!';

end;


Function TForm1.modes(A,e,m:integer):longint;
var
k:longint;i:integer;
begin
for i:=1 to e do
  begin
    A:=sqr(A);
  end;
k:=A mod m;
result:=k;
end;

Функция modes по моей задумке вычисляет выражение A^e mod m
Но почему-то ответ почти всегда 0 или еще что-то, но не то, что надо! Подскажите, пожалуйста, в чем ошибка?

Сообщение отредактировано: SeregaR1Val - 28.04.2010 17:46