Seite 1 von 1
effizientes Primzahlensieb
Verfasst: 13.08.2005 16:06
von yoyo
Aus Telepolis:
http://www.telepolis.de/tp/r4/artikel/20/20678/1.html
Ein effizientes Primzahlensieb könnte indirekt die im Online-Handel
übliche asymmetrische Verschlüsselung obsolet werden lassen
Verfasst: 13.08.2005 21:57
von Patrick Keller
Der Artikel ist einfach FALSCH:
Es handelt sich nicht um ein 'Primzahlsieb' bei dem eine große Zahl von Primzahlen der selben Form faktorisiert werden sondern um einen Algorithmus, der mit Hilfe von 'Fermat's Kleinem Satz' ermittelt ob eine Zahl prim ist. Hier spricht der Artikel von Fermats Letztem Satz, was auch falsch ist (x^n+y^n=z^n, n>2).
Weiterhin ist der sogenannte PRP-Test kein deterministischer Test. Das heißt die Zahl KANN prim sein, wenn a^p = a (mod p) ist.
Der Algorithmus wird auch bereits bei Projekten wie SoB oder PSP verwendet ... Also ich weiß nicht was die Herren da getrickst haben
PS: Mit dem Faktorisieren von Primzahlen wie in der Nachricht hier steht, hat das ganze wirklich NICHTS zu tun.
Verfasst: 14.08.2005 08:49
von Thommy3
Naja ok, Keller. Das interessante ist aber schon der Algorithmus, und der wird auch nicht schon eingesetzt von SooB und so. Es geht hier ja nicht um den PRP Test, sondern "Das Prinzip beruht" nur darauf.
FAQ zuim Artikel "Primes in P"
http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
Algorithmus
http://primes.utm.edu/prove/prove4_3.html