program Twierdzenie_o_liczbach_pierwszych_i_jego_zastosowanie_do_szyfrowania_RSA;
{$N+}
uses crt;
var  i,p,q,k,N,M,a,a1,e,d:integer;
     potega,potega1,potega2:extended;
     reszta,reszta1,reszta2:integer;
function pierwsza(a:integer):boolean;
  var n:integer;
  begin
    pierwsza:=false;
    for n:=2 to round(sqrt(a)) do if a mod n=0 then exit;
    pierwsza:=true;
  end;
function NdoM(a,b:integer):extended;
  var n:integer;
      x:extended;
  begin
    x:=1;
    for n:=1 to b do x:=x*a;
    NdoM:=x;
  end;
function nwd(a,b:integer):integer;
  var r:integer;
  begin
    repeat
      r:=a mod b; a:=b; b:=r;
    until r=0;
    nwd:=a;
  end;
procedure liczba_d;
var m:integer;
begin
  a:=0;
  repeat
    a:=a+1; m:=a*(p-1)*(q-1)+1;
  until m mod e=0;
  d:= m div e;
end;

{******* program gl˘wny *********}
begin
  clrScr; randomize;
    repeat
      repeat
        repeat
          repeat
            p:=random(12)+2;
          until pierwsza(p)=true;
          repeat
            q:=random(12)+2;
          until (pierwsza(q)=true) and (p<>q);
          k := p * q;
          M := (p-1)*(q-1)+1;
          N := random(12)+2;
          potega:=NdoM(N,M);
        until (N<k) and (potega<1e14);
        reszta:=round(potega-int(potega/k)*k);

        repeat                                       
          e:=random(5)+2;
        until (nwd(e,p-1)=1) and (nwd(e,q-1)=1);
        liczba_d;
        potega1:=NdoM(N,e);
      until potega1<1e14;
      reszta1:=round(potega1-int(potega1/k)*k);
      potega2:=NdoM(reszta1,d);
    until (potega2<1e14) and (reszta1<>N);
    reszta2:=round(potega2-int(potega2/k)*k);

    textColor(green);                                   { Twierdzenie }
    writeLn('TW.2.');
    write('   Jezeli p,q-r˘zne liczby pierwsze i ');
    textColor(lightBlue); write('N');
    textColor(green); write('<p*q, to ');
    textColor(lightBlue); write('N');
    textColor(green); write('^(p-1)*(q-1)+1 mod p*q = ');
    textColor(lightBlue); writeLn('N');
    textColor(white); for i:=1 to 76 do write('_');

    textColor(green); writeLn; writeLn;                   { przyklad }
    write('Przyklad:');
    textColor(white);
    write('   p=',p:1,',  q=',q:1,',  p*q=',p*q:1,',  N=');
    textColor(lightBlue);
    write(N:1);
    textColor(white);
    writeLn(',  (p-1)*(q-1)+1=',M:1);
    textColor(lightBlue);
    write('              ',N:1);
    textColor(white);
    write('^',M:1,' mod ',k:1,' = ',potega:1:0,' mod ',k:1,' = ');
    textColor(lightBlue);
    write(reszta:1);

    textColor(green); writeLn; writeLn;                   { uog˘lnienie }
    writeLn('Uog˘lnienie:');
    write('  Jezeli p,q-r˘zne liczby pierwsze i ');
    textColor(lightBlue); write('N');
    textColor(green); write('<p*q, to ');
    textColor(lightBlue); write('N');
    textColor(green); write('^a*(p-1)*(q-1)+1 mod p*q = ');
    textColor(lightBlue); writeLn('N');
    textColor(green);
    writeLn('                                           gdzie a = 1, 2, 3, ...');

    for a1:=1 to 3 do
    begin
      textColor(white);
      write('     np.    a=',a1:1,'  p=',p:1,',  q=',q:1,',  p*q=',p*q:1,'  N=');
      textColor(lightBlue);
      write(N:1);
      M:=a1*(p-1)*(q-1)+1;
      potega:=NdoM(N,M);
      reszta:=round(potega-int(potega/k)*k);
      textColor(white);
      writeLn(',  a*(p-1)*(q-1)+1=',M:1);
      textColor(lightBlue);
      write('         ',N:1);
      textColor(white);
      write('^',M:1,' mod ',k:1,' = ',potega:1:0,' mod ',k:1,' = ');
      textColor(lightBlue); write(reszta:1);
      writeLn;
    end;

    writeLn;
    a1:=a;
    M:=a1*(p-1)*(q-1)+1;
    potega:=NdoM(N,M);
    reszta:=round(potega-int(potega/k)*k);
    textColor(green);
    writeLn('Zastosowanie:');                             { Zastosowanie-szyfrowanie RSA }
    textColor(lightBlue);
    write('  N');
    textColor(green);
    write('^M mod k = (');
    textColor(lightBlue);
    write('N');
    textColor(green);
    write('^e)^d mod k = (');
    textColor(lightBlue);
    write('N');
    textColor(green);
    write('^e mod k)^d mod k = ');
    textColor(lightRed);
    write('X');
    textColor(green);
    write('^d mod k = ');
    textColor(lightBlue);
    writeLn('N');
    textColor(green);
    writeLn('    gdzie M = a*(p-1)*(q-1)+1 = e*d i e,d wzglednie pierwsze z p-1 i q-1,');
    textColor(white);
    writeLn('    np.  a=',a:1,',  p=',p:1,',  q=',q:1,',  e=',e:1,',  d=',d:1,',  M=',M:1,',  k=',k:1);
    writeLn;
    textColor(lightBlue);
    write(N:1);
    textColor(white);
    write('^',M:1,' mod ',k:1,' = (');
    textColor(lightBlue);
    write(N:1);
    textColor(white);
    write('^',e:1,' mod ',k:1,')');

    write('^',d:1,' mod ',k:1,' = ');
    textColor(lightRed);
    write(reszta1:1);
    textColor(white);
    write('^',d:1,' mod ',k:1,' = ');
    write(potega2:1:0,' mod ',k:1,' = ');
    textColor(lightBlue); write(reszta2:1);

    textColor(white);writeLn;
    readLn;
end.