20030621, 00:40  #1 
Sep 2002
2·131 Posts 
Factoring from the factor1
in 2^P2 you allways have P as a factor
Let F the number to test first test if prime if so then N=F1 Find all factor S of N test if N  2^S1 wouldn`t 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. 
20030621, 02:49  #2 
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.
I`ll start my next run at 2^72 and see how it goes. I guess I`d be lucky to find one within the next day. 
20030621, 20:17  #3  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×599 Posts 
Re: Factoring from the factor1
Quote:
If you mean that F is a potential factor of 2^P1, then does your second algorithm line mean "Test whether F is prime"? Quote:


20030621, 22:46  #4 
Sep 2002
2·131 Posts 
Here is an exemple with M67
take M67  1 (2^672) all factors of this are: (2,3,3,7,23,67,89,683,20857,599479) so it contains 67 and it`s the same for all mersenne. It`s also the case with any prime numbers. take 193707721 the numbers that divides M67 the factors of 1937077211 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? 
20030622, 00:14  #5 
Jan 2003
far from M40
175_{8} Posts 
No, each prime is factor of at most one mersenne. See Will Edgington's Mersenne Page for a proof.
Benjamin 
20030622, 14:09  #6  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·599 Posts 
Quote:
Example: (2^111) * (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. 

20030622, 14:27  #7  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1C14_{16} Posts 
Quote:
That task, in general, is not faster than LucasLehmer. Sure, it's costeffective to use certain amounts of trial factoring, P1, and ECM to try to find factors of Mersenne numbers before performing the LL. 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 LL than by finding a factor. 

20030622, 15:45  #8 
Sep 2002
100000110_{2} 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. 
20030623, 00:16  #9 
Aug 2002
Portland, OR USA
112_{16} Posts 
One of your steps is "First test if prime",
Testing F for primality takes nearly as long as factoring F1. (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. [edit] updated version [/edit] I haven't ported it to c yet  incorporating any of the bigint 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 
20030623, 01:59  #10 
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. I`ll try and see if it`s faster without checking for primality. but my factoring of F1 is not very fast since I have to go up to 79.3M 
20030623, 20:04  #11 
Aug 2002
Portland, OR USA
2×137 Posts 
Are you factoring F1 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 = (f1) >> 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 primeexponent 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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New Factor of F11 (?)  ChriS  Factoring  3  20060529 17:57 
P56 ECM Factor  wblipp  Factoring  4  20050423 11:41 
use of factor? (just to be sure)  Ivan Semenov  Data  2  20040529 14:30 
P1 factoring != "Mersenne numbers to factor"?  James Heinrich  Marin's Mersennearies  8  20040517 11:09 
Shortest time to complete a 2^67 trial factor (no factor)  dsouza123  Software  12  20030821 18:38 