Помощь - Поиск - Пользователи - Календарь
Полная версия: Алгоритм Диффи-Хеллмана
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Делфи
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;
}
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 по моей задумке вычисляет выражение Ae mod m
Но почему-то ответ почти всегда 0 или еще что-то, но не то, что надо! Подскажите, пожалуйста, в чем ошибка?
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;
volvo
Цитата
Функция modes по моей задумке вычисляет выражение Ae mod m
На самом деле она вычисляет (A^2e) 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, sad.gif
end;
end;


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

Справка: Первообразный корень по модулю p, такое число g, что положительное наименьшее число k, для которого разность gk - 1 делится на p (gk сравнимо с 1 по модулю p), совпадает c j(p), где j(p) - число натуральных чисел, меньших p и взаимно простых с p. Например, при p =? 7 П. к. по модулю 7 является число 3. Действительно j(7) = 6; числа 31 - 1 = 2, 32 - 1 = 8, 33 - 1 = 26, 34 - 1 = 80, 35 - 1 = 242 не делятся на 7, лишь 36 - 1 = 728 делится на 7. П. к. существуют, когда p = 2, p = 4, p = ta, p = 2ta (где 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
Спасибо большое! Очень помог!
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.