 mersenneforum.org > Math Speeding up Mersenne hunting
 Register FAQ Search Today's Posts Mark Forums Read 2007-05-15, 00:00 #1 m_f_h   Feb 2007 24×33 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^p-1 is prime, then the "digraphs" for LL: x -> x^2-2 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 p-1, the leaves being the well known LL starting points 4,10 and 2^(p-2)-2 other values, which have no ancestor for LL) This tree contains (including 2 and -2 below the root 0) a total of M(p-2)+2 = 2^(p-1)+1 elements (i.e. half) of Z/(Mp) [remain 2^(p-1)-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^(p-1)-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 p-1 ; 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^(c-1)(x) } e.g. in Z/(M5) = Z/31, Code: (18) -> 12 -> 18 -> (12) / / -18=13 -12=19 There are a total of (2^(p-1)-4)/2 = 2 M(p-3) elements ON these cycles, 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 p-2 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 NON-PRIME 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 p-1 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) <=> (x-2)(x+1)=0 other than 2 and -1. (They are given as x=3du-1 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 square-free.) 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 p-2 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 p-1, 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 p-2), - or, which is on a cycle of short length (< p/2) for prime Mp but not for non-prime 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 k-T divides p-1 (this will be the case VERY rarely ; the latest "p" I got from primenet have about 20 divisors (of p-1) on the average) - or whenever k-T 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 p-1 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) < p-1, 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.   2007-05-15, 08:19 #2 maxal   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) <=> (x-2)(x+1)=0 other than 2 and -1", in which case gcd(x-2,Mp) will give a non-trivial factor of Mp. Similarly, if L(x)=-1 and x<>+-1 then x^2-1=(x-1)(x+1)=0 (mod Mp), giving a non-trivial factor gcd(x-1,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 p-1", why do you assume that its length will be smaller than p-1? In general, the length of such cycle may be much larger (up to Mp) as compared to the maximum cycle length p-1 for prime Mp.   2007-05-15, 12:46   #3
m_f_h

Feb 2007

1101100002 Posts Quote:
 Originally Posted by maxal 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) <=> (x-2)(x+1)=0 other than 2 and -1", in which case gcd(x-2,Mp) will give a non-trivial factor of Mp. Similarly, if L(x)=-1 and x<>+-1 then x^2-1=(x-1)(x+1)=0 (mod Mp), giving a non-trivial factor gcd(x-1,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).
Of course I agree and I understood this before - I certainly did not mean to /search/ for fixed points, and again, I agree that the chances of "running into" a nontrivial f.p. are quite feable (maybe about 1 in a million, if one takes into account that {-1} and other f.p. have a small tree with more than 1 element attached to them.).
Quote:
 2) When you discuss "existence of a cycle with length not dividing p-1", why do you assume that its length will be smaller than p-1?
Once again: IF Mp is prime, the length divides p-1 and thus < p-1 is equivalent to say < p/2.
Thus, if after p/2 iterations we see we're NOT on a cycle, then Mp can NOT be prime.
Quote:
 In general, the length of such cycle may be much larger (up to Mp) ...
No, the cycle length must be smaller than Mp/4. (But of course this is useless.)

Last fiddled with by m_f_h on 2007-05-15 at 12:48   2007-05-15, 16:28   #4
T.Rex

Feb 2004
France

92710 Posts Quote:
 Originally Posted by maxal 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).
Remember the rho-pollard method, which can find small factors. Though it says that x^2-2 is not appropriate ..., the method is close to using the LLT for finding a cycle.
Quote:
 Originally Posted by maxal why do you assume that its length will be smaller than p-1? In general, the length of such cycle may be much larger (up to Mp) as compared to the maximum cycle length p-1 for prime Mp.
When Mp is not prime, the length of cycles can be greater than p-1. m_f_h simply thinks that the upper bound is Mp/4, smaller than the maximum (Mp).
T.   2007-05-15, 23:44   #5
m_f_h

Feb 2007

1B016 Posts Quote:
 Originally Posted by T.Rex When Mp is not prime, the length of cycles can be greater than p-1. m_f_h simply thinks that the upper bound is Mp/4, smaller than the maximum (Mp).
Help, nobody understands me !
NO, I don't mean the lengthis smaller than that maximum!
I DO mean that:

IF ( we know that c(x)<p-1 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 ) < p-1 )
=>
( c( x ) >= p/2 => M(p) not prime )

This is a plain logical contraposition, modulo the knowledge that for prime Mp, c(x)<p-1 => c(x)<p/2. (that's why I dont put "<=>").

Last fiddled with by m_f_h on 2007-05-15 at 23:51   2007-05-16, 03:38   #6
maxal

Feb 2005

11·23 Posts Quote:
 Originally Posted by m_f_h ( M(p) prime => c( x ) < p-1 ) => ( c( x ) >= p/2 => M(p) not prime )
Why "c(x) < p-1" for prime M(p)? It may happen that c(x)=p-1. If so, the second implication does not hold.
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 Lucas-Lehmer test.   2007-05-16, 07:21   #7
T.Rex

Feb 2004
France

16378 Posts Quote:
 Originally Posted by m_f_h * 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) < p-1, then we know that Mp is NOT prime in AT MOST p/2 iterations.
Shallit&Vasiga said: If Mp is prime, then the length L of cycles divides p-1, meaning that L can be: 1, 2, ..., (p-1)/2, AND p-1 .

So, your algorithm supposes we can find a Universal Initial Value that generates cycles of length dividing (p-1)/2 for Mersenne primes. I found something: 2^1+2^(p-1) , but it produce cycles of length dividing (p-1)/2 for Mersenne primes AND composites ...

1) finding (par experiments) a "Universal Initial Value that generates cycles of length dividing (p-1)/2 for Mersenne primes ONLY", and:
2) proving it.
Right ?

T.   2007-05-18, 13:24   #8
m_f_h

Feb 2007

24×33 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.)
Quote:
 Originally Posted by maxal Why "c(x) < p-1" for prime M(p)?
not "why".
I say "IF A, THEN B " where A is a proposition of the form P=>Q.
Quote:
 It may happen that c(x)=p-1. If so, the second implication does not hold. On the other hand, implication ( c( x ) >= p => M(p) not prime ) does not help to speed up anything.
Of course, but I did not put "p" but "p/2" - on purpose.

Tony:
> So, your algorithm depends on:
> 1) finding (...) of length dividing (p-1)/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 NON-primality(!) proving), it is sufficient that
the value x=f(p) has c(x)<p-1 AT LEAST for prime Mp,
and some probability epsilon >0 for c(x) not dividing p-1 if Mp is composite.

If I recall correctly, your value 2+2^(p-1) is equivalent to my x[p] := 3*2^[p/2]
(this one has LL(x[p]) = 3-2^(p-1) = your value mod Mp (?))
Other values of this cycle include 2^(p-2)+4, 2^(p-4)+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 2007-05-18 at 13:34 Reason: +comment on only cycle with all elements even   2007-05-18, 13:49 #9 m_f_h   Feb 2007 24×33 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 p-2 iterations to go to 0 * the elements lying on the cycle(s) of length p-1, 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 ) < p-1 ) <=> ( 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 ) < p-1 ) 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 2007-05-18 at 14:04 Reason: added PS to avoid misunderstandings  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Computer Science & Computational Number Theory 9 2016-03-29 19:00 Fred Hardware 17 2016-02-08 19:37 diep Math 8 2012-12-04 15:32 Christenson Math 19 2011-09-07 01:44 clowns789 Software 2 2004-08-11 03:45

All times are UTC. The time now is 05:38.

Mon May 16 05:38:19 UTC 2022 up 32 days, 3:39, 0 users, load averages: 2.04, 1.53, 1.40