Prev: Authentication
Next: 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: Authentication
Next: p!=np