Prev: AuthenticationNext: p!=np From: Cristiano on 9 Aug 2010 05:49 In the paper "Further Investigations with the Strong Probable Prime Test" http://www.ams.org/journals/mcom/1996-65-213/S0025-5718-96-00695-3/home.html Ronald J. Burthe gives some formulas for the probability that the Miller-Rabin test fails. On page 379, Burthe writes that probability as: p(k,t) = N1 / (N1+P1) P1 is the lower bound of the number of k-bit primes and N1 is an upper bound for the sum over the composite integers (please, refer to the paper for a good explanation of N1). I implemented an improved version of the method described on page 379 to calculate N1 and P1. While the lower bound P1 is very good (I used an improved formula given by P. Dusart), the upper bound N1 is much bigger than the true value. I calculated the true value of the numerator using the formula on page 380 (which can be used only for small values of k, say k < 40 bit). Here some values: k TRUE N1 21 28,98 30241,1 23 49,72 100913,2 25 80,97 314258,6 27 137,26 1024264,8 29 234,74 3486901,6 Is there a better upper bound N1 or a better formula for p(k,t)? Thanks Cristiano  |  Pages: 1 Prev: AuthenticationNext: p!=np