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

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

var
PArray:array[1..100] of integer;


procedure TForm1.Button1Click(Sender: TObject);
var
a,b,p,g1,i:integer;
A1,B1,K1,K2:longint;
begin
  Randomize;
  a:=random(40)+1;
  b:=random(40)+1;
  p:=Arrayes;
  g1:=g(p);
  edit1.text:=inttostr(a);
  edit2.text:=inttostr(b);
  edit3.text:=inttostr(p);
  edit4.text:=inttostr(g1);
  A1:=modes(g1,a,p);
  B1:=modes(g1,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;   // Вычисляет A^e mod m
var i: integer;
begin
  result := 1;
  for i:=1 to e do result := (result * A) mod m;
end;


function TForm1.Arrayes:integer;  // Создает случайное простое число от 3 до 150 ...
var
 k,i,j,d:integer;
begin
k:=1;
PArray[1]:=2;
for i:=3 to 150 do
  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]:=i;
       end;
    end;
  end;
  Randomize;
result:=PArray[Random(k)];
end;

function TForm1.Eiler(A,B: integer): integer;
begin
  while (A <> B) do
  begin
    if (A > B) then 
      Dec(A, B)
    else 
      Dec(B, A);
  end;
  Eiler := A;
end;

function TForm1.fi(p:integer):integer;  // Вычисляет количество взаимно простых чисел для  p
var
F,I:integer;
begin
  F := 0;
  for I := 1 to p-1 do
    if (Eiler(I, p) = 1) then
      Inc (F);
  fi:=F;
  edit9.Text:=inttostr(F);
end;

function TForm1.g(p:integer):longint;   // По идее ищет g
var
k,j,kaa:integer;
per:longint;
begin
k:=fi(p);                                 // В алгоритме ниже это j(p)
for kaa:=2 to p do                   // Перебираем натуральные числа в поиске g
    per := 1;
    for j:=1 to k do                   //
    per := (per * kaa);             // 
    dec(per);                           // 3 строки вычисляют gk - 1
    if ((per mod p) = 0)  then    // если разность gk - 1 делится на p
          begin
           result:=kaa;               // искомое число
           //break;                     // Прекращаем поиск g, 
          end;
end;

По идее почти все готово, только не получается выполнить проверку для числа g, которое является первообразным корнем по модулю p...
Опять появляются очень большие числа, хотя теперь вроде все нормально ....

Справка: Первообразный корень по модулю p, такое число g, что положительное наименьшее число k, для которого разность g^k - 1 делится на p (g^k сравнимо с 1 по модулю p), совпадает c j(p), где j(p) - число натуральных чисел, меньших p и взаимно простых с p. Например, при p =? 7 П. к. по модулю 7 является число 3. Действительно j(7) = 6; числа 3¹ - 1 = 2, 3² - 1 = 8, 3³ - 1 = 26, 3⁴ - 1 = 80, 3⁵ - 1 = 242 не делятся на 7, лишь 3⁶ - 1 = 728 делится на 7. П. к. существуют, когда p = 2, p = 4, p = t^a, p = 2t^a (где t - простое нечётное число, a - целое ³1), а для других модулей их нет. Число П. к. в этих случаях равно j[j(p)] (числа, разность которых кратна m, не считаются за различные)