Haben Sie Anregungen, Statements oder Kommentare? Dann schreiben Sie an [redaktion@linux-magazin.de]. Die Redaktion behält es sich vor, die Zuschriften und Leserbriefe zu kürzen. Sie veröffentlicht alle Beiträge mit Namen, sofern der Autor nicht ausdrücklich Anonymität wünscht.

Zu kleine Primzahlen

09/08, S. 33: Auf Seite 33 im Artikel “Computer, bitte kürzen” muss es heißen »p1:next_prime(377220)«. Dann stimmt auch die Angabe, dass »p1« etwa 500 Stellen hat. Allerdings sind Primzahlen der Form »next_prime(ab)« (mit kleinen ganzen Zahlen a, b) für das RSA-Verfahren nicht geeignet.

Zum einen gibt es grob geschätzt nur jeweils 256 Möglichkeiten für a und b. Damit liegt die Entropie nur bei 16 Bit und damit viel zu niedrig. Was eine niedrige Entropie unter Umständen anrichtet, konnte man erst vor Kurzem beim Debian-SSL-Debakel erleben.

Zum anderen lässt sich RSA brechen, wenn die Primzahlen die Form ab+c mit kleinen a, b und c haben. Die dazu nötige Mathematik ist komplizierter und sprengt den Rahmen eines Leserbriefs. Ich habe unter [http://cage.ugent.be/~klein/RSA.html] ein PDF-Dokument zur Verfügung gestellt, das den Angriff ausführlicher beschreibt.

Die in dem Artikel angegebene Zahl hat die folgenden Faktoren: (7*53)212 +8883838837776377363653637188 und (7*53)221 – 8883838837377363653636274. Die zur Faktorisierung benötigte Rechenzeit liegt unter einer Sekunde.

Andreas Klein, per Mail

Python, die Erste

10/08, S. 30: Das Problem der Python-Lösung ist die Funktion »nodups()«, die einfach zu langsam ist: Sie überprüft wiederholt, ob ein Element in einer Liste vorhanden ist. Solche Checks sind einfach sehr langsam. Ich habe deshalb eine Version geschrieben (Listing 1), die ohne die Funktion »nodups()« auskommt, da ich »mkMap()« so verändert habe, dass es die doppelten Werte ignoriert.

Julian Andres Klode, per Mail

Python, die Zweite

10/08, S. 30: Das Titelthema “Programmiersprachen” war eine sehr interessante Lektüre und ich finde Ihr Fazit insoweit gut, als Sie betonen, dass jede Sprache ihre Stärken und Schwächen hat.

Ganz zufrieden bin ich mit dem Artikel aber dann doch nicht, was die Darstellung von Python angeht. Die Randbemerkung, dass das völlige Versagen von Python daran liege, dass die Eingabe nicht zeilenweise, sondern in einem Zug erfolgt, ist mir zu dünn. Da hätte ich mir doch eine etwas ausführlichere Erläuterung gewünscht.

Ich habe meine Systemverwaltungsaufgaben bislang mit Perl erledigt und versuche gerade, mich mit Python vertraut zu machen; bisher bin ich von dieser Sprache auch sehr angetan. Aber was ist da los, wenn sich ein ausgewiesener Experte wie David Mertz offensichtlich so verschätzt, dass die Aufgabe für Python unlösbar wird? Es war doch aus der Aufgabenbeschreibung offensichtlich, dass Dateien im zweistelligen Megabyte-Bereich auftreten können.

Skaliert Python nicht? Oder ist der Algorithmus schuld – trotz des Experten? Liegt es am Speicher? Oder an der Verarbeitung der regulären Ausdrücke bei sehr langen Strings? Das wären für die Praxis sehr interessante Informationen gewesen.

Bernhard Kohl, per Mail

Zugegeben, die Formulierung ist etwas irreführend. Genauer müsste es heißen: Die Python-Lösung scheitert daran, 55 MByte Text mit etwa zwei Millionen Fußnoten in vertretbarer Zeit zu verarbeiten, weil die Dublettenerkennung ein immer länger werdendes assoziatives Array für jede Fußnote von vorn bis hinten durchsucht. Dennoch ist die Aufgabe für Python nicht unlösbar.

Der Sprache Python kann man sicherlich nicht die Schuld geben. Der Einsender der Lösung hat das Gewicht auf die Eleganz des Code gelegt, nicht auf die Performance. Ich finde aber, dass es darauf nicht so sehr ankommt. Immerhin, die Eleganz und Lesbarkeit von Python-Code demonstriert Mertz\’ Beispiel durchaus. Für kleinere Texte löst es auch die Aufgabe. (Peter Kreussel)

01 [...]
02 def mkMap(lst):
03     ret = {}
04     n = 1
05     for ref in lst:
06         if not ref in ret:
07             ret[ref] = "[%d]" % n
08             n+=1
09     return ret
10 [...]