mersenneforum.org > Math Factoring from the factor-1
 Register FAQ Search Today's Posts Mark Forums Read

 2003-06-21, 00:40 #1 jocelynl   Sep 2002 2·131 Posts Factoring from the factor-1 in 2^P-2 you allways have P as a factor Let F the number to test first test if prime if so then N=F-1 Find all factor S of N test if N | 2^S-1 wouldnt that be faster than to go about than try to divide one mersenne by all primes. You only have a few to test for each factor. So when you get to 2^64 you have found all factor less than 2^64 for all Mersenne.
 2003-06-21, 02:49 #2 jocelynl   Sep 2002 2×131 Posts I Tried it up to 2^32 and found all mersenne factor(less then 2^32) up to 79M in less then 10 minutes. I know this is low but it works no matter where you start. 2^100, 2^150 but these are very rare. Ill start my next run at 2^72 and see how it goes. I guess Id be lucky to find one within the next day.
2003-06-21, 20:17   #3

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Re: Factoring from the factor-1

Quote:
 Originally Posted by jocelynl in 2^P-2 you allways have P as a factor Let F the number to test first test if prime if so then N=F-1 Find all factor S of N test if N | 2^S-1
Could you more precisely define your variables F and S in terms of P?

If you mean that F is a potential factor of 2^P-1, then does your second algorithm line mean "Test whether F is prime"?

Quote:
 You only have a few to test for each factor.
A few what to test?

 2003-06-21, 22:46 #4 jocelynl   Sep 2002 2·131 Posts Here is an exemple with M67 take M67 - 1 (2^67-2) all factors of this are: (2,3,3,7,23,67,89,683,20857,599479) so it contains 67 and its the same for all mersenne. Its also the case with any prime numbers. take 193707721 the numbers that divides M67 the factors of 193707721-1 are (2,2,2,3,3,3,5,67,2677) so you know you only have to test M67 and M2677. and since we are only concerned with numbers less then 79.3M there no need to search all factors of the number. You can also include the properties of mersenne numbers to speed up the process. Can a prime numbers be the factor of more than one Mersenne?
 2003-06-22, 00:14 #5 S80780   Jan 2003 far from M40 1758 Posts No, each prime is factor of at most one mersenne. See Will Edgington's Mersenne Page for a proof. Benjamin
2003-06-22, 14:09   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts

Quote:
 Originally Posted by S80780 No, each prime is factor of at most one mersenne. See Will Edgington's Mersenne Page for a proof.
Correction: Each prime is a factor of at most one prime-exponent Mersenne.

Example: (2^11-1) * (2^11+1) = 2^22 - 1. Any prime factor of M11 is also a factor of M22 and of any other M(n*11) for integral n.

2003-06-22, 14:27   #7

"Richard B. Woods"
Aug 2002
Wisconsin USA

1C1416 Posts

Quote:
 Originally Posted by jocelynl take M67 - 1 (2^67-2) all factors of this are: (2,3,3,7,23,67,89,683,20857,599479) so it contains 67 and its the same for all mersenne.
So, are you saying your method of finding factors of Mersenne numbers requires completely factoring (Mersenne number - 1) in each case?

That task, in general, is not faster than Lucas-Lehmer. Sure, it's cost-effective to use certain amounts of trial factoring, P-1, and ECM to try to find factors of Mersenne numbers before performing the L-L. But for any large Mersenne number, those certain points take us only a small fraction of the way through all possible factors. Beyond those points (which differ according to the particular method), it is faster to prove a Mersenne number composite by L-L than by finding a factor.

 2003-06-22, 15:45 #8 jocelynl   Sep 2002 1000001102 Posts I know that trial factoring is very fast but this is only one way of finding very large factors. I was trying to show that one prime number could be test for Mersenne that we might able to test it for others like Fermat, Woodall, etc... I know that work has been done on this before, but old idea can sometime help others find new ones. After 1 day and 12000 primes tried at 2^72 nothing yet.
 2003-06-23, 00:16 #9 Maybeso     Aug 2002 Portland, OR USA 11216 Posts One of your steps is "First test if prime", Testing F for primality takes nearly as long as factoring F-1. (depending on how you do it.) If you're not using primegen to generate each F, I've modified the Atkins algorithm to generate primes +/-1 (mod 8 ), which are the ones you want. There's a javascript demo version on Yahoo's prime numbers group: P17mod8.html -- just click view/source.  updated version [/edit] I haven't ported it to c yet -- incorporating any of the big-int libraries has me stumped, but once it is, it should be 3x the speed of primegen. So you'll have to dig in the core functions for the logic. Are you already using a lib to get above 2^64? Bruce
 2003-06-23, 01:59 #10 jocelynl   Sep 2002 2×131 Posts Yes I use several method like 1 or 7 mod 8 so we remove 3 or 5 and we also remove 1 mod 12. Ill try and see if its faster without checking for primality. but my factoring of F-1 is not very fast since I have to go up to 79.3M
 2003-06-23, 20:04 #11 Maybeso     Aug 2002 Portland, OR USA 2×137 Posts Are you factoring F-1 completely before testing candidates with powermod? Alex Kruppa & I used the following to try and balance time spent factoring against time spent on powermod. [code:1]unsigned int ismersfac(unsigned int f) { unsigned int fm1 = (f-1) >> 1; unsigned int p, d; int earlyout = 0; if (f == 3) return 2; if (f == 7) return 3; if (f == 31) return 5; while ((fm1 & 1) == 0) { fm1 >>= 1; earlyout = 1; } while (fm1 % 3 == 0) { fm1 /= 3; earlyout = 1; } while (fm1 % 5 == 0) { fm1 /= 5; earlyout = 1; } if (earlyout && pow2mod(fm1, f) != 1) return 0; for (p = 7, d = 1; p*p <= fm1; p += mod30diff[d], d = (d+1)&7) { if (fm1 % p == 0) { if (pow2mod(p, f) == 1) return p; while (fm1 % p == 0) fm1 /= p; if (pow2mod(fm1, f) != 1) return 0; } } if (pow2mod(fm1, f) == 1) return fm1; return 0; } [/code:1] The 2,3,5 earlyout sieving could be continued until p > log2(fm1), since F can't be a factor of a smaller prime-exponent mersenne. My demo program took less than 10 seconds to generate the 3320+ primes +-1 mod 8 in a 172800 wide block at 515396390401. Which is pretty good for javascript. Of course, that is at 2982618 * 172800 using 32 bit vars, and you're at 27328509738828965 * 172800, so it *may* ;) slow down a bit more. But since the difference between Atkins and regular sieving increases with F, I don't think you can check the primality of 23000 F values quicker. If you don't want to port my code into yours, I would strongly suggest you use something similar to my function filter() to sieve a large block of F values at once. (I filter out q = k*p^2, you want q = k*p.) Bruce

 Similar Threads Thread Thread Starter Forum Replies Last Post ChriS Factoring 3 2006-05-29 17:57 wblipp Factoring 4 2005-04-23 11:41 Ivan Semenov Data 2 2004-05-29 14:30 James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09 dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 00:43.

Wed Oct 28 00:43:39 UTC 2020 up 47 days, 21:54, 2 users, load averages: 1.96, 2.12, 1.97