Aktuelle Zeit: 12.12.2018 00:05

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]




Ein neues Thema erstellen Auf das Thema antworten  [ 13 Beiträge ]  Gehe zu Seite Vorherige  1, 2
Autor Nachricht
 Betreff des Beitrags: Re: Primzahl Prüfung Miller-Rabin Test
BeitragVerfasst: 04.01.2018 00:29 
Offline
Benutzeravatar

Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet
@Helle: Meine Assembler - Kenntnisse sind doch schon ziemlich eingerostet daher bin ich gleich auf BigInt umgestiegen. Aber für Deine Variante :allright:

aus Wikipedia:

Zitat:
Wenn die Zahl n klein ist, ist es nicht notwendig, alle a < 2(ln n)2 zu testen, da bekannt ist, dass eine viel kleinere Anzahl ausreichend ist. Beispielsweise haben Pomerance, Selfridge und Wagstaff sowie Jaeschke folgendes verifiziert:

Wenn n < 1.373.653, genügt es, a = 2 und 3 zu testen,
wenn n < 9.080.191, genügt es, a = 31 und 73 zu testen,
wenn n < 4.759.123.141, genügt es, a = 2, 7, und 61 zu testen,
wenn n < 2.152.302.898.747, genügt es, a = 2, 3, 5, 7, und 11 zu testen,
wenn n < 3.474.749.660.383, genügt es, a = 2, 3, 5, 7, 11, und 13 zu testen,
wenn n < 341.550.071.728.321, genügt es, a = 2, 3, 5, 7, 11, 13, und 17 zu testen.
wenn n < 3.825.123.056.546.413.051, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, und 23 zu testen.
wenn n < 318.665.857.834.031.151.167.461, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, und 37 zu testen.

Dabei dürfen nur solche n getestet werden, die größer sind als das jeweils größte angegebene a.


Da die angegebene Zahl 318.665.857.834.031.151.167.461 größer ist als die größte positive QUAD und die größste zu prüfende Zahl ja in eine positive QUAD passen muss, kann man den Algo mit obigen Angaben auch recht einfach in einen deterministischen ändern und wirklich sicher sein dass bei Rückgabe #True die Zahl auch eine Primzahl ist.

Wenn ich die Tage mal Zeit finde baue ich die Procedure vlt. um sodass auch Zahlen größer als QUAD getestet werden können. Dann aber wieder mit BigInt auch wenn es deutlich langsamer ist als die Variante von Helle. Oder einer von Euch kommt mir da zuvor :mrgreen:

_________________
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Primzahl Prüfung Miller-Rabin Test
BeitragVerfasst: 05.01.2018 22:14 
Offline

Registriert: 05.01.2018 21:46
Als stiller Mitleser habe ich alle Beiträge interessiert verfolgt und kann nur staunen was Ihr Profis imstande seid zu leisten. Zu diesem Thema habe ich heute zufällig einen Bericht über einen neuen WR gelesen, den ich Euch nicht vorenthalten möchte, wenn Ihr es noch nicht gelesen habt.

https://www.mersenne.org/primes/

Schöne Grüße
Dextro


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Primzahl Prüfung Miller-Rabin Test
BeitragVerfasst: 07.01.2018 12:24 
Offline
Benutzeravatar

Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet
Eine Variante die komplett mit BigInt arbeitet im ersten Post hinzugefügt. Dadurch können theoretisch beliebig große Zahlen getestet werden; vgl. Hinweise im ersten Post.

_________________
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 13 Beiträge ]  Gehe zu Seite Vorherige  1, 2

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: Bing [Bot], Google [Bot] und 4 Gäste


Sie dürfen keine neuen Themen in diesem Forum erstellen.
Sie dürfen keine Antworten zu Themen in diesem Forum erstellen.
Sie dürfen Ihre Beiträge in diesem Forum nicht ändern.
Sie dürfen Ihre Beiträge in diesem Forum nicht löschen.

Suche nach:
Gehe zu:  

 


Powered by phpBB © 2008 phpBB Group | Deutsche Übersetzung durch phpBB.de
subSilver+ theme by Canver Software, sponsor Sanal Modifiye