Probability of a Mersenne number being prime

[vimil]

On clicking the status menu-item from the Test menu of Prime95 I am told the probabilty of the mercene number I have chosen to test being prime is 1 in 317069.Even though the percentage of iterations of Lucas Lehmer test increases this probabilty remains the same. Shouldn't this probability increase with the iterations of Lucas-Lehmer test?

[TimSorbet]

Originally Posted by vimil

On clicking the status menu-item from the Test menu of Prime95 I am told the probabilty of the mercene number I have chosen to test being prime is 1 in 317069.Even though the percentage of iterations of Lucas Lehmer test increases this probabilty remains the same. Shouldn't this probability increase with the iterations of Lucas-Lehmer test?

No, it shouldn't. The LL (Lucas-Lehmer) test doesn't give any results until it is 100% completed, after which it determines whether the number is prime or composite. It does not find factors.
Here's more reading about the LL test: (the top one has info on the other tests Prime95 runs)
http://www.mersenne.org/math.htm
http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers
http://mathworld.wolfram.com/Lucas-LehmerTest.html

[R.D. Silverman]

Originally Posted by vimil

On clicking the status menu-item from the Test menu of Prime95 I am told the probabilty of the mercene number I have chosen to test being prime is 1 in 317069.Even though the percentage of iterations of Lucas Lehmer test increases this probabilty remains the same. Shouldn't this probability increase with the iterations of Lucas-Lehmer test?

I am curious as to why you think it should. The LL test is a
computational procedure. It gives a yes/no answer based on a
simple modular criterion that says at the *ultimate iteration*, a certain
value should be 0. Why do you think this implies that running some number
of earlier iterations yields any information about what the final answer will
be? [hint: it doesn't; the map x_{n+1} = x_n^2 -2 is pseudo-random
within the finite field GF(P^2) where P = 2^p-1 is the number being tested]

I am curious as to your thought processes on this matter.

And stating that the probability is 1/317069 is fuzzy at best. In actuality,
for any given number, the probability is either 1 or 0. Asserting that it
is 1/317069

(1) Assumes some facts that have not yet been proven.
(2) Assigns a probability based on the assumption that a number has been
drawn, uniformly at random, from a fairly short interval of potential candidates. However, this is the a priori probability for any candidate in
the interval. Once you have taken a *sample*, the probability becomes
either 0 or 1.
(3) Uses more significant digits than any possible theorem can give.
It implies more accuracy in the estimate than is mathematically
possible.

Mathematicians do have some heuristics that tells us what the probability
will be for randomly drawn candidates that are SUFFICIENTLY LARGE.
Sufficiently large means as the candidates go to infinity. These heuristics
can give only a very rough approximate probability for the small numbers
we are working with today.

[potonono]

You mean to say the probability isn't 50/50 when it gets to the last iteration? :)


jk

[retina]

Originally Posted by potonono

You mean to say the probability isn't 50/50 when it gets to the last iteration? :)

Of course not, it is 50/50 when you get half way through the interations.

[Fusion_power]

One way to look at this is that a Mersenne number could be either prime or composite right up to completion of the final iteration. From this perspective, it is similar to the Shroedinger's Cat scenario, meaning there is a cat in a box and it could be either alive or dead and in some ways is both. Only when the box is opened do the probabilities converge and one result is seen.

From this viewpoint, saying the probability is 50/50 at any point during the iterations is ludicrous.

DarJones

[R.D. Silverman]

Originally Posted by Fusion_power

One way to look at this is that a Mersenne number could be either prime or composite right up to completion of the final iteration. From this perspective, it is similar to the Shroedinger's Cat scenario, :

Codswallop. A Mersenne number is either prime or composite even
before one conducts a LL test. Bringing in QM is nonsense. Indeed,
*every* number (except for units) is either prime or composite.

Conducting a primality test simply reveals which. We simply don't
know the answer until after the test is run. But it is definitely one or
the other, unlike QM when it is *neither* until the wave function collapses.

[bsquared]

Originally Posted by R.D. Silverman

A Mersenne number is either prime or composite even before one conducts a LL test...

Conducting a primality test simply reveals which.

It is this fact which I think confuses people when they say there is a probability that a number is prime, because it seems like a flip of the coin as to which is revealed. I know it has confused me. I like to think of the primeness of a number as a signal in a channel which has been muddled by noise. We just can't tell what the signal is until after we apply our perfect dectector to the channel (the LL test), but the signal itself is never in doubt.

[vimil]

Allright, how does Prime95 come up with this probability then? Does it run some other probablistic test on a mercenne number before giving it to the user to test?

[R.D. Silverman]

Originally Posted by bsquared

It is this fact which I think confuses people when they say there is a probability that a number is prime, because it seems like a flip of the coin as to which is revealed. I know it has confused me. I like to think of the primeness of a number as a signal in a channel which has been muddled by noise. We just can't tell what the signal is until after we apply our perfect dectector to the channel (the LL test), but the signal itself is never in doubt.

An *individual* number does not have a "probability" in the sense
you discuss.

When we assign a probability we mean that if one selects a number
*uniformly at random* from some short interval, then it might be prime
or it might be composite. The probability is the percentage of numbers
in the interval that ARE prime.

probability always means with respct to some underlying distribution.
For Mersenne primes, the distribution is *believed* to be Poisson,
but there is no proof. (nor any hope of proof in the near future)

[bsquared]

Originally Posted by vimil

Allright, how does Prime95 come up with this probability then? Does it run some other probablistic test on a mercenne number before giving it to the user to test?

A given integer N is either prime or not, but it's possible to *model* a range of integers using a probability distribution, in order to say something about how many primes to expect in that range. One rough estimate is the probability that an integer n is prime is about 1/log n. This figure must be modified if one has already determined that no small primes up to some limit divide the integer (and I presume your test number has been sieved to some bit depth). I don't know the exact implementation details, but I suspect that this is what prime95 is doing. Again, this is simply the output of a probablistic model and says nothing about the true primeness of a particular number.

- ben.