Zitat:
andererseits könnte es sein, dass diese Methode falsche Primzahlen liefert?
Die Wahrscheinlichkeit, dass man eine Zahl bekommt, nachdem man diese Rechenschritte 8 mal durchgeführt hat, liegt bei 0,390625%. Und wenn man einfach nochmal 8 drauflegt, hat man diese auf 0,001526% verringert.
Es ist jedoch deine Sache, ob du diesen Test benutzen willst. Wenn es nur eine CPU-Auslastung werden soll, solltest du einfach nur alle Zahlen durchtesten ohne dem Trick mit der Wurzel und ohne diesem Test.
Wenn es allerdings wirklich Primzahlen finden soll, musst du dich nach besseren Alogrithmen umsehen (effizientere und sichere). Mit dem Fermat-Test wärst du allerdings schonmal auf dem richtigen Weg.
Zitat:
Aber eine Frage hätte ich noch in wie fern kann man Primzahlen in der Kryptographie gebrauchen?
Praktisch alle heute benutzten Arten der Kryptographie benötigen Primzahlen zur verschlüsselung, da diese nicht so einfach in ihre Faktoren zu zerlegen sind.
Im Moment werden praktisch alle Arten von Verschlüsselung durch RSA verschlüsselt. Hierfür benötigt man 2 verschiedene Primzahlen, die in ein bestimmtes Schema passen.
Zum Beispiel die Verschlüsselung von SSL-Verbindungen (u.a. https) wird mit RSA durchgeführt.
Edit: Wirklich neue Primzahlen wirst du auf diesen Wegen allerdings nicht finde... Dafür bräuchte man einfach zu viel Rechenleistung, als dass man das auf normalen Desktops lösen könnte. Da muss man dann schon etwas größeres benutzen.
J-C