---

program RSA_Short;

// Быстрое возведение в степень по модулю
function ModPow(b, e, m: int64): int64;
begin
  Result := 1; b := b mod m;
  while e > 0 do
  begin
    if Odd(e) then Result := Result * b mod m;
    b := b * b mod m;
    e := e div 2;
  end;
end;

// Расширенный алгоритм Евклида: возвращает d, где e*d ≡ 1 mod phi
function Inverse(e, phi: integer): integer;
var a, b, x0, x1, t: integer;
begin
  a := e; b := phi; x0 := 1; x1 := 0;
  while b <> 0 do
  begin
    t := a div b;
    a := a - t * b; Swap(a, b);
    x0 := x0 - t * x1; Swap(x0, x1);
  end;
  if x0 < 0 then x0 := x0 + phi;
  Result := x0;
end;

function GCD(a, b: integer): integer;
begin
  while b <> 0 do begin var t := b; b := a mod b; a := t; end;
  Result := a;
end;

var p, q, n, phi, e, d: integer;
    s, r: string;
    c: int64;

begin
  write('p = '); readln(p);
  write('q = '); readln(q);
  n := p * q;
  phi := (p - 1) * (q - 1);
  writeln('n = ', n, ', phi = ', phi);

  repeat
    write('e = '); readln(e);
    if (e <= 1) or (e >= phi) or (GCD(e, phi) <> 1) then
      writeln('e должно быть 1 < e < ', phi, ' и НОД(e,phi)=1');
  until (e > 1) and (e < phi) and (GCD(e, phi) = 1);

  d := Inverse(e, phi);
  writeln('Открытый ключ: (', e, ', ', n, ')');
  writeln('Закрытый ключ: (', d, ', ', n, ')');

  write('Слово: '); readln(s);

  write('Шифр: ');
  for var i := 1 to Length(s) do
  begin
    c := ModPow(Ord(s[i]), e, n);
    write(c, ' ');
  end;
  writeln;

  write('Расшифровка: ');
  for var i := 1 to Length(s) do
  begin
    c := ModPow(Ord(s[i]), e, n);
    write(Chr(ModPow(c, d, n)));
  end;
  writeln;
end.