Verschlüsselung

Aus ProgrammingWiki
< Gymnasium Kamenz < Informatik
Archivierte Version vom 2011-01-25T23:12:58+00:00. Aktuelle Version

Inhaltsverzeichnis

InfWolfS_Verschlüsselung.gif

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

InfWolfS_Eratosthenes.png

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 Bestimmung "aller" Primzahlen zurück, das sogenannte Das Sieb des Eratosthenes. Warum "man" doch nicht alle so einfach ermitteln kann, sollen Sie empirisch zeigen.

InfWolfS_Eratos_map.jpg


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




Aufgaben
  1. Testen Sie die benötigte Laufzeit. Verändern Sie dazu die Grenzwerte in geeigneten Schritten bis zu 4000000.
  2. Tragen Sie die Zeiten in einem Diagramm ein.