Feature request: p+1 factorization

alpertron · 2005-11-24, 13:04

I would like to see p+1 factorization in some future release of Prime95. The programming should not be difficult since it is similar to p-1 in many aspects, and the duplication of the index is already programmed for the Lucas-Lehmer test. The step 1 could be performed about 30% faster than the naive method shown at the page linked by using Montgomery's PRAC algorithm

This would require twice the memory of p-1 and it would be slightly slower than p-1, but we can find some factors using p+1 that would be useful for LMH.

ewmayer · 2005-11-24, 19:29

Well, it's of course up to George whether he does this, but at least for Mersennes p+1 is very likely not worth the effort because:

1) The special form of factors of M(p) makes p-1 much more likely to succeed for any given smoothness bounds;

2) Statistically speaking, on average half the times you do a "p+1" run you end up doing p-1 anyway (and probably less efficiently than doing a straight p-1 run would have been) - that's one of the intrinsic properties of the p+1 method.

alpertron · 2005-11-24, 20:08

You are right in both points, but even doing it twice with different parameters (so it has a 75% of success if p+1 is smooth) it is still faster than performing an ECM curve with the same bounds. ECM also has the same smoothness problem like p+1 so it cannot be used for LMH.

I think that p+1 can find some new factors (but with a productivity of about half of p-1).

2005-11-24, 13:04	#1
alpertron Aug 2002 Buenos Aires, Argentina 2×683 Posts	Feature request: p+1 factorization I would like to see p+1 factorization in some future release of Prime95. The programming should not be difficult since it is similar to p-1 in many aspects, and the duplication of the index is already programmed for the Lucas-Lehmer test. The step 1 could be performed about 30% faster than the naive method shown at the page linked by using Montgomery's PRAC algorithm This would require twice the memory of p-1 and it would be slightly slower than p-1, but we can find some factors using p+1 that would be useful for LMH.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Feature request	tcharron	Software	3	2018-10-03 20:08
Feature request	axn	Forum Feedback	15	2017-06-03 16:38
v5.0 Feature Request	Bent	PrimeNet	2	2008-12-07 23:22
Feature Request	Uncwilly	Software	0	2008-03-06 21:07
Feature request	JuanTutors	Software	2	2005-07-04 22:02

2005-11-24, 19:29	#2
ewmayer ∂²ω=0 Sep 2002 República de California 19·613 Posts	Well, it's of course up to George whether he does this, but at least for Mersennes p+1 is very likely not worth the effort because: 1) The special form of factors of M(p) makes p-1 much more likely to succeed for any given smoothness bounds; 2) Statistically speaking, on average half the times you do a "p+1" run you end up doing p-1 anyway (and probably less efficiently than doing a straight p-1 run would have been) - that's one of the intrinsic properties of the p+1 method.

2005-11-24, 20:08	#3
alpertron Aug 2002 Buenos Aires, Argentina 2×683 Posts	You are right in both points, but even doing it twice with different parameters (so it has a 75% of success if p+1 is smooth) it is still faster than performing an ECM curve with the same bounds. ECM also has the same smoothness problem like p+1 so it cannot be used for LMH. I think that p+1 can find some new factors (but with a productivity of about half of p-1).