You are currently browsing the tag archive for the ‘probability of being a prime’ tag.
Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)
1. Since, by the Prime Number Theorem, the number of primes is , it would follow that determining a factor of requires at least one logical operation for each prime , and therefore cannot be done in polynomial time—whence —IF whether or not a prime divides an integer were independent of whether or not a prime divides the integer .
2. Currently, conventional approaches to determining the computational complexity of Integer Factorising apparently appeal critically to the belief that:
(i) either—explicitly (see here)—that whether or not a prime divides an integer is not independent of whether or not a prime divides the integer ;
(ii) or—implicitly (since the problem is yet open)—that a proof to the contrary must imply that if is the probability that is a prime, then .
3. If so, then conventional approaches seem to conflate the two probabilities:
(i) The probability of selecting a number that has the property of being prime from a given set of numbers;
Example 1: I have a bag containing numbers in which there are twice as many composites as primes. What is the probability that the first number you blindly pick from it is a prime. This is the basis for setting odds in games such as roulette.
(ii) The probability of determining that a given integer is prime.
Example 2: I give you a -digit combination lock along with a -digit number . The lock only opens if you set the combination to a proper factor of which is greater than . What is the probability that the first combination you try will open the lock. This is the basis for RSA encryption, which provides the cryptosystem used by many banks for securing their communications.
4. In case 3(i), if the precise proportion of primes to non-primes in is definable, then clearly too is definable.
However if is the set of all integers, and we cannot define a precise ratio of primes to composites in , but only an order of magnitude such as , then equally obviously cannot be defined in (see Chapter 2, p.9, Theorem 2.1, here).
5. In case 3(ii) the following paper proves , since it shows that whether or not a prime divides a given integer is independent of whether or not a prime divides :
Not only does it immediately follow that (see here), but we further have that , with a binomial standard deviation. Hence, even though we cannot define the probability of selecting a number from the set of all natural numbers that has the property of being prime, can be treated as the de facto probability that a given is prime, with all its attended consequences for various prime-counting functions and the Riemann Zeta function (see here).