5 Zahlen

In diesem Kapitel werden der euklidische Algorithmus, das Sieb des Eratosthenes, der Heron-Algorithmus und ausgewählte Algorithmen für die Berechnung der Kreiszahl π und der eulerschen Zahl e behandelt.

Mathematiker haben die natürlichen Zahlen formula , die ganzen Zahlen formula , die rationalen Zahlen formula , die reellen Zahlen formula und die komplexen Zahlen formula erfunden. Zahlen sind also nicht naturgegeben, sondern ein Konstrukt des menschlichen Geistes. Daher hat der uns heute als selbstverständlich erscheinende Zahlenbegriff eine lange Geschichte.

In der griechischen Mathematik hatte das Wort Zahl seit Pythagoras (ca. 580–500 v. Chr.) die Bedeutung einer positiv natürlichen Zahl. Leonardo von Pisa, auch bekannt als Fibonacci (1170–1240), führte in seinem Buch Liber Abbaci (1202) die uns heute geläufigen indisch-arabischen Ziffern einschließlich der 0 ein [Stewart: 150]. Michael Stifel (1487–1567) überlegte sich, ob Brüche und irrationale Zahlen wahre oder fingierte Zahlen sind. Er stellte die Hypothese auf, dass zwischen zwei ganzen Zahlen unendlich viele Brüche, aber auch unendlich viele irrationale Zahlen liegen müssen [Gericke: 245 f.]. Simon Stevin (1548–1620) schlug 1585, auf der Suche nach einer präzisen Buchführungsmethode, eine Dezimalschreibweise als Ersatz für die zu seiner Zeit noch gebräuchlichen Brüche vor. Er betonte die besondere praktische Bedeutung seines Systems:

»Alle geschäftsmäßigen Berechnungen lassen sich unter alleiniger Nutzung ganzer Zahlen und ohne Hilfe von Brüchen durchführen.« [Stewart: 151]

Nachdem Leonhard Euler 1777 das Symbol i als Darstellung für formula veröffentlichte [Stewart: 188], schlug Caspar Wessel 1797 die Darstellung komplexer Zahlen in der komplexen Zahlenebene vor. Carl Friedrich Gauß formulierte 1799 in seiner Dissertation, unabhängig von Wessel, dieselbe Idee [Stewart: 192]. Die Bezeichnung komplexe Zahl hat Gauß erst 1831 eingeführt. Obwohl Cardano (1501–1576) diese Bezeichnung noch nicht kannte, löste er die gemischt quadratische Gleichung formula . Er bezeichnete formula als quantitas sophistica. Gericke übersetzt diesen Ausdruck mit formale Größe [Gericke: 238].

Abbildung 5.1 veranschaulicht die aktuell bekannten Zahlen als Mengendiagramm.

Abbildung 5.1 Strukturierung der Zahlen

Die natürlichen Zahlen formula sind eine Teilmenge der ganzen Zahlen formula . Diese sind eine Teilmenge der rationalen Zahlen formula . Diese sind wiederum eine Teilmenge der reellen Zahlen formula , und diese sind letztendlich eine Teilmenge der komplexen Zahlen formula .

Mathematiker formulieren diesen Zusammenhang mit den Symbolen der Mengenlehre so:

Zahlen wurden zunächst erfunden, um praktische Probleme des Alltags zu bewältigen: das Zählen, Teilen, Rechnen und das Lösen von Gleichungen.

Die folgenden fünf Gleichungen verdeutlichen, wie die Menge der natürlichen Zahlen erweitert werden muss, um diese Gleichungen lösen zu können:

Natürliche Zahlen

Durch Umstellen erhält man die Lösungen der Gleichungen. Die Lösung der Gleichung (1) ist eine natürliche Zahl x = 2. Wenn für x der Wert 2 eingesetzt wird, ist die Gleichung erfüllt. Die Aussage der Gleichung ist wahr, wenn x = 2 ist, denn es gilt: 2 – 2 = 0. Für die Menge der natürlichen Zahlen schreibt man:

Jedes nachfolgende Element wird dadurch erzeugt, dass die Zahl 1 zum Vorgänger addiert wird. Dieser Prozess der fortlaufenden Operation endet nie. Es gibt also unendlich viele natürliche Zahlen.

Die Operationen der Addition und der Multiplikation mit natürlichen Zahlen ergeben wieder natürliche Zahlen. Die Division von zwei natürlichen Zahlen muss nicht aufgehen, es kann ein Rest entstehen.

Komplexe Zahlen

Um Gleichungen vom Typ x² + a = 0 mit Wurzeln aus negativen Zahlen lösen zu können, wurde die imaginäre Einheit i eingeführt. Es gilt: i² = –1. Die Gleichung (5) hat demnach die Lösungen und . Die gemischt quadratische Gleichung

hat die Lösungsmenge:

Die Lösung setzt sich aus einem Real- und einem Imaginärteil zusammen. Diese Zahlen sind Teilmengen der komplexen Zahlen . Um Gleichungen von diesem Typ x² + p ⋅ x + q = 0 mit (p / 2)² – q < 0 lösen zu können, muss die Menge der reellen Zahlen um die Menge der komplexen Zahlen erweitert werden. Der Konsolendialog zeigt die Lösung der gemischt quadratischen Gleichung mit SymPy:

>>> from sympy import *
>>> x=symbols('x')
>>> y=x**2-4*x+29
>>> solve(y,x)
[2 - 5*I, 2 + 5*I]

Formal schreibt man für die Menge der komplexen Zahlen:

Darstellung im Dezimalsystem

In allen Kulturen werden Zahlen durch Ziffern repräsentiert. Die Ziffern des dezimalen Zahlensystems stammen aus Indien, sie werden hintereinander in eine Reihe notiert. Die Stelle, an der eine Ziffer steht, bestimmt den Wert der Zahl.

Wählt man eine Ziffer in der Mitte der Ziffernfolge aus, dann repräsentiert die weiter links von der gewählten Ziffer stehende Ziffer einen höheren Zahlenwert als die rechts davon stehende Ziffer. Aus der Anordnung der Ziffern entsteht ein Zahlensystem. Weil die Stelle einer Ziffer den Wert einer Zahl bestimmt, heißt dieses Konstrukt auch Stellenwertsystem . Im dezimalen Zahlensystem wird der Wert einer Ziffer berechnet, indem man die Ziffer a aus dem Ziffernvorrat {0,1,2,3,4,5,6,7,8,9} mit einer ganzzahligen Potenz der Basis a ⋅ 10ⁿ multipliziert. Die ganze Zahl n repräsentiert den Stellenwert . Gezählt wird von 0 bis n, aber nicht von links nach rechts, sondern umgekehrt, beginnend mit der letzten Ziffer, von rechts nach links: Einer, Zehner, Hunderter, Tausender usw.

Um den Wert der Zahl zu bestimmen, muss man diese einzelnen Produkte aus Ziffernwert und n-ter Potenz addieren. Diese Operation müssen Sie selbstverständlich nicht ausführen, denn ihr Wert ist bereits durch ihre dezimale Darstellungsform gegeben.

5.1 Natürliche und ganze Zahlen

Um den euklidischen Algorithmus und das Sieb des Eratosthenes zu verstehen, muss zunächst das Problem der Teilbarkeit näher untersucht werden. Die hierfür notwendigen Rechenoperationen können noch innerhalb der Menge der natürlichen Zahlen durchgeführt werden. Bei der Berechnung der Linearfaktoren u und v des erweiterten euklidischen Algorithmus können diese Faktoren negative Werte annehmen (Listing 5.7). Die Rechenoperationen müssen also innerhalb der Menge der ganzen Zahlen durchgeführt werden.

5.1.1 Teilbarkeit

Die Teilbarkeit ist eine mathematische Beziehung zwischen zwei natürlichen Zahlen. Eine natürliche Zahl ist durch eine andere natürliche Zahl teilbar, wenn sich bei der Division kein Rest ergibt. Wenn b ein Teiler von a ist, schreibt man abgekürzt: b | a.

Auch andere Formulierungen sind üblich:

b teilt a.
b misst a.
a ist ein Vielfaches von b.

Es gibt einfache Regeln, mit denen überprüft werden kann, ob eine Zahl durch die Zahlen von 2 bis 10 ohne Rest teilbar ist. Eine Zahl ist durch

2 teilbar, wenn ihre letzte Stelle eine 0 oder eine gerade Zahl ist.
3 teilbar, wenn ihre Quersumme durch 3 teilbar ist.
4 teilbar, wenn die letzten beiden Stellen durch 4 teilbar sind.
5 teilbar, wenn ihre letzte Stelle eine 0 oder 5 ist.
6 teilbar, wenn sie durch 2 und ihre Quersumme durch 3 teilbar ist.
7 teilbar: Hier gibt es keine einfache Regel!
8 teilbar, wenn die letzten drei Stellen durch 8 teilbar sind.
9 teilbar, wenn ihre Quersumme durch 9 teilbar ist.
10 teilbar, wenn die letzte Stelle eine 0 ist.

Gerade und ungerade Zahlen

Alle geraden Zahlen lassen sich ohne Rest durch 2 teilen. Trifft dies nicht zu, dann ist die Zahl ungerade. Ob eine Zahl n > 10 gerade oder ungerade ist, erkennt man an ihrer letzten Stelle. Wenn die letzte Ziffer einer ganzen Zahl sich durch 2 teilen lässt oder eine 0 ist, handelt es sich um eine gerade Zahl.

Listing 5.1 wertet die letzte Ziffer einer Zahl daraufhin aus, ob sie gerade oder ungerade ist. Diese Vorgehensweise ist nicht besonders elegant; sie dient dazu, die oben beschriebene Regel auszuprobieren. Mit der Modulo-Operation n%2 kann einfacher überprüft werden, ob eine Zahl gerade oder ungerade ist (siehe Aufgabe 1).

01  #01_gerade_ungerade.py
02  def gerade_ungerade(zahl):
03      strZahl=str(zahl)
04      letzteZiffer=strZahl[-1]
05      lz=int(letzteZiffer)
06      if (lz==0)or(lz==2)or(lz==4)or(lz==6)or(lz==8):
07          return "gerade Zahl"
08      else:
09          return "ungerade Zahl"
10  #Hauptprogramm
11  #z=1234
12  z=234563
13  print(z,"ist eine",gerade_ungerade(z))

Listing 5.1 Gerade oder ungerade Zahlen ermitteln

Ausgabe

234563 ist eine ungerade Zahl

Analyse

In Zeile 04 wird das letzte Zeichen der Stringvariablen strZahl ermittelt. Mit dem Index -1 kann man auf das letzte Element einer Liste zugreifen. Dieses Zeichen wird in Zeile 05 in eine numerische Variable lz vom Typ Integer umgewandelt.

In Zeile 06 erfolgt die Fallabfrage, ob die letzte Ziffer eine gerade Zahl ist. Wenn das der Fall ist, dann wird der String gerade Zahl zurückgegeben (Zeile 07). Wenn die letzte Ziffer keine gerade Zahl ist, wird die return-Anweisung in Zeile 09 ausgeführt.

Quersumme

Die Quersumme einer natürlichen Zahl ist die Summe ihrer Ziffernwerte. Mit Quersummen kann z. B. überprüft werden, ob eine Zahl durch 3 oder 9 teilbar ist. Einfache Prüfverfahren benutzen Quersummen, um zu überprüfen, ob ein Nachrichtenkanal eine Ziffernfolge fehlerfrei überträgt. Für die Zahl 123456789 beträgt die Quersumme 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45. Mit Listing 5.2 können Sie die Quersummen beliebiger natürlicher Zahlen berechnen:

01  #02_quersumme.py
02  #Division mit Rest
03  def quersumme1(z):
04      qs=0
05      while z!=0:
06          qs=qs+z%10
07          z=z//10
08      return qs
09  #typische Lösung mit Python
10  def quersumme2(z):
11      strZahl=str(z)
12      qs=0
13      for ziffer in strZahl:
14          qs=qs+int(ziffer)
15      return qs
16  #Hauptprogramm
17  zahl=123456789
18  #q=quersumme1(zahl)
19  q=quersumme2(zahl)
20  print("Die Quersumme von",zahl,"ist",q)

Listing 5.2 Berechnung von Quersummen

Ausgabe

Die Quersumme von 123456789 ist 45

Analyse

Die Quersumme der Zahl z soll berechnet werden. Dazu wird ihr Divisionsrest z%10 in Zeile 06 zu der Quersumme qs aufaddiert. In Zeile 07 erfolgt eine Ganzzahldivision z//10. Diese Division wird so lange ausgeführt, bis z ungleich 0 ist (Zeile 05). Die ist die klassische Lösung. Mit Python geht das eleganter.

In Zeile 11 wandelt die eingebaute Python-Funktion str(z) die Zahl z in einen String um. In Zeile 13 erfasst die Laufvariable ziffer alle Zeichen des Strings strZahl. In Zeile 14 wird das Zeichen ziffer in eine Ganzzahl umgewandelt und zur Summe qs aufaddiert.

5.1.2 Division mit Rest

Der folgende Konsolendialog zeigt eine Ganzzahldivision mit dem Operator //, eine Modulo-Division mit dem Operator % und eine Division mit der eingebauten Funktion divmod(17,5), die das Ergebnis beider Operationen als Tupel zurückgibt:

>>> 17//5
3
>>> 17%5
2
>>> divmod(17,5)
(3, 2)

Die Zahl 5 ist kein echter Teiler von 17. Wenn 17 durch 5 geteilt wird, ergibt sich ein Rest von 2. Abbildung 5.2 veranschaulicht diesen Sachverhalt.

Abbildung 5.2 Veranschaulichung der Division mit Rest

Die Zahl 5 ist in der Zahl 17 also dreimal enthalten. Wenn von der Zahl 17 die Zahl 5 fortlaufend subtrahiert wird, dann kann diese Operation dreimal durchgeführt werden, ohne dass das Ergebnis negativ wird. Es bleibt ein Rest von 2.

Für die Division mit dem Dividend a und dem Divisor b gilt allgemein:

In dem Beispiel »17 geteilt durch 5« ist a = 17, m = 3, b = 5 und r = 2. Der Quotient m ist eine nichtnegative ganze Zahl.

Für den Divisionsrest r gilt allgemein: 0 ⩽ r < b.

In der Schreibweise der modularen Arithmetik wird der Rest r mit dem Modul m als Division mit Rest berechnet:

Für alle und m > 0 wird geschrieben

wenn gilt: m teilt a – r bzw. m | a – r.

Exkurs: Kongruenz

Zwei ganze Zahlen a und b heißen kongruent modulo m, wenn die Division von a und b durch m den gleichen Rest r lässt. Im obigen Beispiel sind 2, 7, 12 und 17 alle kongruent, da bei Division durch 5 in allen Fällen der Rest 2 übrigbleibt.

Der folgende Konsolendialog zeigt, ob zwei Kongruenzen übereinstimmen:

>>> def kongruent(a,b,m):
    return a%m==b%m
 
>>> kongruent(12,17,5)
True
>>> kongruent(12,22,5)
True
>>> kongruent(27,22,5)
True

Rechenregeln für mod m:

Der folgende Konsolendialog demonstriert die Anwendung der Rechenregeln:

>>> a=11
>>> b=17
>>> m=5
>>> (a+b)%m
3
>>> ((a%m)+(b%m))%m
3
>>> (a-b)%m
4
>>> ((a%m)-(b%m))%m
4
>>> (a*b)%m
2
>>> ((a%m)*(b%m))%m
2

Mit Listing 5.3 soll die Division mit Rest veranschaulicht werden. Das Programm berechnet die Division mit Rest iterativ durch fortlaufende Subtraktion:

01  #03_modulo.py
02  def mod(a,b):
03      i=0
04      while a>=b:
05          a=a-b
06          i=i+1
07      return i,a
08  #Hauptprogramm
09  z1=17
10  z2=5
11  ganz,rest=mod(z1,z2)
12  print(z1,"geteilt durch",z2,"ergibt:",ganz,"Rest",rest)
13  print("Mit divmod berechnet:",divmod(z1,z2))

Listing 5.3 Division mit Rest

Ausgabe

17 geteilt durch 5 ergibt: 3 Rest 2
Mit divmod berechnet: (3, 2)

Analyse

In Zeile 05 wird von der Zahl a die Zahl b so lange subtrahiert, bis die Subtraktion nicht mehr aufgeht. Dieser Vorgang wird in Zeile 06 gezählt. Die Variable i repräsentiert das Ergebnis der Division. Übrig bleibt der Rest a. Beide Werte werden in Zeile 07 zurückgegeben.

Exkurs: Neunerprüfung

Mit der Neunerprüfung kann überprüft werden, ob das Produkt zweier Zahlen a und b das richtige Ergebnis liefert. Dazu müssen folgende Operationen ausgeführt werden:

Berechne das Produkt a ⋅ b.
Berechne die Quersummen Q(a), Q(b) und Q(a ⋅ b).
Berechne das Produkt der Quersummen Q(a) ⋅ Q(b).
Prüfe: Q(a) ⋅ Q(b) ≡ (a ⋅ b) (mod 9) [Ziegenbalg: 106].

Bei der Neunerprüfung handelt es sich nur um eine Plausibilitätsprüfung. Sie liefert nur eine notwendige und keine hinreichende Bedingung dafür, dass das Ergebnis auch korrekt ist.

5.1.3 Der euklidische Algorithmus

Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler (ggT) von zwei natürlichen Zahlen a und b. Er kann z. B. dafür verwendet werden, Brüche zu kürzen. Es gibt verschiedene Varianten des ggT-Algorithmus. Durch fortlaufendes Subtrahieren werden die beiden Zahlen a und b so lange voneinander subtrahiert, bis der ggT gefunden ist (Listing 5.5). Dies ist der Algorithmus, den Euklid ausführt [Scheid: 27]. Er wird als Subtraktionsform [Ziegenbalg: 44] oder Wechselwegnahme [Scheid: 28] bezeichnet. Eine zweite Variante berechnet den ggT mithilfe der Modulo-Operation (Listing 5.6). In der Fachliteratur werden beide Varianten als euklidischer Algorithmus bezeichnet.

Der größte gemeinsame Teiler

Den größten gemeinsamen Teiler von zwei natürlichen Zahlen können Sie ermitteln, indem Sie alle Teiler dieser Zahlen aufschreiben und die Teiler auswählen, die für beide Zahlen gleich sind und den größten Wert haben. Tabelle 5.1 zeigt die Teiler der Zahlen 78 und 174.

78	2	3	6	13	26	39
174	2	3	6	29	58	87

Tabelle 5.1 Die Teiler von zwei Zahlen

Aus Tabelle 5.1 können Sie jetzt ablesen, dass 6 der größte gemeinsame Teiler von 78 und 174 ist. Abgekürzt schreibt man: ggT(78,174) = 6.

Listing 5.4 berechnet die in Tabelle 5.1 aufgelisteten Teiler:

01  #04_teiler.py
02  def berechneTeiler(zahl):
03      teiler=[]
04      for t in range(2,zahl//2+1):
05          if zahl%t==0:
06              teiler.append(t)
07          else:
08              continue
09      return teiler
10  #Hauptprogramm
11  z1=78
12  z2=174
13  print("Teiler von",z1,"=",berechneTeiler(z1))
14  print("Teiler von",z2,"=",berechneTeiler(z2))

Listing 5.4 Teiler von zwei Zahlen berechnen

Ausgabe

Teiler von 78  = [2, 3, 6, 13, 26, 39]
Teiler von 174 = [2, 3, 6, 29, 58, 87]

Analyse

In Zeile 03 wird eine leere Liste teiler erzeugt. In Zeile 04 wird die for-Schleife von 2 bis zahl//2+1 ausgeführt. Wenn der Divisionsrest gleich 0 ist (Zeile 05), dann wird der Teiler t an die Liste teiler angehängt (Zeile 06). Ansonsten wird die Schleife weiter durchlaufen (Zeilen 07 und 08).

Den größten gemeinsamen Teiler durch Wechselwegnahme berechnen

Das Verfahren, alle Teiler von zwei Zahlen in eine Tabelle einzutragen, um dann aus den Einträgen den größten gemeinsamen Teiler zu ermitteln, ist sehr umständlich. Einfacher geht es mit dem euklidischen Algorithmus . Euklid von Alexandria (ca. 365–300 v. Chr.) hat ihn in seinem berühmten Buch Die Elemente, das noch bis in die zweite Hälfte des 19. Jahrhunderts als Mathematiklehrbuch genutzt wurde, als Prozess einer fortlaufenden Subtraktion beschrieben:

»Nimmt man abwechselnd immer das Kleinere vom Größeren weg, dann muß der Rest schließlich die vorhergehende Größe messen ...« [Zehntes Buch, §3].

Von der größeren Zahl wird die kleinere subtrahiert. Für die Subtraktion gilt:

Minuend – Subtrahend = Differenzwert

Von dem Ergebnis, also dem Differenzwert, wird dann wieder die kleinere Zahl subtrahiert. Diese Operation wird so lange fortgesetzt, bis die Teilung abgeschlossen ist. Wenn der Subtrahend größer als der Minuend ist, werden beide Zahlen vertauscht.

Am Beispiel der Zahlen 78 und 174 soll gezeigt werden, wie der euklidische Algorithmus funktioniert:

>>> 174-78
96
>>> 96-78
18
>>> 78-18
60
>>> 60-18
42
>>> 42-18
24
>>> 24-18
6
>>> 18-6
12
>>> 12-6
6

Der größte gemeinsame Teiler von 78 und 174 ist also, wie oben bereits ermittelt wurde, die Zahl 6.

Python verfügt über die eingebaute Funktion gcd(a,b) (greatest common divisor). Mit dem folgenden Konsolendialog wird das Ergebnis überprüft:

>>> from math import gcd
>>> gcd(78,174)
6

Wenn zwei Zahlen keinen gemeinsamen Teiler haben, dann ist der gemeinsame Teiler gleich 1: z. B. ggT(7,8) = 1. Für Primzahlen gilt grundsätzlich: ggT(prim₁, prim₂) = 1. Der nachfolgende Konsolendialog zeigt zwei Beispiele:

>>> gcd(7,8)
1
>>> gcd(17,19)
1

In Pseudocode übersetzt, lässt sich der euklidische Algorithmus wie folgt formulieren:

solange a ungleich b:
   Ausgabe a und b
   wenn a > b:
        a = a - b
   sonst:
        b = b - a

Listing 5.5 berechnet den größten gemeinsamen Teiler der Zahlen 78 und 174 durch Wechselwegnahme. Die einzelnen mathematischen Operationen werden mit ausgegeben.

01  #05_euklid.py
02  a=78
03  b=174
04  while a!=b:
05      if a>b:
06          print(a,"-",b,"=",a-b)
07          a=a-b
08      elif b>a:
09          print(b,"-",a,"=",b-a)
10          b=b-a

Listing 5.5 Der euklidische Algorithmus

Ausgabe

174 - 78 = 96
96 - 78 = 18
78 - 18 = 60
60 - 18 = 42
42 - 18 = 24
24 - 18 = 6
18 - 6 = 12
12 - 6 = 6

Analyse

Die while-Schleife (Zeilen 04 bis 10) wird so lange durchlaufen, wie a ungleich b ist. Wenn a größer b ist (Zeile 05), dann wird die Differenz a-b berechnet (Zeile 07). Ansonsten wird b-a berechnet (Zeile 10).

Den größten gemeinsamen Teiler mit dem Modulo-Operator berechnen

Das Verfahren der Wechselwegnahme ist aufwendig. Mithilfe der Modulo-Operation kann der größte gemeinsame Teiler wesentlich schneller berechnet werden. Es wird fortlaufend die Division mit Rest durchgeführt. Der Rest wird dann für die nächste Division verwendet. Diese Operation wird so lange wiederholt, bis die Division aufgeht. Es handelt sich also um ein rekursives Rechenverfahren.

Die praktische Umsetzung wird am Beispiel von ggT(78,174) gezeigt:

>>> 174%78
18
>>> 78%18
6
>>> 18%6
0

Ergebnis: ggT(78,174) = 6

Die Wechselwegnahme hat einen Aufwand von acht Operationen, die Division mit Rest benötigt dagegen nur drei Operationen.

In Listing 5.6 berechnen Python-Funktionen den größten gemeinsamen Teiler mit dem Modulo-Operator.

01  #06_ggT.py
02  #Division mit Rest
03  def ggT(a, b):
04      while b != 0:
05          a, b = b, a % b
06      return a
07  #Hauptprogramm
08  z1,z2=78,174
09  t=ggT(z1,z2)
10  print("Größter gemeinsamer Teiler von %i und %i ist %i" %(z1,z2,t))

Listing 5.6 Berechnung des größten gemeinsamen Teilers

Ausgabe

Größter gemeinsamer Teiler von 78 und 174 ist 6

Analyse

In Zeile 05 wird der Wert von b der Variablen a zugewiesen. Der Divisionsrest a%b wird der Variablen b zugewiesen. Dieser Vorgang wird so lange wiederholt, wie b ungleich 0 ist. Bei der Python-Funktion ggT() in Zeile 03 handelt es sich um eine typische Python-Lösung. Sie ist wesentlich kürzer als die Subtraktionsform.

5.1.4 Der erweiterte euklidische Algorithmus

Mit dem erweiterten euklidischen Algorithmus (EEA) kann man die Linearfaktoren u und v der Gleichung

berechnen. Diese Darstellung wird auch als Vielfachsummendarstellung von ggT(a,b) bezeichnet [Scheid: 30].

Der EEA berechnet für a und b mit den Startwerten

und mit der rekursiven Berechnungsvorschrift

die Linearfaktoren u und v. Für den Quotienten gilt: q = a_i div b_i, a_n ist der ggT.

[Quelle: https://hwlang.de/krypto/algo/euklid-erweitert.htm]

Listing 5.7 zeigt, wie der EEA implementiert werden kann. In der Zeile 13 können Sie andere Werte für a und b eingeben.

01  #07_erw_ggt.py
02  #ggT(a,b)=u*a+v*b
03  def erweitert_ggT(a,b):
04      u,v=1,0
05      s,t=0,1
06      while b!=0:
07          q=a//b
08          a, b = b, a-q*b
09          u, s = s, u-q*s
10          v, t = t, v-q*t
11      return u,v,a
12  #Berechnung und Ausgabe
13  a,b=99,78
14  print(erweitert_ggT(a,b))

Listing 5.7 Implementierung des erweiterten euklidischen Algorithmus

Ausgabe

(-11, 14, 3)

Analyse

In den Zeilen 04 und 05 stehen die Startwerte. In den Zeilen 06 bis 10 wird der Algorithmus ausgeführt. Auf der linken Seite des Zuweisungsoperators stehen die jeweils aktualisierten neuen Werte, z. B. u,s. Auf der rechten Seite vom Zuweisungsoperator stehen die Vorgänger (alte Werte). Der Variablen u wird s zugewiesen, und der Variablen s wird u-q*s zugewiesen. Das Ergebnis wird als Tupel (Zeile 11) zurückgegeben. Mit dem Konsolendialog

>>> -11*99+14*78
3

können Sie das Ergebnis überprüfen. Das Beispiel zeigt, dass die Linearfaktoren u und v auch negative Werte annehmen können. Für die Lösungsmenge gilt also u,v ∈ ℤ.

Für das RSA-Verfahren kann der geheime Schlüssel d mit dem EEA ggT(e,𝜑(n)) = 1 = d ⋅ e + k ⋅ 𝜑(n)) berechnet werden. Diese Operation wird in Abschnitt 5.1.6 benötigt.

Mit der SymPy-Methode gcdex() können Sie die Linearfaktoren einfacher berechnen:

>>> from sympy import gcdex
>>> gcdex(99,78)
(-11, 14, 3)

5.1.5 Primzahlen

Primzahlen sind das Fundament moderner Verschlüsselungsverfahren. Im Jahr 1977 entdeckten Ronald Rivest, Adi Shamir und Leonard Adleman ein Verschlüsselungsverfahren, in dem Primzahlen die entscheidende Funktion für eine sichere Verschlüsselung übernehmen.

Primzahl

Eine Primzahl ist eine natürliche Zahl größer 1, die nur durch 1 und durch sich selbst teilbar ist. Es gibt unendlich viele Primzahlen.

Schon im antiken Griechenland waren Primzahlen Gegenstand mathematischer Untersuchungen. Eratosthenes fand eine Methode, mit der Primzahlen bestimmt werden konnten. Alle Zahlen von 1 bis n werden in eine Tabelle eingetragen, und es wird geprüft, ob sie durch eine Zahl von 2 bis formula teilbar sind. Wenn das der Fall ist, wird diese Zahl gestrichen. Übrig bleiben die Primzahlen. Tabelle 5.2 zeigt die herausgesiebten Primzahlen.

	2	3	5	7
11		13		17	19
		23			29
31				37
41		43		47

Tabelle 5.2 Die Primzahlen von 1 bis 50

Zwischen den natürlichen Zahlen von 1 bis 50 gibt es 15 Primzahlen. Aus der Darstellung in Tabelle 5.2 geht deutlich hervor, dass die Primzahlen unregelmäßig verteilt sind. Es ist kein Muster erkennbar, folglich gibt es auch kein Bildungsgesetz, mit dem Primzahlen aus ihrem Vorgänger einfach ermittelt werden können.

Die Menge der Primzahlen von 2 bis 50 lautet also:

Die selbst erstellten Algorithmen können Sie mit den zahlentheoretischen Methoden von SymPy überprüfen. Tabelle 5.3 enthält eine Übersicht über Methoden, mit denen der Primzahltest und Primzahlsuchen durchgeführt werden können.

Methode	Beschreibung
`isprime(n)`	Überprüft, ob die Zahl `n` eine Primzahl ist.
`prime(n)`	Gibt die n-te Primzahl zurück. Die n-te Primzahl ist ungefähr `n*log(n)`.
`primefactors(z)`	Ermittelt die Primfaktoren der Zahl `z`.
`primepi(n)`	Ermittelt die Anzahl der Primzahlen von 2 bis `n`.
`sieve.primerange(n1,n2)`	Erzeugt eine Liste von Primzahlen, mit dem Algorithmus »Sieb des Eratosthenes«.
`totient(n)`	Berechnet die Anzahl der teilerfremden Zahlen von `n`.

Tabelle 5.3 SymPy-Methoden für Primzahlen

Naiver Primzahltest

Um zu prüfen, ob eine Zahl zahl eine Primzahl ist, kann man über die Menge aller potenziellen Teiler k von 2 bis zur nächsten natürlichen Zahl nach sqrt(zahl) iterieren und prüfen, ob man einen echten Teiler findet, d. h. ein k, bei dem nach der Modulo-Operation zahl%k kein Rest übrig bleibt. In diesem Fall wäre k ein Teiler von zahl und zahl damit keine Primzahl. Findet man kein solches k, dann wäre damit gezeigt, dass es sich bei zahl um eine Primzahl handelt.

In Listing 5.8 wird die Modulo-Operation (Zeile 06) innerhalb einer for-Schleife durchgeführt. Das Modul k durchläuft den Wertebereich von 2 bis sqrt(zahl). Dieser Algorithmus ist naiv, weil er unnötige Divisionen durchführt. Hat man beispielsweise bereits festgestellt, dass k nicht durch 2 teilbar ist, dann könnte man sich die Prüfung für k = 4, 6, 8, … und alle weiteren Vielfachen von 2 sparen.

01  #08_primtest_naiv.py
02  from math import sqrt,ceil
03  def istPrim(zahl):
04      kmax=ceil(sqrt(zahl))
05      for k in range(2,kmax):
06          if zahl%k==0:          #ohne Rest teilbar
07              return zahl, False #also keine Primzahl
08      return zahl, True #ist eine Primzahl
09  #Hauptprogramm
10  for z in [11,191,499,9091,333667,2**11-1]:
11      print(istPrim(z))

Listing 5.8 Naiver Primzahltest

Ausgabe

(11, True)
(191, True)
(499, True)
(9091, True)
(333667, True)
(2047, False)

Analyse

In Zeile 04 berechnet die eingebaute Python-Funktion ceil(sqrt(n)) die kleinste ganze Zahl kmax, die größer oder gleich sqrt(n) ist. Die Probedivisionen brauchen nur bis kmax, der nächsten natürlichen Zahl nach der Wurzel aus zahl, durchgeführt zu werden (Zeilen 04 und 05).

Die Laufvariable k ist der Divisor. Wenn sich die Zahl zahl ohne Rest durch k teilen lässt, ist zahl keine Primzahl, und die return-Anweisung in Zeile 07 wird ausgeführt.

Bleibt bei der Division immer ein Rest, wird nach dem letzten Schleifendurchlauf die return-Anweisung in Zeile 08 ausgeführt. Die Zahl zahl ist eine Primzahl.

Primzahltest mit SymPy

Bei der RSA-Verschlüsselung müssen zwei sehr große Primzahlen miteinander multipliziert werden. Diese Primzahlen können mit der Formel von Mersenne berechnet werden: M_n = 2ⁿ – 1. Mit den Exponenten n = {2, 3, 5, 7, 13, 17, 19, 31} erhält man die Mersenne-Primzahlen p = {3, 7, 31, 127, 8191, 131071, 524287, 2147483647}.

Da ein Computer 2er-Potenzen einfach berechnen kann, eignet sich die Mersenne-Formel besonders gut dazu, große Primzahlen zu finden. Die Formel liefert aber nicht für alle n eine Mersenne-Primzahl M_n. So sind z. B. die Zahlen M₁₁, M₂₃ M₂₉ und M₃₇ keine Primzahlen. Deshalb muss eine Zahl, die mit der Mersenne-Formel berechnet wurde, daraufhin überprüft werden, ob sie prim ist.

Der amerikanische Mathematiker Frank Nelson Cole hielt im Jahr 1903 einen »Vortrag« ohne Worte: Er rechnete, ohne ein Wort zu sprechen, an einer Tafel vor, dass die Mersenne-Zahl 2⁶⁷ – 1 in die beiden Faktoren 193.707.721 und 761.838.257.287 faktorisiert werden kann. Um auf dieses Ergebnis zu kommen, hatte er drei Jahre lang jedes Wochenende mit Rechnen zugebracht [Barth: 71]. SymPy erledigt diese Aufgabe in Bruchteilen einer Sekunde:

>>> primefactors(2**67-1)
[193707721, 761838257287]

In seinem Buch »Unglaubliche Zahlen« hat Ian Stewart [Stewart: 416] die Rekorde der Mersenne-Primzahlen aufgelistet. Sie können die Leistungsfähigkeit Ihres Computers testen, indem Sie in Zeile 03 andere Werte eintragen. Der Primzahltest wird mit der SymPy-Methode isprime(M) in Zeile 06 durchgeführt. Das Programm berechnet die Mersenne-Primzahl und ermittelt auch die Anzahl ihrer Stellen.

01  #09_primtest_sympy.py
02  from sympy import isprime
03  n=2281   #Robinson 1952
04  M=2**n-1 #Mersenne-Primzahl
05  print("Ist die Zahl\n",M,"\nmit",len(str(M)),"Stellen eine Primzahl?")
06  print(isprime(M))

Listing 5.9 Primzahltest mit SymPy

Ausgabe

Ist die Zahl
446087557183758429571151706402101809886208632412859901111991219963404685792820473369112545269003989026153245931124316702395758705693679364790903497461147071065254193353938124978226307947312410798874869040070279328428810311754844108094878252494866760969586998128982645877596028979171536962503068429617331702184750324583009171832104916050157628886606372145501702225925125224076829605427173573964812995250569412480720738476855293681666712844831190877620606786663862190240118570736831901886479225810414714078935386562497968178729127629594924411960961386713946279899275006954917139758796061223803393537381034666494402951052059047968693255388647930440925104186817009640171764133172418132836351 
mit 687 Stellen eine Primzahl?
True

Analyse

Wie gesagt: Sie können das Programm benutzen, um die Leistungsfähigkeit Ihres Computers zu beurteilen. Mein Rechner mit einem Apple-M1-Prozessor kann gerade noch überprüfen, ob M₂₂₈₁ eine Mersenne-Primzahl ist (Zeile 03). Das gelang schon Raphael Robinson (1911–1995) im Jahr 1952 mit einem Röhrencomputer , dem SWAC (Standards Western Automatic Computer).

In Zeile 05 ermittelt die eingebaute Python-Funktion len() die Anzahl der Stellen. In Zeile 06 überprüft die SymPy-Methode isprime(M), ob es sich bei M um eine Primzahl handelt.

Mit der Tastenkombination (Strg)+(C) können Sie die Ausführung des Programms in der Kommandozeile jederzeit abbrechen, falls die Berechnung zu lange dauert.

Primzahlen finden

Zahlentheoretiker gingen der Frage nach, wie viele Primzahlen in einem bestimmten Intervall vorkommen: Wie viele Primzahlen gibt es in dem Intervall von 0 bis 100.000 oder in dem Intervall von 100.000 und 200.000 usw.? Nimmt die Dichte der Primzahlen mit der Größe der Intervalle ab? Oder bleibt sie eventuell konstant? Diese Fragen beantwortet die Darstellung der Primzahlverteilung in Tabelle 5.4.

Listing 5.10 ermittelt Primzahlen und deren Anzahl n für ein vorgegebenes Intervall mit einer unteren Schranke us und einer oberen Schranke os. Die Intervallgrenzen können Sie in den Zeilen 19 und 20 ändern. Der selbst erstellte Algorithmus arbeitet mit dem naiven Primzahltest. Zur Kontrolle wird das Ergebnis mit der SymPy-Methode primerange(u,o) überprüft.

01  #10_primgenerator.py
02  from sympy import sqrt, primerange 
03  def primzahl(us,os):
04      primZahlen=[]
05      istPrim=False
06      n=0
07      for zahl in range(us,os):
08          istPrim=True
09          kmax=int(sqrt(zahl))+1 #größter Teiler
10          for k in range(2,kmax): 
11              if zahl%k==0:     #ohne Rest teilbar
12                  istPrim=False #also keine Primzahl
13                  break
14          if istPrim:
15              n=n+1 #zähle Primzahlen
16              primZahlen.append(zahl)
17      return primZahlen,n
18  #Hauptprogramm
19  u=2
20  o=50
21  pz=primzahl(u,o)
22  pz_sympy=[i for i in primerange(u,o)]
23  print(pz)
24  print("",pz_sympy,len(pz_sympy))

Listing 5.10 Primzahlengenerator

Ausgabe

([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47], 15)
 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 15

Analyse

Die selbst erstellte Python-Funktion primzahl(us,os) besteht aus zwei ineinander verschachtelten for-Schleifen (Zeilen 07 bis 13). In der äußeren Schleife werden die Zahlen zahl zwischen us und os erzeugt. In der inneren Schleife wird überprüft, ob die Zahl zahl ohne Rest teilbar ist (Zeile 11). Ist das der Fall, dann ist sie keine Primzahl (Zeile 12), und der Schleifendurchlauf wird mit break unterbrochen (Zeile 13).

Wenn die boolesche Variable istPrim den Wert True hat (Zeile 14), wird der Zähler n um 1 erhöht, und die gefundene Primzahl wird in Zeile 16 an die Liste primZahlen angehängt. Zurückgegeben werden die Primzahlen primZahlen und die Anzahl der Primzahlen n in Zeile 17.

Zur Kontrolle ermittelt in Zeile 22 die SymPy-Methode primerange(u,o) die Primzahlen in dem Intervall zwischen u und o.

Das Sieb des Eratosthenes

Der Algorithmus von Eratosthenes wurde anhand von Tabelle 5.2 beschrieben. In Listing 5.11 wird diese Tabelle durch die Python-Liste gestrichen[n] erzeugt. Diese Liste wird mit dem booleschen Wert False initialisiert (Zeile 08). Wenn eine Zahl aus dieser Liste einen Teiler hat, dann wird an dieser Stelle der Wert auf True gesetzt und damit »herausgesiebt«. Anschließend werden aus dieser Liste die nicht gestrichenen Werte ermittelt und ausgegeben (Zeilen 14 bis 16).

01  #11_eratosthenes.py
02  from math import sqrt,ceil
03 
04  def sieb(n):
05      '''Sieb des Eratosthenes'''
06      kmax=ceil(sqrt(n))
07      prim=[]
08      gestrichen=[False]*n
09      for i in range(2,kmax):
10          if not gestrichen[i]:
11              for j in range(i**2,n,i):
12                  gestrichen[j]=True
13                  #print(i,j)
14      for i in range(2,n):
15          if not gestrichen[i]:
16              prim.append(i)
17      return prim
18  #Hauptprogramm
19  N=100
20  print(sieb(N))

Listing 5.11 Das Sieb des Eratosthenes

Ausgabe

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Analyse

Die leere Liste prim hat die Aufgabe, die herausgesiebten Primzahlen aufzunehmen (Zeile 07). In Zeile 08 wird die mit n booleschen Werten als False initialisierte Liste gestrichen erzeugt.

Die äußere for-Schleife iteriert die Teiler von 2 bis formula . Wenn an der Position i noch keine Zahl gestrichen wurde, wird die innere for-Schleife in Zeile 11 ausgeführt. Da alle kleineren Vielfachen bereits gestrichen wurden, reicht es aus, bei jedem neuen Schleifendurchlauf der inneren Schleife die Iteration mit dem Quadrat von i zu be ginnen. Bei jedem neuen Schleifendurchlauf der inneren Schleife erhöht sich auch die Schrittweite. In Zeile 12 wird an der Position j der boolesche Wert von gestrichen auf True gesetzt. Das heißt, die Zahl, die an dieser Stelle steht, ist keine Primzahl und muss deshalb gestrichen werden.

In den Zeilen 14 bis 16 werden alle Zahlen, die nicht gestrichen wurden (Zeile 15) gesammelt und an die Liste prim angehängt (Zeile 16). In Zeile 17 werden die herausgesiebten Primzahlen als Liste zurückgegeben.

Um den Ablauf besser nachvollziehbar zu machen, können Sie sich in der innersten for-Schleife in Zeile 13 die Werte von i und j per print(i,j) ausgeben lassen.

Verteilung der Primzahlen

Wie häufig kommen Primzahlen innerhalb eines bestimmten Intervalls vor? Diese Frage stellten sich schon der 15-jährige Carl Friedrich Gauß 1793 und Adrien-Marie Legendre 1798. Sie soll zunächst empirisch mithilfe des Primzahlgenerators aus Listing 5.10 beantwortet werden.

Tabelle 5.4 zeigt die Verteilung der Primzahlen für die ersten Hunderttausender-Intervalle.

Intervall	Anzahl der Primzahlen in dem Intervall
0 – 100.000	9.592
100.000 – 200.000	8.392
200.000 – 300.000	8.013
400.000 – 500.000	7.863
500.000 – 600.000	7.560
600.000 – 700.000	7.445
700.000 – 800.000	7.408
800.000 – 900.000	7.323
900.000 – 1.000.000	7.224

Tabelle 5.4 Anzahl der Primzahlen in den ersten »Hunderttausender-Intervallen«

Mit zunehmender Größe der Intervalle scheint die Dichte der Primzahlen leicht abzunehmen.

Gauß fand 1793 eine Formel, die den Zusammenhang zwischen der Anzahl der Primzahlen π(n) und dem natürlichen Logarithmus von n näherungsweise beschreibt:

Anmerkung: Es besteht kein logischer oder inhaltlicher Zusammenhang zwischen der Notation π(n) und der Kreiszahl π. Die Notation π(n) hat sich historisch durchgesetzt.

Wenn wir die Formel von Gauß für n = 10⁵ in einem Konsolendialog anwenden, erhalten wir für π(10⁵) einen Wert von etwa 8.686 Primzahlen:

>>> from math import log
>>> n=100000
>>> n/log(n)
8685.889638065037

Laut Tabelle 5.4 kommen in dem Intervall von 0 bis 100.000 genau 9.592 Primzahlen vor. Die Formel von Gauß erlaubt also nur eine grobe Abschätzung.

Abbildung 5.3 zeigt die Primzahlverteilung in dem Intervall von 10² bis 10⁹.

Verteilung der Primzahlen von 102 bis 109

Abbildung 5.3 Verteilung der Primzahlen von 10² bis 10⁹

Aus dem Funktionsgraphen in Abbildung 5.3 kann man ablesen, dass bis zu der Zahl n = 10⁹ etwa 5 ⋅ 10⁷ Primzahlen vorkommen.

Die SymPy-Methode primepi(n) ermittelt die Anzahl der Primzahlen von 2 bis n. Mit dem folgenden Konsolendialog kann der Wert für π(10⁹) ≈ 5 ⋅ 10⁷ bestätigt werden:

>>> from sympy import primepi
>>> primepi(1000000000)
50847534

Primfaktorzerlegung

Jede natürliche Zahl kann als Produkt aus anderen Zahlen dargestellt werden. Abbildung 5.4 zeigt exemplarisch, wie die Zahl 210 in ihre Faktoren zerlegt werden kann.

Abbildung 5.4 Primfaktorzerlegung

Das Produkt 21 ⋅ 10 kann weiter zerlegt werden in 3 ⋅ 7 und 2 ⋅ 5. Die Zerlegung wird so lange fortgesetzt, bis nur noch Primzahlen als Faktoren vorkommen. Als Formel geschrieben, lautet die Berechnungsvorschrift:

Diese Berechnungsvorschrift wird als Hauptsatz der elementaren Zahlentheorie bezeichnet.

Hauptsatz der elementaren Zahlentheorie

Jede ganze Zahl lässt sich eindeutig als Faktoren aus Primzahlen darstellen. Bis auf die Reihenfolge der Faktoren ist diese Darstellung eindeutig.

Bisher wurde noch kein effizienter Faktorisierungsalgorithmus gefunden. Diese Einschätzung ist wichtig, weil die Sicherheit des RSA-Verschlüsselungsverfahrens darauf beruht, dass ein Produkt aus zwei sehr großen Primzahlen nicht in akzeptabler Zeit in deren Primfaktoren zerlegt werden kann. Es ist zwar sehr leicht zu prüfen, dass eine Zahl das Produkt zweier gegebener Primzahlen ist, aber umgekehrt deutlich aufwendiger, die Zahl in ihre Primfaktoren zu zerlegen, wenn man diese nicht kennt.

Die erste Implementierung verwendet den Algorithmus aus der Algorithmensammlung zur Zahlentheorie von Wikipedia:

https://de.wikibooks.org/wiki/Algorithmensammlung:_Zahlentheorie:_Primfaktorisierung

Listing 5.12 überprüft mit dem Modulo-Operator % bis zur formula , ob die Zahl n einen Teiler t hat. Wenn das der Fall ist, dann wird dieser Teiler zu einer Liste f[] hinzugefügt. Dieser Prozess wird so lange fortgesetzt, bis alle Primfaktoren gefunden wurden. Das Ergebnis wird mit der SymPy-Methode primefactors(n) überprüft.

01  #12_primfaktoren1.py
02  from sympy import primefactors
03  def primfaktoren(n):
04      f=[]
05      t=2
06      while t**2<=n:
07          if n%t==0:
08              f.append(t)
09              n=n//t
10          else:
11              t=t+1
12      f.append(n)
13      return f
14 
15  z=1234566789
16  print("Primfaktoren von",z," sind:")
17  print(primfaktoren(z))
18  print(primefactors(z),"SymPy")

Listing 5.12 Einfacher Algorithmus für die Primfaktorzerlegung

Ausgabe

Primfaktoren von 1234566789  sind:
[3, 53, 151, 51421]
[3, 53, 151, 51421] SymPy

Analyse

In die leere Liste f sollen alle Primfaktoren gespeichert werden (Zeile 04). Der Teiler t wird mit 2 initialisiert (Zeile 05).

Die Iteration beginnt mit dem Quadrat des Teilers t**2 und endet bei n. Wenn sich n durch t teilen lässt, liegt ein Faktor vor (Zeile 07), und t wird an die Liste f angehängt. In Zeile 09 erfolgt die Ganzzahldivision n=n//t. Das heißt, bei jedem neuen Schleifendurchlauf wird der Wert von n reduziert. Wenn sich n nicht teilen lässt, wird der Wert des Teilers t um 1 erhöht (Zeile 11).

In Zeile 12 wird der letzte Wert von n noch an die Liste f angehängt. Die Primfaktoren werden als Liste zurückgegeben (Zeile 13). Wenn Sie das Programm mit sehr großen Zahlen testen, werden Sie feststellen, dass Sie mit Ihrem Computer diese Zahlen nicht mehr in ihre Primfaktoren zerlegen können. Selbst die leistungsstärksten Computer sind nicht in der Lage, sehr große Zahlen in einer noch akzeptablen Zeit in ihre Primfaktoren zu zerlegen. Darauf beruht die Sicherheit des RSA-Verschlüsselungsverfahrens (siehe Abschnitt 5.1.6).

Verbesserte Version

Die zweite, verbesserte Version (in Listing 5.13) stammt ebenfalls aus der oben zitierten Wikipedia-Quelle. Sie verwendet die Python-Funktion chain() aus dem Modul itertools. Mit dieser Funktion wird ein Iterator erzeugt. Ein Iterator ist ein Zeiger, der die Elemente einer Liste durchläuft, bis alle Elemente erfasst wurden. Die Funktion chain() entspricht in etwa dem Konstrukt aus zwei verschachtelten for-Schleifen:

def chain(iterables):
    #chain('ABC', 'DEF') --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

Die Anweisung yield gibt alle erfassten Elemente zurück.

Die Funktion chain() wird verwendet, um aufeinanderfolgende Sequenzen als eine einzelne Sequenz zu verarbeiten.

Das Ergebnis wird wieder mit der SymPy-Methode primefactors(n) überprüft.

01  #13_primfaktoren2.py
02  from itertools import chain
03  from sympy import primefactors
04 
05  def primfaktoren(n):
06      f = [] 
07      for i in chain([2], range(3, n//2+1, 2)):
08          while n % i == 0:
09              f.append(i)
10              n = n // i 
11          if i > n: 
12              break
13      return f
14 
15  z=1234566789
16  print("Primfaktoren von",z," sind:")
17  print(primfaktoren(z))
18  print(primefactors(z),"SymPy")

Listing 5.13 Primfaktorzerlegung mit »chain«

Ausgabe

Primfaktoren von 1234566789  sind:
[3, 53, 151, 51421]
[3, 53, 151, 51421] SymPy

Analyse

Die Anzahl der Iterationen in der äußeren for-Schleife wird bei jedem neuen Schleifendurchlauf halbiert (Zeile 07).

Die innere while-Schleife überprüft die Teilbarkeit der Zahl n (Zeile 08). Wenn sich n ohne Rest durch i teilen lässt, wird i an die Liste f angehängt. In Zeile 10 erfolgt die Verkleinerung von n durch eine Ganzzahldivision n=n//i. Wenn i größer n ist, wird die while-Schleife abgebrochen.

5.1.6 RSA-Verschlüsselung

Die RSA-Verschlüsselung ist ein asymmetrisches Verschlüsselungsverfahren. Es wurde 1977 von Ronald Rivest, Adi Shamir und Leonard Adleman erfunden. Dieses Verfahren umgeht das Problem des Schlüsseltausches der symmetrischen Verfahren. Bei den symmetrischen Verfahren muss der Schlüssel vom Sender A zum Empfänger B transportiert werden. Da Übertragungswege wie Bote, Post und Internet prinzipiell unsicher sind, sind symmetrische Verschlüsselungsverfahren leicht angreifbar und deshalb eigentlich nicht praxistauglich. Wenn ein Angreifer das Schlüsselwort in Erfahrung bringt, kann er den Geheimtext leicht entschlüsseln. Das Problem der Schlüsselübertragung lässt sich mit einem asymmetrischen Verfahren leicht umgehen. Der Empfänger des Geheimtextes generiert drei Schlüssel: zwei öffentliche Schlüssel e und n sowie einen geheimen Schlüssel d. Die öffentlichen Schlüssel ver öffentlicht er z. B. auf seiner Webseite. Der Sender A verschlüsselt seinen Text mit den öffentlichen Schlüsseln e und n. Der Empfänger B entschlüsselt dann den Geheimtext mit seinem privaten Schlüssel d und dem öffentlichen Schlüssel n. Abbildung 5.5 veranschaulicht diesen Prozess.

Abbildung 5.5 Das Prinzip der asymmetrischen Verschlüsselung

Entscheidend für die Sicherheit der asymmetrischen Verfahren ist, dass kein Schlüsseltausch zwischen A und B stattfindet. Es gibt aber andere Angriffsmöglichkeiten, die weiter unten noch diskutiert werden.

Der Sender A verschlüsselt die Nachricht (Klartext ) m (m steht für message) mit den öffentlichen Schlüsseln e (e steht für encrypt) und n:

Der Einfachheit halber nehmen wir zunächst an, dass es sich bei der zu verschlüsselnden Nachricht m nur um eine natürliche Zahl handelt. Es ist wesentlich komplizierter, Text zu verschlüsseln. In der Praxis wird dabei nur der Schlüssel selbst asymmetrisch verschlüsselt, der dann genutzt wird, um den Text symmetrisch zu verschlüsseln.

Der Empfänger B entschlüsselt den Geheimtext c mit dem privaten Schlüssel d (d steht für decrypt) und dem öffentlichen Schlüssel n:

Die Zahl n wird als Modul bezeichnet. Es ist das Produkt aus zwei sehr großen Primzahlen p und q:

Die Gleichungen für die Verschlüsselung und Entschlüsselung werfen die Fragen auf, warum das RSA-Verfahren überhaupt funktioniert und wie die Schlüssel e und d be rechnet werden. Dazu müssen wir die eulersche φ-Funktion φ(n) und den Satz von Euler näher untersuchen, denn die RSA-Verschlüsselung ist eine direkte Anwendung des Satzes von Euler [Beutelspacher2002: 101]. Die eulersche φ-Funktion gibt die Anzahl der teilerfremden natürlichen Zahlen von n an. Für zwei Primzahlen gilt:

Der Satz von Euler lautet für ggT(m,n) = 1:

Ein Beispiel soll diese mathematische Aussage verdeutlichen:

Die gleiche Operation mit Sympy ergibt:

>>> from sympy import totient
>>> 5**totient(6)%6
1

Wenn man eine natürliche Zahl m mit φ(n) potenziert und durch n dividiert, dann erhält man immer den Rest 1.

Beide Seiten der Gleichung werden jetzt mit m multipliziert:

und man erhält:

Allgemein gilt für jede natürliche Zahl k:

Die Zahl m muss kleiner n sein und darf kein Teiler von n sein. Diese Bedingungen sind in der Praxis immer erfüllt.

Die entscheidende Idee des RSA-Verfahrens besteht darin, den Exponenten durch das Produkt aus öffentlichem Schlüssel e und geheimem Schlüssel d zu ersetzen:

Der öffentliche Schlüssel e ist frei wählbar. Er muss größer 1 und kleiner φ(n) sein. Außerdem muss er teilerfremd zu φ(n) sein. Es gilt also:

1 < e < φ(n) und ggT(e, φ(n)) = 1

Für den privaten Schlüssel d gilt die Bedingung:

Er wird entweder mit dem erweiterten euklidischen Algorithmus (Listing 5.7) oder mit der modularen Inversen berechnet.

Wenn man die Gleichung für die Verschlüsselung c = m^e mod n in die Gleichung für die Entschlüsselung m = c^d mod n einsetzt, erhält man wieder die ursprüngliche Nachricht:

Listing 5.14 berechnet mit einem naiven Algorithmus (Zeilen 04 bis 12) den privaten Schlüssel d. In Zeile 15 ermittelt die SymPy-Methode prime() die fünfzigste und sechzigste Primzahl. Zur Kontrolle wird d mit den Resultaten des erweiterten euklidischen Algorithmus gcdex(e,phi) und der modularen Inversen mod_inverse(e,phi) (Zeile 19 und 20) des Moduls SymPy verglichen.

01  #14_d_berechnen.py
02  from sympy import prime,gcdex,mod_inverse
03  #geheimen Schlüssel berechnen
04  def geheimerSchluessel(e,phi):
05      gefunden = False
06      d = 1
07      while d <= phi and not gefunden:
08          if (e*d) % phi == 1:
09              gefunden = True
10          else:
11              d = d + 1
12      return d
13  #Hauptprogramm
14  e=47
15  p,q=prime(50),prime(60)
16  phi=(p-1)*(q-1) 
17  print("e =",e,", phi =",phi)
18  print("d =",geheimerSchluessel(e,phi))
19  print("d =",gcdex(e,phi)[0])
20  print("d =",mod_inverse(e,phi))

Listing 5.14 Berechnung des privaten Schlüssels

Ausgabe

e = 47 , phi = 63840
d = 13583
d = 13583
d = 13583

Das RSA-Verfahren können Sie mit dem folgenden Algorithmus implementieren:

Empfänger B berechnet die öffentlichen und den privaten Schlüssel

bestimme zwei sehr große Primzahlen p und q
berechne das Modul n: n = p*q
berechne φ(n): phi=(p-1)*(q-1)
bestimme e mit 1 < e < phi und ggT(e,phi)=1
berechne d aus e und phi: d = mod_inverse(e,phi)
veröffentliche e und n

Sender A verschlüsselt und sendet die Nachricht m an Empfänger B

c=m^e mod n

Empfänger B empfängt und entschlüsselt die verschlüsselte Nachricht c

m=c^d mod n

Mit Listing 5.15 können Sie das RSA-Verfahren testen. Weisen Sie in Zeile 04 den Variablen p und q verschiedene Primzahlen zu. Probieren Sie auch aus, was passiert, wenn keine Primzahlen zugewiesen werden. In Zeile 07 können Sie das Programm mit verschiedenen öffentlichen Schlüsseln e testen.

01  #15_rsa1.py
02  from sympy import mod_inverse,igcd
03  #Empfänger B
04  p,q=53,97            #1.Schritt: zwei Primzahlen bestimmen
05  n=p*q                #2.Schritt: Modul berechnen
06  phi=(p-1)*(q-1)      #3.Schritt: eulersche Funktion berechnen
07  e=101                #4.Schritt: öffentlichen Schlüssel wählen
08  d=mod_inverse(e,phi) #5.Schritt: geheimen Schlüssel berechnen
09  #Sender A
10  m=2525   #Nachricht
11  c=m**e%n #verschlüsseln
12  #Empfänger B
13  m=c**d%n #entschlüsseln
14  #Ausgaben
15  print("öffentliche Schlüssel e =",e,", n =",n)
16  print("phi =",phi)
17  print("privater Schlüssel d =",d)
18  print("Nachricht:",m)
19  print("verschlüsselte Nachricht:",c)
20  print("entschlüsselte Nachricht:",m)
21  print("ggT(m,n) =",igcd(m,n))

Listing 5.15 Test des RSA-Verfahrens

Ausgabe

öffentliche Schlüssel e = 101 , n = 5141
phi = 4992
privater Schlüssel d = 2669
Nachricht: 2525
verschlüsselte Nachricht: 1019
entschlüsselte Nachricht: 2525
ggT(m,n) = 1

Analyse

In Zeile 11 findet die Verschlüsselung der Nachricht m mit den öffentlichen Schlüsseln e und n statt. In Zeile 13 wird diese Nachricht mit dem geheimen Schlüssel d und dem öffentlichen Schlüssel n zu der Nachricht m entschlüsselt. Die Ausgabe in Zeile 20 bestätigt, dass das RSA-Verfahren für die vorgegebenen Daten funktioniert.

Testen Sie das Programm mit unterschiedlichen Nachrichten, z. B. mit m=53 und 97 (Zeile 10) und mit den Anweisungen:

print((m**e%n)**d%n)
print(m**(e*d)%n)

Texte verschlüsseln

Die bisher entwickelten Programme sollten zeigen, wie das RSA-Verfahren prinzipiell funktioniert. Wegen des hohen Rechenaufwands wird es in der Praxis nicht für die Verschlüsselung von längeren Texten verwendet. Stattdessen wird nur der geheime Schlüssel d mit dem RSA-Verfahren verschlüsselt. Die Verschlüsselung des Geheimtextes erfolgt mit symmetrischen Verfahren.

Ein praxisnahes Beispiel ist die Übertragung einer Kreditkartennummer bei Interneteinkäufen. Die in Zeile 16 von Listing 5.16 eingetragene Zeichenkette soll mit dem RSA-Verfahren verschlüsselt werden. In der Zeile 06 ermittelt die SymPy-Methode prime() die fünfzigste und sechzigste Primzahl. Das Programm berechnet den öffentlichen Schlüssel n und den geheimen Schlüssel d in einer separaten Python-Funktion (Zeilen 04 bis 12). Der geheime Schlüssel wird in eine Datei gespeichert (Zeilen 09 bis 11).

01  #16_rsa2.py
02  from sympy import prime, mod_inverse
03  #Empfänger B: Schlüssel erzeugen
04  def schluessel(): 
05      e=47 
06      p,q=prime(50),prime(60) #Primzahlen erzeugen
07      phi=(p-1)*(q-1)         #eulersche phi-Funktion
08      d=mod_inverse(e,phi)    #geheimer Schlüssel, decrypt
09      txtD=open('schluessel.txt','w')#geheimen Schlüssel speichern
10      txtD.write(str(d))
11      txtD.close()
12      n=p*q
13      return e,n #öffentliche Schlüssel
14  #Sender A: Nachricht verschlüsseln
15  def verschluesseln():
16      m='5234.1562.3398.6976' #Nachricht
17      e,n=schluessel()
18      c = [(ord(i)**e)%n for i in m]
19      return c
20  #Empfänger B: Nachricht entschlüsseln
21  def entschluesseln():
22      c=verschluesseln()
23      n=schluessel()[1]
24      txtD=open('schluessel.txt','r').read()
25      d=int(txtD)
26      mi = [(c[i]**d)%n for i in range(len(c))]
27      m=''
28      for i in range(len(mi)):
29          m=m+chr(mi[i])
30      return m
31  #Hauptprogramm
32  print("verschlüsselte Nachricht\n",verschluesseln())
33  print("entschlüsselte Nachricht\n",entschluesseln())

Listing 5.16 Texte mit dem RSA-Verfahren verschlüsseln und entschlüsseln

Ausgabe

verschlüsselte Nachricht
[62048, 51415, 40477, 51517, 28018, 14178, 62048, 49661, 51415, 28018, 40477, 40477, 60899, 20939, 28018, 49661, 60899, 54490, 49661]
entschlüsselte Nachricht
5234.1562.3398.6976

Analyse

In Zeile 04 berechnet die Funktion schluessel() den privaten Schlüssel d (Zeile 08) und den öffentlichen Schlüssel n (Zeile 12). Der öffentliche Schlüssel e (Zeile 05) wird vorgegeben. Er muss teilerfremd zu φ(n) sein: ggT(e,φ(n)) = 1. In Zeile 08 berechnet die SymPy-Methode mod_inverse(e,phi) den geheimen Schlüssel d. Er wird in die Datei schluessel.txt gespeichert (Zeilen 09 bis 11).

Die Funktion verschluesseln() in Zeile 15 verschlüsselt die Kreditkartennummer. Da die Kreditkartennummer als String gegeben ist (Zeile 16), wird sie in Zeile 18 mit der eingebauten Python-Funktion ord(i) in eine Liste aus Ganzzahlen umgewandelt. Die verschlüsselte Nachricht ist in dem Objekt c gespeichert.

In Zeile 21 entschlüsselt die Funktion entschluesseln() die verschlüsselte Nachricht c. Die verschlüsselte Nachricht besteht aus einer Liste mit ganzen Zahlen. In Zeile 24 liest die Python-Funktion open('schluessel.txt','r').read() den geheimen Schlüssel d aus der Datei schluessel.txt und speichert ihn als String-Objekt in die Variable txtD. Dieses Objekt muss in eine Integer-Variable d umgewandelt werden (Zeile 25).

In Zeile 26 werden die Elemente der verschlüsselten Nachricht c[i] in einer Listenabstraktion elementweise entschlüsselt. Das Ergebnis wird in das Objekt mi gespeichert. In den Zeilen 28 und 29 wird das Objekt mi in eine Zeichenkette m (engl. message) umgewandelt.

Der Funktionsaufruf in Zeile 33 gibt die ursprüngliche Nachricht aus.

Angriffsmöglichkeiten

Wenn man in der Lage wäre, die Primzahlen p und q aus dem RSA-Modul n = p ⋅ q durch Faktorisierung zu ermitteln, dann kann der geheime Schlüssel d mit der eulerschen φ-Funktion φ(n)

berechnet werden.

Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé und Paul Zimmermann konnten am 28. Februar 2020 ein RSA-Modul mit 250 Dezimalstellen faktorisieren. Das ist der aktuelle Rekord.

Das Bundesamt für Sicherheit in der Informationstechnik (BSI) empfiehlt (Stand 2023) ein RSA-Modul n ≥ 3000 Bits (904 Dezimalstellen).

Da aber aktuell kein effektiver Algorithmus bekannt ist, mit dem es gelänge, das Modul n in akzeptabler Zeit in seine Faktoren zu zerlegen, bleibt das RSA-Verschlüsselungsverfahren vor Hacker-Angriffen (noch) sicher.

Eine andere Angriffsmöglichkeit besteht darin, aus der Entschlüsselungsformel

den geheimen Schlüssel d mit dem diskreten Logarithmus zu berechnen. Auch das ist bisher noch nicht gelungen.

Hinweis

Auch wenn Sie nun die Grundlagen hinter der RSA-Verschlüsselung kennen: Verwenden Sie in der Praxis niemals selbst erstellte Programme für die Verschlüsselung Ihrer geheimen Botschaften! Diese lassen sich von erfahrenen Hackern fast immer leicht knacken, denn es ist eine große Kunst, einen Verschlüsselungsalgorithmus richtig zu implementieren. Benutzen Sie daher immer professionelle Verschlüsselungsprogramme, deren Quellcode offen liegt und die von einer großen Community gepflegt werden! Der hier vorgestellte RSA-Algorithmus sollte nur die prinzipielle Funktionsweise erklären.