Mersenne prímek

 

         A számítógépes információtovábbítás biztonságossá tétele érdekében az adatok titkosítására van szükség. A legelterjedtebb titkosítási mód az RSA, mely egy nyílt kódú, aszimmetrikus titkosító eljárás. Ehhez az eljáráshoz szükség van két elég nagy prímszámra. Ezek szorzata és egy ehhez a szorzathoz relatív prímszám a nyilvános kulcs, melyet mindenki ismerhet. Az egyik prímszámot az információ-küldő, a másikat a fogadó birtokolja. Hatványozás és maradékképzések segítségével a titkosított üzenetet csak a fogadó képes a saját kulcsa segítségével visszafejteni. Az egész eljárás biztonsága attól függ, hogy nyilvános kulcsban szereplő elég nagy prímszámok valóban elég nagyok-e. A cél minél nagyobb prímszámok előállítása, mert minél nagyobb egy szám, prímszám volta, illetve ha nem prím, akkor a szorzattá alakítása, annál hosszabb ideig lehetséges, és itt a hosszú idő alatt évmilliárdokra kell gondolni, még a mai leggyorsabb számítógépekkel is.

 

Elég nagy prímszám előállításánál leggyakrabban a Mersenne-féle számok között keresnek. A Mersenne-féle számok a következő alakúak:

 

         2p-1,

 

ahol a p maga is prímszám. A legnagyobb ismert Mersenne-féle prímszám a 47., mely közel 13 millió tízes számrendszerbeli számjegyként írható fel, és egy mai gyors személyi számítógép egy hónapos munkájának az eredménye.

 

         Az itt található program csak demonstráció, nem képes a fent említett méretű prímszámok közelébe sem érni. Azért az első 10 Mersenne-féle prímet produkálja.

 

         A futtatási kép:

 

 

         A program listája:

 

unit UMersenne;

interface

uses
  Windows, MessagesSysUtilsVariantsClassesGraphics,

  ControlsForms, DialogsStdCtrlsGrids;

type
  TfmMersenne = class(TForm)
    lbMersenneTLabel;
    sgTablaTStringGrid;
    btKilepesTButton;
    procedure btKilepesClick(SenderTObject);
    procedure FormCreate(SenderTObject);
  private
    Private declarations }
  public
    Public declarations }
  end;

var
  fmMersenneTfmMersenne;

implementation

{$R *.dfm}

procedure TfmMersenne.btKilepesClick(SenderTObject);
begin
  Close;
end;

Function Prime(S: Int64): Boolean;
Var J: Word;
Begin
  Prime:= FalseIf S In [0,1] Then Exit;
  Prime:= TrueIf S In [2,3] Then Exit;

  Prime:= FalseIf (S Mod 6<>1) And (S Mod 6<>5) Then Exit;
  Prime:= True;
  For J:= 2 To S-1 Do If (S Mod J)=0 Then
  Begin Prime:= FalseBreak End;
End;

Function Hatvany(P: Word): Int64;
Begin
  If P=0 Then Hatvany:= 1 Else Hatvany:= 2*Hatvany(P-1);
End;

procedure TfmMersenne.FormCreate(SenderTObject);
Var I, N, M: LongInt;
begin
  With sgTabla Do
  Begin
    ColWidths[2]:= 140;

    Cells[0,0]:= 'Sorsz.';
    Cells[1,0]:= 'P';
    Cells[2,0]:= '2^P-1';
    Cells[3,0]:= 'Prim?';
    Cells[4,0]:= 'Merse.sorsz.';
    I:= 0; M:= 0;
    For N:= 1 To 1000 Do If Prime(N) Then
    Begin
      If RowCount<I+2 Then RowCount:= RowCount+1;
      Inc(I);
      Cells[0,I]:= IntToStr(I);
      Cells[1,I]:= IntToStr(N);
      Cells[2,I]:= IntToStr(Hatvany(N)-1);
      If Prime(Hatvany(N)-1) Then
      Begin
        Cells[3,I]:= 'Igen'; Inc(M); Cells[4,I]:= IntToStr(M);
      End
      Else Cells[3,I]:= 'Nem';
    End;
  End;
end;

end.