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

[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 - 27.04.2010 0: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;

[SeregaR1Val]

TList<Integer> не пропускает, исправил на TList of integer ... тоже самое ...

[volvo]

Блин... Я все время забываю, что не у всех Дельфи 2009/2010... Тогда придется делать через Array of Integer...

[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 21:46

[Ozzя]

var
  r,k:longint;i:integer;
begin
r:=1;
for i:=1 to e do
  begin
    r:=r*A;
  end;
k:=r mod m;
result:=k;
end;

Сообщение отредактировано: Ozzя - 28.04.2010 22:03

[volvo]

Функция modes по моей задумке вычисляет выражение A^e mod m

На самом деле она вычисляет (A^2^e) mod m, и возвращает 0 только потому что не хватает разрядности. Даже в UInt64 не помещается промежуточный результат вычисления modes(2, 6, {ну_здесь_неважно_что_будет})

[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 мин.
Извините, глупая ошибка была ... нашел!

[SeregaR1Val]

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;

На практике e - степень, оказывается достаточно большой и как написал volvo не хватает разрядности, а как можно избавиться от этой проблемы?

[volvo]

а как можно избавиться от этой проблемы?

Вот это:

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

, если я ничего не путаю, должно возвращать такой же результат, как и функция, приведенная Оззей. Твой код вообще неправильный, я написал почему...

[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, не считаются за различные)

[volvo]

function TForm1.Arrayes:integer;  // Создает случайное простое число от 3 до 150 ...
// bla-bla-bla ...

  Randomize; // <--- Вот этот Randomize закомментируй и запусти программу еще раз
  result := PArray[Random(k)];
end;

Еще раз: Randomize должна вызываться ОДИН раз в начале программы, не 2 и не 3 и не больше... Один.

[SeregaR1Val]

Спасибо, стало лучше работать, но g в половине случаев принимает значение '4523261', хотя перебор идет от 2 до p.. Вообще не понятно что за число и откуда оно ...

function TForm1.g(p:integer):longint;  
var
k,j,kaa:integer;
per:longint;
begin
k:=fi(p);
for kaa:=2 to p do          //     <-----от 2 до p 
    begin
    per := 1;
    for j:=1 to k do
    per := (per * kaa);
    dec(per);
    if ((per mod p) = 0)  then
          begin
           result:=kaa;
           exit;
          end;
    end;
end;

[volvo]

Ну, а теперь посмотри внимательно на функцию (я не запускаю, мне сейчас негде проверить, Дельфя здесь не установлена, но это видно и без запуска). Если (per mod p) = 0 выполняется - то ты что-то присваиваешь в Result, а если нет? Вот закончился цикл, и ни для одного kaa (чувствую себя Киплингом прямо) это условие не выполнилось, что функция вернет, ты подумал? Мусор она вернет. Что в стеке валялось на том месте, где была создана переменная Result - то и вернется тебе под видом результата...

Либо в самом начале либо в самом конце функции присвой Result-у значение, которое будет возвращаться при невыполнении условия.

[SeregaR1Val]

Спасибо большое! Очень помог!