Re: Primzahl Prüfung Miller-Rabin Test
Verfasst: 04.01.2018 00:29
@Helle: Meine Assembler - Kenntnisse sind doch schon ziemlich eingerostet daher bin ich gleich auf BigInt umgestiegen. Aber für Deine Variante
aus Wikipedia:
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
aus Wikipedia:
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 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.
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