Verschlüsselung

Aus ProgrammingWiki

Archivierte Version vom 2011-01-26T07:17:18+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einführung
2 Ermittlung von Primzahlen

Einführung

Für die moderne Verschlüsselungstechnik sind Primzahlen überaus bedeutsam; z.B. für den RSA-Code oder Hybrid-Codes.
Die Potenzierung von Primzahlen kann als Einwegfunktion genutzt werden. Warum dies möglich ist, soll ein einfacher Versuch mit einem Algorithmus zur Primzahlermittlung verdeutlichen.

Ermittlung von Primzahlen

Der griechische Mathematiker, Geograph, Philosoph, Philologe und Dichter Eratosthenes von Kyrene (zwischen ca. 275 bis ca. 195 v. Chr.) war der erste Gelehrte der Antike, der durch eine Messung den Umfang der Erde mit erstaunlicher Genauigkeit bestimmt hat.
Auf ihn geht aber auch ein einfacher Algorithmus zur Ermittlung "aller" Primzahlen zurück, das sogenannte Das Sieb des Eratosthenes. Warum "man" doch nicht alle so einfach "aussieben" kann, sollen Sie empirisch zeigen.

Algorithmus nach Eratosthenes

Notiere die natürlichen Zahlen, beginne mit 2.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

Unterstreiche die 2 und streiche alle Vielfachen von 2.

\usepackage{ulem} \uline{2}, 3, \xout{4}, 5, \xout{6}, 7, \xout{8}, 9, \xout{10}, 11, \xout{12}, 13, \xout{14}, 15, \xout{16}, 17, \xout{18}, 19, \xout{20}, ...

Unterstreiche die erste freie Zahl (in diesem Falle die Zahl 3) und streiche deren Vielfachen.

\usepackage{ulem} \uline{2}, \uline{3}, \xout{4}, 5, \xout{6}, 7, \xout{8}, \xout{9}, \xout{10}, 11, \xout{12}, 13, \xout{14}, \xout{15}, \xout{16}, 17, \xout{18}, 19, \xout{20}, ...

Verfahre mit allen weiteren Zahlen ebenso.

\usepackage{ulem} \uline{2}, \uline{3}, \xout{4}, \uline{5}, \xout{6}, \uline{7}, \xout{8}, \xout{9}, \xout{10}, \uline{11}, \xout{12}, \uline{13}, \xout{14}, \xout{15}, \xout{16}, \uline{17}, \xout{18}, \uline{19}, \xout{20}, ...

Alle unterstrichenen Zahlen sind Primzahlen.

Hinweis zur Lösung

Belege ein eindimensionales Feld (Array) mit n ganzen Zahlen. Beginne mit der 2.
Setze die Vielfachen jedes der von Null verschiedenen Feldelemente auf Null. Beginne ebenfalls bei 2.
Gib nur die Feldelemente aus, die von Null verschieden sind.

Implementation

var grenze: integer;
    liste : array[0..3000000] of integer;
procedure primausgabe(n: integer);
 var i, zaehler: integer;
 begin
  zaehler:=0; 
  for i:=2 to n do
   if liste[i]<>0 then
   begin
    zaehler:=zaehler+1; 
    if (zaehler mod 15)=0 then
     writeln(inttostr(liste[i])+', ')
    else
     write(inttostr(liste[i])+', ');
   end;
 end;

procedure primsieb(n: integer);
 var i, j: integer;
 begin 
  // Implementation des Algorithmus
 end;

grenze:=1000;
primsieb(grenze);
primausgabe(grenze);

Aufgaben

Implementieren Sie die Befehle für das "Aussieben" der Primzahlen.
Testen Sie mit dem fertigen Programm die benötigte Laufzeit. Verändern Sie dazu die Grenzwerte in geeigneten Schritten bis zu 3000000.
Tragen Sie die Zeiten in einem Diagramm ein.
Stellen Sie eine Vermutung zum weiteren Kurvenverlauf an.

Verschlüsselung

Inhaltsverzeichnis

Einführung

Ermittlung von Primzahlen

Algorithmus nach Eratosthenes

Hinweis zur Lösung

Implementation

Aufgaben

Suche