Das Programm berechnet lange Primzahlen (bis zu 999 Ziffern).

Solche großen Primzahlen werden für das RSA-Verfahren benötigt.
de.wikipedia.org/wiki/RSA-Kryptosystem
Als Algorithmen habe ich Fermat und Rabin-Miller benutzt.
de.wikipedia.org/wik...atscher_Primzahltest
de.wikipedia.org/wiki/Miller-Rabin-Test
In der Unit LangZahlRechnen sind die nötigen Routinen implementiert.
Viel Spaß beim Testen
Fiete

Edit1:
Die Anzahl der Zeugen lässt sich einstellen, die Versuche werden gezählt und angezeigt.
Es lässt sich zeigen, dass die Wahrscheinlichkeit dafür, dass eine ungerade zusammengesetzte Zahl n durch den Miller-Rabin-Test nicht als zusammengesetzt identifiziert wird, kleiner als 1/4^k ist für k Zeugen.
k = 12 ergibt 0,00000005960464
k = 24 ergibt 3,5527136788005009293556213378906e-15
Dabei ist es zwar theoretisch möglich, dass eine zusammengesetzte Zahl als Primzahl genutzt wird, die Wahrscheinlichkeit ist jedoch so gering, dass es in der Praxis keine Rolle spielt.

Hallo,

wie kommt man auf die Liste der Prüfzahlen?
Ich sehe dort nur einfach die ersten 12 Primzahlen.Macht das Sinn?

Für kleinere Zahlen gibt es ja gute Kombinationen, die Mathematiker in der von Ihm genutzten Variante von is_prime einsetzt.( nIcht optimal, wie ich jetzt weiß )

Man kann ja bei der Suche so etwas finden:
//SPRP= strong probable prime
Finding strong probable prime bases for efficient ranged primality testing
"The best known SPRP bases sets" -> miller-rabin.appspot.com/
Ala mit 3 Basen für alle Zahlen bis 75e9 auf prim zu testen. // Keine Basis > 32 Bit
75.792.980.677: 2, 379215, 457083754 Steve Worley anno 2009

Man müßte mal herausfinden, wie man die BesteBasis ( Lugato?? ) findet

Achso, es wäre eine Anzeige während der Laufzeit nett.
Bei 100 Stellen einmal 0.7 und dann fast 15 Sekunden, da denke ich immer, da ist was kaputt

Gruß Horst

Horst_H hat folgendes geschrieben :

Achso, es wäre eine Anzeige während der Laufzeit nett. Bei 100 Stellen einmal 0.7 und dann fast 15 Sekunden, da denke ich immer, da ist was kaputt

Ging mir auch so. Obwohl es ja nur eine GUI-Anpassung ist und nichts mit der Idee zu tun hat.

Aber da wir einmal dabei sind:

• Abgelaufene Zeit
  
• Programmstatus(Startbereit, In Bearbeitung, Beendet)
  
• Vielleicht voraussichtliche Bearbeitungszeit (Hatte was bei knapp 30 Minuten)
  
• Resize Form aktualisieren/ Größe der Elemente anpassen

Zum Problem kann ich leider nichts sagen, aber verfolge eure Themen mit Interesse.

Hallo,

Zitat:

Zum Problem kann ich leider nichts sagen, aber verfolge eure Themen mit Interesse.

Mal schauen, was die "Spinner" da wieder merkwürdiges treiben ..

An dem Programm etwas zu ändern, liegt mir nichts, denn Gammatester hat mit mparith etwas wesentlich leistungsstärkeres und gmp ist noch eine Ecke schneller.Das Programm zeigt sehr anschaulich, wie wenig Zeilen schon reichen.

Gruß Horst
P.S
Eine Angabe in Bit wäre toll.
Bits ~ Anzahl_Dezimalen/ log10(2) = 3,322 *Anzahl_Dezimalen
4096 Bit wären also 1233 Dezimalen, dann wird die Rechnerei etwas zäh....
EDIT:
Der Miller-Rabin Test viertelt bei Bestehen, die Wahrscheinlichkeit einer Primzahl.
Test bestanden => 75% es ist Primzahl / 25% es ist dennoch keine Primzahl
p = (1/4) ^AnzahlTests.
Bei 100 Dezimalen ~ 330 Bits = 2^330 = 4 ^ 155 braucht es mindestens 155 Tests mit zueinander teilerfremden Zahlen, am einfachsten Primzahlen, um die Unsicherheit in den Bereich des letzten Bits, wenn man es so nennen möchte, zu bekommen.

Moin,
die unterschiedlichen Laufzeiten resultieren von der K-Schleife und ob die Zufallszahl prim ist!
Eine Fortschrittsanzeige könnte abhängig von der Listenlänge sein, bisher gibt's die Sanduhr.
Man könnte auch mit den Basen von miller-rabin.appspot.com/ experimentieren.
Mit 2, 379215, 457083754 gab es kurze Rechenzeiten.
Gruß Fiete

Hallo,

aber die angegebenen Basen sind doch nur Tests für "kleine" Zahlen.
Die suchen doch Basen deren Pseudoprimzahl-Mengen möglichst verschieden/disjunkt sind.
Was n-1 Basen als pseudoprime bestätigen, schmeißt die letzte Base als definitiv zusammengesetzt heraus.
Beim Fermat Test steht ja drin, dass Anzahl der pseudoprimen Zahlen nicht stark abnimmt.

Für sehr große, 100 Stellige, Zahlen gibt es dort keine Aussagen.
Da hilft nur der massenhafte Test mit zufälligen Primzahlen bis 65536 sind es ja schon 6542.
Da ist vielleicht doch schneller, den Lucas-Test einzubauen.

Zitat:

(Maple, isprime) It returns false if n is shown to be composite within one strong pseudo-primality test and one Lucas test and returns true otherwise

www.entwickler-ecke....der=asc&start=20
Es geht hier aber doch mehr um das prinzipielle Vorgehen und nicht um Geschwindigkeit.

Gruß Horst

Moin,
das Programm wurde wunschgemäß geändert.
Für große Zahlen bietet Fermat keine Gewähr, Rabin-Miller weist eine größere Wahrscheinlichkeit auf.
Es ist zwar theoretisch möglich, dass eine zusammengesetzte Zahl als Primzahl erkannt wird, die Wahrscheinlichkeit ist jedoch
so gering, dass es in der Praxis keine Rolle spielt.
Andere ausführliche Algorithmen habe ich nicht gefunden.
Gruß Fiete