Talk:Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
m (moved Talk:Carmichael 3 strong pseudoprimes, or Miller Rabin's nemesis to Talk:Carmichael 3 strong pseudoprimes: Alternate names are done via redirects, not multipart names) |
m (→Analysis: increased the windows size (for the PRE html tab) for easier perusing.) |
||
| Line 23: | Line 23: | ||
==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%). --[[User:Nigel Galloway|Nigel Galloway]] 13:48, 27 December 2012 (UTC) |
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: |
<pre style="height:80ex;overflow:scroll"> |
||
5 2/2 100.00% [2, 3] |
5 2/2 100.00% [2, 3] |
||
7 4/4 100.00% [2, 3, 4, 5] |
7 4/4 100.00% [2, 3, 4, 5] |
||