Where to start

[Jellyfish420]

Basic overview.....i recently OCed my pc and started running P95 for stress. Thinking bout how big these numbers actually are and that 47 have ever been found has sparked my interest. I been doing LL tests on one core and TF on the other for bout 2weeks. Reading around on this forum. And i understand, to an extent, about what a mersenne prime is... But when people start talking bout different factors, and bit levels, and all the other good stuff i am totally lost. Ive searched around and i can find what stuff means but without a more basic knowledge the more advanced stuff really doesn't mean much. So after all that reading where do i start? Anyone got some links to some good reading? I need to learn the basics so i have something to build off of. Thank you to anyone that can help

[Dubslow]

So when we talk about "exponents", such as s 59,xxx,xxx exponent, we mean that we're talking about the number 2^59,xxx,xxx-1, but it seems you know that.

The LL test is a guaranteed test of primality -- if it's says 2^p-1 is composite, then if definitely is, and if it says it's prime, it definitely is. Of course, as you've probably figured out, running an LL test takes quite a bit of time, even with highly-optimized assembly on modern processors, so if we can avoid the test, we've saved a bunch of computing time.

The easiest way to avoid the LL test is to prove that 2^p-1 is composite by showing that it has a factor. This is what trial factoring is: literally just try all numbers below a certain bound to see if they divide 2^p-1. (It's not quite like that -- but that's the idea.) So first we check all numbers below (say) 2^59. If TF fails to find such a factor, then we say that 2^p-1 has no factors less than 2^59, or alternately, we say that 2^p-1 was TFed to 59 bits. (That's because any number < 2^59 is 59 bits in binary representation.) Then we check for factors from 2^59 to 2^60, when we can say (if no factor was found) that 2^p-1 was TFed to 60 bits. Then we check between 2^60 and 2^61, etc. up to a certain bound where doing TF becomes more expensive that just doing the LL test -- typically around 72 or 73 bits for exponents in the 59 million range. (That's if the TF is done on a GPU -- for CPUs the crossover is around 69 bits.)

All in all, a bit more than ~60% of candidate exponents are found to have a small factor, meaning we save a lot of CPU time from doing useless LL tests. (Note: we also use a factoring method called P-1 ("p minus 1") factoring, but that works differently from TF.)

(PS @chalsall: Something's wrong in the 33M-34M region of the graphs.)

[Uncwilly]

Poke around on the Wiki, here is a good page to start on: http://mersennewiki.org/index.php/Category:GIMPS_FAQ

[Jellyfish420]

Ok, i get that... I should of been clearer in my first post. I get ,for the most part, whats happening. The compute is finding factors of exponents cause its faster to do that than to LL test every number. What im curious about is the math side of it. People start throwing around equations and i just look at them for a min and go WTF? And also what does everyone mean when they say something is to expensive? Up 2 posts its too expensive to factor over 72...

[chalsall]

Originally Posted by Dubslow

(PS @chalsall: Something's wrong in the 33M-34M region of the graphs.)

Yeah... I know...

[Dubslow]

Originally Posted by Jellyfish420

Ok, i get that... I should of been clearer in my first post. I get ,for the most part, whats happening. The compute is finding factors of exponents cause its faster to do that than to LL test every number. What im curious about is the math side of it. People start throwing around equations and i just look at them for a min and go WTF? And also what does everyone mean when they say something is to expensive? Up 2 posts its too expensive to factor over 72...

Well, I can answer about "expensive". Essentially, what's the most efficient way to use available CPU/GPU cycles? (Or, how many exponents can we clear with x many cycles available?)

Well, as you can imagine, since 2^73 = 2 * 2^72, doing one bitlevel takes about twice as much work to TF than the previous bitlevel. (That is, TFing 2^73-2^74 takes twice as much work as TFing 72-73.) Furthermore, the chance of finding a factor is roughly 1/bitlevel, so as you do more and more TF, you have less and less chance of finding a factor. (I can't quite prove this latter statement, but it's related to the distribution of primes.)

Thus, at a certain point, it takes more CPU time (or GPU time, in the case of TF) to find a factor than run an LL test on one exponent.

For instance, if TFing one exponent from 72-73 bits takes one day on your GPU, then on average you'd expect to find one factor (that is, clear one exponent as not prime) once every 73 days. If running an LL test on your CPU takes 73 days, then this is the "crossover point"; you'll clear more Mersenne numbers by running LL tests than by TFing them to 74 bits, so 73 bits is where you stop TFing.

That's roughly what we mean by expense: how many C/GPU cycles it takes to complete a particular assignment.



What parts of the math don't you get? I was just guessing, and clearly I guessed wrong. Please be more specific.

[Jellyfish420]

Gotcha. It takes less time to ll numbers that high rather than tf.... I swear i saw some numbers up to 80 bit level. I could be mistaken and thats not important. I been going down to factoring projects and stuff and when i get to lookin at them i have no clue. There is a thread named fft explination for non math people(somethin like that, cant post link im on an ipod) either way a few posts down they start explaining i just get totally lost. Ive even read it slow a few times over and still dont get it. The same with all threads that start talkkng bout all the diff equations for diff problems. Last math class i took was 15 years ago in high school and i only went up to algebra 2. I guess all this factoring and such is higher than that.... And to be honest if it was in there i probably forgot. Should i just get a text book and start working through it? Calculus? I would like to know some of this stuff, but i dont wanna have to ask a question every post. Id like to be able to contribute. There's alot of projects on here but i have no. Clue whats going on... Does that make it ant clearer what im asking?

[Dubslow]

Originally Posted by Jellyfish420

Gotcha. It takes less time to ll numbers that high rather than tf.... I swear i saw some numbers up to 80 bit level. I could be mistaken and thats not important. I been going down to factoring projects and stuff and when i get to lookin at them i have no clue. There is a thread named fft explination for non math people(somethin like that, cant post link im on an ipod) either way a few posts down they start explaining i just get totally lost. Ive even read it slow a few times over and still dont get it. The same with all threads that start talkkng bout all the diff equations for diff problems. Last math class i took was 15 years ago in high school and i only went up to algebra 2. I guess all this factoring and such is higher than that.... And to be honest if it was in there i probably forgot. Should i just get a text book and start working through it? Calculus? I would like to know some of this stuff, but i dont wanna have to ask a question every post. Id like to be able to contribute. There's alot of projects on here but i have no. Clue whats going on... Does that make it ant clearer what im asking?

That's a bit better, yes. After Algebra 2 is usually some sort of trigonometry, then precalc and then calc. I'm quite sure sure how directly useful those would be to the sort of math done here -- but it would at least be higher level math than just algebra 2.

As for 80 bits, you probably have seen it. In the current LL range (exponents around 60M), you might see someone take an exponent to 74 or 75 bits TF -- 80 would be more or less impossible. In the 100 million digit range though, exponents around 332M, or exponents higher than that (like 900M -- PrimeNet tracks them up to 1B) you might see some higher TF levels, like 80 and beyond. It's a slightly counter intuitive (at first glance) fact that TFing a bit level gets easier with higher exponents -- it takes about half as long to TF a 100M exponent to 75 bits than a 50M exponent to 75 bits. For both this reason and the fact that a longer LL test means more TF required, means that these higher exponents are taken to higher bit levels. So you probably have seen an expo taken to 80 bits. Graph -- try zooming in.

[LaurV]

This might be a better link. Try clicking on rows. :P

[science_man_88]

Originally Posted by Jellyfish420

Basic overview.....i recently OCed my pc and started running P95 for stress. Thinking bout how big these numbers actually are and that 47 have ever been found has sparked my interest. I been doing LL tests on one core and TF on the other for bout 2weeks. Reading around on this forum. And i understand, to an extent, about what a mersenne prime is... But when people start talking bout different factors, and bit levels, and all the other good stuff i am totally lost. Ive searched around and i can find what stuff means but without a more basic knowledge the more advanced stuff really doesn't mean much. So after all that reading where do i start? Anyone got some links to some good reading? I need to learn the basics so i have something to build off of. Thank you to anyone that can help

Mersenne factors are of form 2*k*p+1 for 2^p-1 , p being a prime.

from this an example:

2^11-1 = 2047

2047/23 = 89

23=2*1*11+1
89=2*4*11+1

2047 = 2*93*11+1

[Jellyfish420]

Originally Posted by science_man_88

Mersenne factors are of form 2*k*p+1 for 2^p-1 , p being a prime.

from this an example:

2^11-1 = 2047

2047/23 = 89

23=2*1*11+1
89=2*4*11+1

2047 = 2*93*11+1

So where did 23 and 93 come from? Factors of 2047? So in LL tests its does all these calculations for every iteration? I just thought there was one equation that each number went in... Didnt realize there was a handfull..

Ok 23 is a factor. And 93 is k.... But what is k and why is k 3 different numbers? I guess thats what is throwing me off the most. I always thought that the number stayed the same throughout the problem. ie. p=11 everywhere there is a p ... But k=23, 89, & 93.