20070515, 00:00  #1 
Feb 2007
2^{4}×3^{3} Posts 
Speeding up Mersenne hunting
This is an idea that occurred to me while looking at Tony's idea of "universal seeds":
It is known that if Mp=2^p1 is prime, then the "digraphs" for LL: x > x^22 on Z/(Mp), i.e. the set of graphs you obtain by connecting x to LL(x), has the following simple structure: 1. One large "reversed" tree of the form: fixed point { 2 } < 2 < 0 < +/ 2^((p+1)/2) .... (from here on it's a complete binary tree (i.e. each number has 2 ancestors), of total height p1, the leaves being the well known LL starting points 4,10 and 2^(p2)2 other values, which have no ancestor for LL) This tree contains (including 2 and 2 below the root 0) a total of M(p2)+2 = 2^(p1)+1 elements (i.e. half) of Z/(Mp) [remain 2^(p1)2 elements of Z/(Mp)] 2. the ridiculous cycle {1} of length 1 with its appendix 1, i.e. { 1 } < 1 (1 being the only other fixed point of LL) [remain 2^(p1)4 elements of Z/(Mp)] 3. a number of other cycles (i.e. { x > LL(x) > ... > LL^c(x) = x }) of length c=c(x)>1 dividing p1 ; each element of which having as second (and only other) ancestor the opposite of it's predecessor in the cycle, i.e. LL^1(x) = { +/ LL^(c1)(x) } e.g. in Z/(M5) = Z/31, Code:
(18) > 12 > 18 > (12) / / 18=13 12=19 plus the same number of "appendices" (their opposites). And that's all. Now the whole power of GIMPS is used to start with 4 and do p2 iterations to see if we end in 0: then M(p) is prime. However, > 99.9% percent of GIMPS work is not FINDING PRIME p, but REJECTING NONPRIME p. To do this, it is sufficient to show a contradiction with any of the facts given above, in particular: a) existence of a fixed point (f.p.) other than { 2, 1 } b) existence of a cycle with length not dividing p1 c) existence of an element x with "tail" t(x)>1 (number of iterations needed to land on a cycle), not going to {2} d) existence of an element having more than 2 ancestors, in particular: * any element other than 1 going to {1}, * any element not lying on a cycle, such that LL^(c(x))(x) <> x . as to (a) : If Mp is composite, then there are divisors of zero, i.e. fixed points x=LL(x) <=> (x2)(x+1)=0 other than 2 and 1. (They are given as x=3du1 where d runs over divisors of Mp and u is solution to u*d+v*(Mp)/d=1 for some v  at least if Mp is squarefree.) Also, there are "appendices" to elements of cycles which are trees bigger than 1. However, it seems as if the tail t(x) (# iterations to reach the cycle) is always *very* small, except for the tree(s) ending in fixed points. (I never found one longer than 4  which of course does not mean much). Anyway, my conclusion is that starting with 4 and blindly doing p2 iterations before checking if it gives 0 is about the worst one can do! The best would be to have a function f giving x=f(p) in Z_Mp which  for composite Mp, is likely to run into a cycle of length < p either not dividing p1, or having t(x)>1, or ending in a f.p.  for prime Mp, is on the big tree at known height (like 4 which is at height p2),  or, which is on a cycle of short length (< p/2) for prime Mp but not for nonprime Mp. But even if, missing such a formula, we start with /any/ value (except 2,1,0,1,2): we should store the value of s[T] for some T >= max{ t(x)  c(x)>1 } (unless the exact max, assumed to be VERY small, is known, take T comfortably larger), and compare s[k] to that s[T]  either each time (note that we don't need to compare the whole 8MB but starting from the least significant byte I suppose it does not take much time on the average to find a difference.)  or whenever kT divides p1 (this will be the case VERY rarely ; the latest "p" I got from primenet have about 20 divisors (of p1) on the average)  or whenever kT satisfies some other intelligent criterion (e.g. one finds that cycle lengths usually are To get around the "unknown T" problem, it is also conceivable to let T=k whenever k divides p1 or so (thus, for larger divisors, we would "lose" the preceding iterations, but be on the safer side of not missing a loop detection). Once again, to finish, let me give one very simplified version of my idea ; it is not what I believe the most efficient, but enough to speed up Mersenne hunting by a factor of 2, without storing anything and with only 1 comparision. * take a starting value x=f(p) such that, if Mp is prime, it will go to a cycle of any length 1 < c(x) < p1, then we know that Mp is NOT prime in AT MOST p/2 iterations. It seems clear to me that with some refinement, one can make much better. 
20070515, 08:19  #2 
Feb 2005
11·23 Posts 
I have a couple of comments:
1) Finding contradictions to "known facts" may be as hard as factoring Mp. In particular, you have shown that "fixed points x=LL(x) <=> (x2)(x+1)=0 other than 2 and 1", in which case gcd(x2,Mp) will give a nontrivial factor of Mp. Similarly, if L(x)=1 and x<>+1 then x^21=(x1)(x+1)=0 (mod Mp), giving a nontrivial factor gcd(x1,Mp). Therefore, this method seems to be equivalent (at least partially) to indirect factorization of Mp. But I do not see any single reason why it should by any simpler than direct factorization of Mp (e.g., with ECM). 2) When you discuss "existence of a cycle with length not dividing p1", why do you assume that its length will be smaller than p1? In general, the length of such cycle may be much larger (up to Mp) as compared to the maximum cycle length p1 for prime Mp. 
20070515, 12:46  #3  
Feb 2007
110110000_{2} Posts 
Quote:
Quote:
Thus, if after p/2 iterations we see we're NOT on a cycle, then Mp can NOT be prime. Quote:
Last fiddled with by m_f_h on 20070515 at 12:48 

20070515, 16:28  #4  
Feb 2004
France
927_{10} Posts 
Quote:
Quote:
T. 

20070515, 23:44  #5  
Feb 2007
1B0_{16} Posts 
Quote:
NO, I don't mean the lengthis smaller than that maximum! I DO mean that: IF ( we know that c(x)<p1 IF Mp is prime ) THEN : ( IF c(x) >= p/2 THEN Mp is not prime. ) or: (note that x=x(p), maybe  I wrote x=f(p) in the initial post, but omit it below to simplify) ( M(p) prime => c( x ) < p1 ) => ( c( x ) >= p/2 => M(p) not prime ) This is a plain logical contraposition, modulo the knowledge that for prime Mp, c(x)<p1 => c(x)<p/2. (that's why I dont put "<=>"). Last fiddled with by m_f_h on 20070515 at 23:51 

20070516, 03:38  #6  
Feb 2005
11·23 Posts 
Quote:
On the other hand, implication ( c( x ) >= p => M(p) not prime ) does not help to speed up anything, since in this case it will take at least the same amount of time as the standard LucasLehmer test. 

20070516, 07:21  #7  
Feb 2004
France
1637_{8} Posts 
Quote:
So, your algorithm supposes we can find a Universal Initial Value that generates cycles of length dividing (p1)/2 for Mersenne primes. I found something: 2^1+2^(p1) , but it produce cycles of length dividing (p1)/2 for Mersenne primes AND composites ... So, your algorithm depends on: 1) finding (par experiments) a "Universal Initial Value that generates cycles of length dividing (p1)/2 for Mersenne primes ONLY", and: 2) proving it. Right ? T. 

20070518, 13:24  #8  
Feb 2007
2^{4}×3^{3} Posts 
Maxal: Sorry for some reason I don't understand I did not see your mail earlier while I already saw Tony's reply. He understood now what I mean (but his conclusion is not 100% correct.)
not "why". I say "IF A, THEN B " where A is a proposition of the form P=>Q. Quote:
Tony: > So, your algorithm depends on: > 1) finding (...) of length dividing (p1)/2 for Mersenne primes ONLY" > 2) proving it. > Right ? Not exactly. For "my" or rather "this" algorithm (as I said, this is a very (over) simplified version of my true idea) to "work" (i.e. to make better than LL for NONprimality(!) proving), it is sufficient that the value x=f(p) has c(x)<p1 AT LEAST for prime Mp, and some probability epsilon >0 for c(x) not dividing p1 if Mp is composite. If I recall correctly, your value 2+2^(p1) is equivalent to my x[p] := 3*2^[p/2] (this one has LL(x[p]) = 32^(p1) = your value mod Mp (?)) Other values of this cycle include 2^(p2)+4, 2^(p4)+16, etc. (PS: did you notice that all elements of this cycle are even if one takes the representatives in [0,Mp) ? I think it is the only cycle (except {2}) which has this property, at least for prime Mp.) Unfortunately, for p=5 this is the only cycle (+/{12,13}) of length < 4... (well, there are only 2 nontrivial cycles in Z_M5....) PS: Tony: I hope you're not too deceived by Sarko's deputies ;) Last fiddled with by m_f_h on 20070518 at 13:34 Reason: +comment on only cycle with all elements even 

20070518, 13:49  #9 
Feb 2007
2^{4}×3^{3} Posts 
Well, everybody agrees that it remains to find a nice x...
One might study if a random x, maybe rejecting obvious "very bad choices", might not do the job. The main problem is to avoid, in case Mp would be prime, * the Mp/4 elements on leaves of the tree, which need p2 iterations to go to 0 * the elements lying on the cycle(s) of length p1, and their oppose. (I agree there are many...) If we manage to find this (and assuming that with a random x the chance of falling on the special cycle of length [p/2] are "negligable"), we have a better method. Apart from that, I'd like to complete a previously given formula, to use equivalences rather than implications ; it maybe avoids misunderstandings. ( M(p) prime => c( x ) < p1 ) <=> ( M(p) prime => c( x ) < p/2 ) <=> ( c( x ) >= p/2 => M(p) not prime ) <=> ( c( x ) > p/2 => M(p) not prime ) /* for odd p */ PS: and once again, to avoid misunderstandings, the above does NOT say that ( M(p) prime => c( x ) < p1 ) is true. It says to what this is equivalent. Only if we have an x for which it IS true, then all of the three lines are true, FOR THAT x. Last fiddled with by m_f_h on 20070518 at 14:04 Reason: added PS to avoid misunderstandings 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Speeding up (n mod m) for very large fixed n and varying smaller m  mickfrancis  Computer Science & Computational Number Theory  9  20160329 19:00 
i56400 vs 6600 (for prime hunting)  Fred  Hardware  17  20160208 19:37 
Speeding up 321  diep  Math  8  20121204 15:32 
Goldbach's Conjecture: Hunting Counterexamples  Christenson  Math  19  20110907 01:44 
Speeding up ECM 10x  clowns789  Software  2  20040811 03:45 