Gymnasium Kamenz/Informatik/Verschlüsselung

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
[[Bild:InfWolfS_Verschlüsselung.gif|InfWolfS_Verschlüsselung.gif|center]]
:
== 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|100px|links]]

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

[[Bild:InfWolfS_Eratos_map.jpg|center]]


=== 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..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
    for i:=2 to n do liste[i]:=i;
  for i:=2 to n do
  begin
   j:=2*i;
   // while j
   // Implementation des Algorithmus
  end;
 end;
</code>

<code id="4d4ba965860e7" hidden>
var testliste: array[0..3000000] 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 ===

# 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.