[Primes Home][Home]
In cryptography we sometimes have to estimate \(pi(x)\), and which is the number of primes between 0 and \(x\). This page estimate the number of primes for a given bit size and will use the Riemannr method.
Estimate number of primes
[Primes Home][Home]
In cryptography we sometimes have to estimate \(pi(x)\), and which is the number of primes between 0 and \(x\). This page estimate the number of primes for a given bit size and will use the Riemannr method.
|
One method which can be used to estimate the number of prime numbers is the Riemann R function. This is a smooth approximation for π(x). The function is defined using the rapidly convergent Gram series:
\(R(x) = 1 + \sum_{k=1}^{\infty} \frac{\log^k x}{k k! \zeta(k+1)}\)
A sample run is:
from mpmath import * import sys from decimal import * bits=512 print ("Estimate the number of primes for a given prime number size.") if (len(sys.argv)>1): bits=int(sys.argv[1]) val=2**(bits) val2=2**(bits-1) print ("\nNumber of bits in prime number:\t",bits) est = int(riemannr(val))-int(riemannr(val2)) print ("Estimated number of prime numbers is:\t",est) d_est = Decimal(est) d_val = Decimal(val-val2) val = Decimal(100*d_est)/Decimal(d_val) print ("Changes of finding a prime: ",round(Decimal(val),2),"%")