- Primzahlen:
Bereits vor 2000 Jahren war den Griechen bekannt, daß es besondere Zahlen gibt, die Primzahlen, die nicht weiter geteilt werden können, und die mathematische Algebra lehrt uns, daß jede natürliche Zahl auf eindeutige Weise in Primfaktoren zerfällt.
Dennoch hat es über zwei Jahrtausende gedauert, bis im Jahre 2002 drei indische Informatiker den ersten effizienten Algorithmus gefunden haben, der Primzahlen von Nichtprimzahlen unterscheiden kann.
Mit sogenannten randomisierten Algorithmen konnte man dies schon 25 Jahre früher, aber derartige Verfahren besitzen eine kleine Irrtumswahrscheinlichkeit, daß ihr Ergebnis nicht korrekt ist.Buch über Primzahltest:
M. Dietzfelbinger, Primality Testing in Polynomial Time
Springer Lecture Notes in Computer Science, Band 3000, Springer Verlag, 2004. -
Faktorisierung:
Für konventionelle digitale Rechner dürften schnelle Algorithmen auf absehbare Zeit nicht zu erwarten sein - massive Anstrengungen weltweiter Experten in den letzten Jahrzehnten haben hier keine Durchbrüche errreichen können. Für das Modell des Quantencomputers dagegen hat Peter Shor vor etwas mehr als zehn Jahren einen schnellen Faktorisierungsalgorithmen entdeckt. Es ist aber nicht klar, ob eine derartige Maschine, die genügend viele Quantenbits verarbeiten kann, jemals real gebaut werden kann.
- Einweg-Funktionen mit Geheimtür
- Eine der ersten Veröffentlichungen im Bereich der Trapdoor Functions:
W. Diffie, M.E. Hellman - New Directions in Cryptography,
IEEE Transactions on Information Theory 22(6), pp 644-654, 1976 -
Ralph Merkle, Whitfield Diffie und Martin E. Hellman haben 1978 ein Verfahren vorgeschlagen, das
Trapdoor-Knapsack genannt wird (Geheimtür-Rucksack-Problem).
Leider wurde dieses Kryptosystem bereits Anfang der 80er Jahre geknackt.
Es ist dennoch interessant und eng verwandt mit unserem Münzproblem: Das Geheimnis liegt darin, eine beliebige (schwere) Münzfolge in eine supermonotone zu verwandeln, ähnlich wie wir es mit unserem Telefonbuch und der Umkehrung der Transformation S gemacht haben.
- Merkle-Hellman Knapsack Cryptosystem: Verweis 1 , Verweis 2 , Original-Arbeit von R. Merkle und M.E. Hellman: Hiding Information and Signatures in Trap Door Knapsacks, IEEE Transaction on Information Theory, 24, pp. 525-536, 1978
- Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem, CRYPTO 1982, pp 279-288.
- Eine der ersten Veröffentlichungen im Bereich der Trapdoor Functions:
- weitere Links: