Talk:Miller–Rabin primality test: Difference between revisions
| Line 11: | Line 11: | ||
</lang> |
</lang> |
||
with n=703 (19 * 37) and g=1 for times=10,000 returned 2242 false trues, which compares well with the 2286 which may be expected [http://rosettacode.org/wiki/Talk:Carmichael_3_strong_pseudoprimes,_or_Miller_Rabin%27s_nemesis#Analysis from]. Increasing g to 5 reduced the number of false trues to 7. Increasing g to 10 reduced the number of false trues to 0 even when times was increased to 100000. Increasing times to 1000000 only returned 1 false true.--[[User:Nigel Galloway|Nigel Galloway]] 13:47, 30 December 2012 (UTC) |
with n=703 (19 * 37) and g=1 for times=10,000 returned 2242 false trues, which compares well with the 2286 which may be expected [http://rosettacode.org/wiki/Talk:Carmichael_3_strong_pseudoprimes,_or_Miller_Rabin%27s_nemesis#Analysis from]. Increasing g to 5 reduced the number of false trues to 7. Increasing g to 10 reduced the number of false trues to 0 even when times was increased to 100000. Increasing times to 1000000 only returned 1 false true. Obviously these results will vary for each trial.--[[User:Nigel Galloway|Nigel Galloway]] 13:47, 30 December 2012 (UTC) |
||
Revision as of 13:49, 30 December 2012
Python
This task can also be handled by the NZMATH modules prime and arith1 to enable its millerRabin function.--Billymac00 02:32, 3 January 2011 (UTC)
Testing Composite Probability
In addition to finding primes it is interesting to determine how often the algorithm returns composites as prime, see here. Using Ruby's miller_rabin_prime? as follows:
<lang ruby> v = (1..times).find_all { |i| miller_rabin_prime?(n,g)} puts v.length </lang>
with n=703 (19 * 37) and g=1 for times=10,000 returned 2242 false trues, which compares well with the 2286 which may be expected from. Increasing g to 5 reduced the number of false trues to 7. Increasing g to 10 reduced the number of false trues to 0 even when times was increased to 100000. Increasing times to 1000000 only returned 1 false true. Obviously these results will vary for each trial.--Nigel Galloway 13:47, 30 December 2012 (UTC)