| |
 |
| Primzahlen Problem gelöst |
|
|
Veröffentlicht durch dawn am Montag 12. August, 10:34
Aus der mathematik Abteilung
|
|
|
|
|
Wie derStandard.at berichtet, haben drei indische Forscher einen Algorithmus entwickelt, mit dem sich prüfen lässt, ob eine bestimmte Zahl eine Primzahl ist. Im Gegensatz zum bereits seit langem bekannten Algorithmus von Eratosthenes ist dieser deterministisch und polynominell (Eratosthenes Algorithmus ist exponentiell zur Grösse des Inputs). Von den Forschern gibt es auch ein Paper dazu.
|
|
|
|
< Gobe Productive Office kommt unter GPL | Druckausgabe | Lilo und OPN kämpfen mit Problemen > | |
|
|
Diese Diskussion wurde archiviert.
Es können keine neuen Kommentare abgegeben werden.
|
|
|
|
|
|
|
|
|
|
|
|
|
Hihi. Ja, bei uns im IRC (#plant, IRCnet) ist auch folgendes passiert:
12:04 -XTaran- Cool, drei indische Forscher haben einen Algorithmus zur Prüfungen einer Zahl auf Primheit (Primsein? Primzahlsein?) entdeckt, der deterministisch und polynomiell ist!
12:06 -FelixKatz- *rsaindietonnekipp*
12:06 -XTaran- Nein, nicht Primfaktorzerlegung! Das kann der nicht.
12:06 -FelixKatz- Oh. *rsawiederraushol*
12:06 -FelixKatz- *rsaabwisch*
12:07 -FelixKatz- *rsapolier*
12:07 -XTaran- Im Gegenteil, damit können die auf Primzahlen basierenden Verschlüsselungsalgorithmen 100% sicher sein, daß sie Primzahlen haben.
12:09 -XTaran- http://www.symlink.ch/article.pl?sid=02/08/11/1138226&mode=nested btw
12:15 -robilad- Primzahlen zerlegen kann ich auch.
12:15 -robilad- haben eh nur zwei faktoren
maol, und selbst wenn: ElGamal ist IIRC bewiesen sicher und basiert auch nicht auf Primfaktorzerlegung. Man braucht sich also diesbezüglich keine Sorgen machen. Sorgen kommen erst, wenn man mal Quantencomputer auf sowas ansetzen kann.
--
Einer der Gnutella-Klone heißt Gnutoka, und ich frag mich, wann Gnusspli rauskommt...
|
|
|
|
|
|
|
|
|
|
|
|
|
ElGamal ist IIRC bewiesen sicher
Bewiesenermaßen sicher ist nur das One-time Pad.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ok, ich hab's etwas arg lax formuliert und auch noch die Häfte falsch im Kopf gehabt. Deswegen habe ich's grade nochmal genau nachgelesen:
Es ist bewiesen, daß ElGamal genauso schwer ist, wie das Diffie-Hellman-Problem. Bei RSA ist z.B. nicht bewiesen, daß RSA genauso schwer ist wie die Primfaktorzerlegung. (Das war das, was ich beim Schreiben des Kommentars im Kopf hatte, aber nicht mehr richtig zusammen brachte. Schande über mich. Ich hoffe, ich hab's jetzt richtig.) Außerdem ist der ElGamal-Algorithmus im Gegensatz zu RSA nicht durch Patente beschränkt, was ihn natürlich zum Liebling der Open-Source-Fans macht.
100% sicher ist natürlich nur das One-Time-Pad.
--
Einer der Gnutella-Klone heißt Gnutoka, und ich frag mich, wann Gnusspli rauskommt...
|
|
|
|
|
|
|
|
|
|
|
|
|
>100% sicher ist natürlich nur das One-Time-Pad.
Wenn die Schlüssellänge >= des zu verschlüsselnden Textes ist und nicht mehrmals verwendet wird und sicher übertragen wird.
|
|
|
|
|
|
|
|
|
|
|
|
|
Das ist genau die Eigenschaft eines One-Time-Pad. Deswegen auch der Name: Jedes Bit wird nur einmal benutzt um ein anderes Bit zu verschlüsseln. Und daß der Schlüssel nicht korrupt ist, davon geht man bei dieser Betrachtung aus.
--
Einer der Gnutella-Klone heißt Gnutoka, und ich frag mich, wann Gnusspli rauskommt...
|
|
|
|
|
|
|
|
|
|
|
|
|
oder hat diese Entdeckung noch weitere praktische Folgen?
Bei Verfahren, die darauf angewiesen sind, große Primzahlen zu erzeugen, hat man bis jetzt den Miller-Rabin- oder Fermat-Test benutzt, die mit sehr hoher Wahrscheinlichkeit sagen können, ob es sich dabei um eine Primzahl handelt, aber eben nicht mit 100%iger Sicherheit. Nun kann man das eben mit 100%iger Sicherheit in polynominaler Zeit sagen. Die Kryptosysteme werden also stärker.
|
|
|
|
|
|
