20130102, 20:36  #1 
Jan 2013
19 Posts 
Where to start
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

20130102, 22:55  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
16035_{8} Posts 
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^p1 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 highlyoptimized 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^p1 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^p1. (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^p1 has no factors less than 2^59, or alternately, we say that 2^p1 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^p1 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 P1 ("p minus 1") factoring, but that works differently from TF.) (PS @chalsall: Something's wrong in the 33M34M region of the graphs.) Last fiddled with by Dubslow on 20130102 at 22:57 
20130103, 00:47  #3 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2·4,441 Posts 
Poke around on the Wiki, here is a good page to start on: http://mersennewiki.org/index.php/Category:GIMPS_FAQ

20130103, 01:57  #4 
Jan 2013
19 Posts 
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...

20130103, 01:59  #5 
If I May
"Chris Halsall"
Sep 2002
Barbados
5^{2}×373 Posts 

20130103, 02:48  #6  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×2,399 Posts 
Quote:
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^732^74 takes twice as much work as TFing 7273.) 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 7273 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. 

20130103, 03:16  #7 
Jan 2013
19 Posts 
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?

20130103, 05:30  #8  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×2,399 Posts 
Quote:
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. 

20130103, 13:47  #10  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
from this an example: 2^111 = 2047 2047/23 = 89 23=2*1*11+1 89=2*4*11+1 2047 = 2*93*11+1 

20130103, 16:41  #11  
Jan 2013
19 Posts 
Quote:
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. Last fiddled with by Jellyfish420 on 20130103 at 16:50 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where should I start?  christian_  Information & Answers  9  20160122 19:28 
Before you start...  jasonp  Operation Kibibit  65  20130903 22:06 
How to start?  Thomas11  Lone Mersenne Hunters  29  20081221 13:47 
how to start with P1?  ValerieVonck  Marin's Mersennearies  8  20060429 22:21 
How to start?  OmbooHankvald  Factoring  15  20050903 13:42 