И понятия не имею как это запрограммировать, если можете, помогите пожалуйста.
В методичке есть реализация на 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; }
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, для которого разность 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, не считаются за различные)