Talk:Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
No edit summary |
m (→Analysis) |
||
Line 22: | Line 22: | ||
==Analysis== |
==Analysis== |
||
Carmichael numbers 100% defeat Fermat's Little Theorem. Miller Rabin uses a combination of Fermat's Little Theorem and Chinese Division Theorem to promise that a false prime for any number is not returned with a probability of more than 25%. The following table tries all numbers from 5 to 999. It shows the number of trues returned / number of possible trials and expresses it as a percentage. The numbers in brackets are the values that return true. The worst case is 703 (22.86% false trues). This task's interest is 561 (3*11*17)(1.43%). 1264 false trues were found out of 172878 possible trials (0.73%). |
Carmichael numbers 100% defeat Fermat's Little Theorem. Miller Rabin uses a combination of Fermat's Little Theorem and Chinese Division Theorem to promise that a false prime for any number is not returned with a probability of more than 25%. The following table tries all numbers from 5 to 999. It shows the number of trues returned / number of possible trials and expresses it as a percentage. The numbers in brackets are the values that return true. The worst case is 703 (22.86% false trues). This task's interest is 561 (3*11*17)(1.43%). 1264 false trues were found out of 172878 possible trials (0.73%). --[[User:Nigel Galloway|Nigel Galloway]] 13:48, 27 December 2012 (UTC) |
||
<pre style="height:30ex;overflow:scroll"> |
<pre style="height:30ex;overflow:scroll"> |
||
5 2/2 100.00% [2, 3] |
5 2/2 100.00% [2, 3] |