Factoring from the factor-1 - Page 2

ewmayer · 2003-06-23, 22:37

It's well-known that all prime-exponent Mersennes factorize as 2*k*p + 1. Any good Mersenne-specific implementation of the p-1 factoring method already exploits this fact, i.e. even if your stage bounds are < p, you always raise your p-1 seed to the p*{product of small prime powers}th power, since you know that p will divide any factor minus one.

jocelynl · 2003-06-27, 01:24

Sorry for the delay, I was off on holiday.

Today I tried a different approach. I find it no longer necessary to check for prp(probable prime) befor checking since it`s takes less time to check non primes also. But the main change is that I look for prime in an exponential curve. I base the increase on the average of the last 10 differences and start checking from there. I find about 90% of the factors. But the speed increase is worth the loss. I checked up to 2^32 in 30 seconds. Up to 2^34 in 1 hours. I`m still on 2^35. I`ll keep you up to date.

Joss

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New Factor of F11 (?)	ChriS	Factoring	3	2006-05-29 17:57
P56 ECM Factor	wblipp	Factoring	4	2005-04-23 11:41
use of factor? (just to be sure)	Ivan Semenov	Data	2	2004-05-29 14:30
P-1 factoring != "Mersenne numbers to factor"?	James Heinrich	Marin's Mersenne-aries	8	2004-05-17 11:09
Shortest time to complete a 2^67 trial factor (no factor)	dsouza123	Software	12	2003-08-21 18:38

2003-06-23, 22:37	#12
ewmayer ∂²ω=0 Sep 2002 República de California 103·113 Posts	It's well-known that all prime-exponent Mersennes factorize as 2kp + 1. Any good Mersenne-specific implementation of the p-1 factoring method already exploits this fact, i.e. even if your stage bounds are < p, you always raise your p-1 seed to the p*{product of small prime powers}th power, since you know that p will divide any factor minus one.

2003-06-27, 01:24	#13
jocelynl Sep 2002 2×131 Posts	Sorry for the delay, I was off on holiday. Today I tried a different approach. I find it no longer necessary to check for prp(probable prime) befor checking since it`s takes less time to check non primes also. But the main change is that I look for prime in an exponential curve. I base the increase on the average of the last 10 differences and start checking from there. I find about 90% of the factors. But the speed increase is worth the loss. I checked up to 2^32 in 30 seconds. Up to 2^34 in 1 hours. I`m still on 2^35. I`ll keep you up to date. Joss