mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-05-15, 00:00   #1
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default 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.
m_f_h is offline   Reply With Quote
Old 2007-05-15, 08:19   #2
maxal
 
maxal's Avatar
 
Feb 2005

11·23 Posts
Default

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.
maxal is offline   Reply With Quote
Old 2007-05-15, 12:46   #3
m_f_h
 
m_f_h's Avatar
 
Feb 2007

1101100002 Posts
Default

Quote:
Originally Posted by maxal View Post
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
m_f_h is offline   Reply With Quote
Old 2007-05-15, 16:28   #4
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

92710 Posts
Default

Quote:
Originally Posted by maxal View Post
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 View Post
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.
T.Rex is offline   Reply With Quote
Old 2007-05-15, 23:44   #5
m_f_h
 
m_f_h's Avatar
 
Feb 2007

1B016 Posts
Unhappy

Quote:
Originally Posted by T.Rex View Post
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
m_f_h is offline   Reply With Quote
Old 2007-05-16, 03:38   #6
maxal
 
maxal's Avatar
 
Feb 2005

11·23 Posts
Default

Quote:
Originally Posted by m_f_h View Post
( 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.
maxal is offline   Reply With Quote
Old 2007-05-16, 07:21   #7
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16378 Posts
Default

Quote:
Originally Posted by m_f_h View Post
* 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 ...

So, your algorithm depends on:
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.
T.Rex is offline   Reply With Quote
Old 2007-05-18, 13:24   #8
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

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 View Post
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
m_f_h is offline   Reply With Quote
Old 2007-05-18, 13:49   #9
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

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
m_f_h is offline   Reply With Quote
Reply

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 2016-03-29 19:00
i5-6400 vs 6600 (for prime hunting) Fred Hardware 17 2016-02-08 19:37
Speeding up 321 diep Math 8 2012-12-04 15:32
Goldbach's Conjecture: Hunting Counterexamples Christenson Math 19 2011-09-07 01:44
Speeding up ECM 10x 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 ς𝜍 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔