Gymnasium Kamenz/Informatik/Verschlüsselung

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
:::::[[Bild:InfWolfS_Verschlüsselung.gif|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.<br /> 
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 ==
[[Bild: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.<br />
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.<br />
::::::::[[Bild:InfWolfS_Eratos_map.jpg]]


=== Algorithmus nach Eratosthenes ===
* Notiere die natürlichen Zahlen, beginne mit <math>2</math>.

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

* Unterstreiche die <math>2</math> und streiche alle Vielfachen von <math>2</math>.

<blockquote>
<math>\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}, ...</math>
</blockquote>

* Unterstreiche die erste freie Zahl (in diesem Falle die Zahl <math>3</math>) und streiche deren Vielfachen.

<blockquote>
<math>\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}, ...</math>
</blockquote>

* Verfahre mit allen weiteren Zahlen ebenso.

<blockquote>
<math>\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}, ...</math>
</blockquote>

* Alle unterstrichenen Zahlen sind Primzahlen.

=== Hinweis zur Lösung ===

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


=== Implementation ===

<code id="4d35b3f554587">
var grenze: integer;
    liste : array[0..4000000] 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;
</code>

<code id="4d35b3f554606" hidden>
var testliste: array[0..1000000] of integer;

procedure testprimsieb(n: integer);
 var i, j: integer;
 begin 
  for i:=2 to n do testliste[i]:=i;
  for i:=2 to n do
  begin
   j:=2*i;
   while j<=n do
   begin
    testliste[j]:=0;
    j:=j+i;
   end;
  end;
 end;

function korrekt(n: integer): boolean;
 var i   : integer;
     test: boolean;
 begin
  test:=true;
  primsieb(n);testprimsieb(n);
  for i:=2 to n do 
   test:=test and (testliste[i]=liste[i]);
  result:=test;
 end;
</code>

<check>
result:=korrekt(20);
</check>

<run id="4d2cc6e0afa01">
grenze:=1000;
primsieb(grenze);
primausgabe(grenze);
</run>



=== Aufgaben ===

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