 mersenneforum.org Probability of a Mersenne number being prime
 Register FAQ Search Today's Posts Mark Forums Read  2007-12-10, 17:19 #1 vimil   Nov 2007 3 Posts Probability of a Mersenne number being prime 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?   2007-12-10, 18:03   #2
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts Quote:
 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   2007-12-10, 18:04   #3
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 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.   2007-12-11, 02:35 #4 potonono   Jun 2005 USA, IL 193 Posts You mean to say the probability isn't 50/50 when it gets to the last iteration? :) jk   2007-12-11, 08:44   #5
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

22×5×307 Posts Quote:
 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.    2007-12-11, 12:19 #6 Fusion_power   Aug 2003 Snicker, AL 7·137 Posts 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    2007-12-11, 14:45   #7
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 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.   2007-12-11, 15:03   #8
bsquared

"Ben"
Feb 2007

2×32×191 Posts Quote:
 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.

Last fiddled with by bsquared on 2007-12-11 at 15:06   2007-12-11, 17:17 #9 vimil   Nov 2007 3 Posts How does Prime95 come up with this probability 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? Last fiddled with by vimil on 2007-12-11 at 17:19   2007-12-11, 18:14   #10
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 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)   2007-12-11, 18:15   #11
bsquared

"Ben"
Feb 2007

2×32×191 Posts Quote:
 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.

Last fiddled with by bsquared on 2007-12-11 at 18:25 Reason: tpyo   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 Trilo Homework Help 12 2014-06-06 19:17 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 optim Math 2 2003-12-06 19:03 Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 20:26.

Tue May 11 20:26:08 UTC 2021 up 33 days, 15:07, 1 user, load averages: 1.75, 2.30, 2.24