mersenneforum.org  

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

Reply
 
Thread Tools
Old 2003-06-21, 00:40   #1
jocelynl
 
Sep 2002

2·131 Posts
Default 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

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.
jocelynl is offline   Reply With Quote
Old 2003-06-21, 02:49   #2
jocelynl
 
Sep 2002

2×131 Posts
Default

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.
jocelynl is offline   Reply With Quote
Old 2003-06-21, 20:17   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default 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?
cheesehead is offline   Reply With Quote
Old 2003-06-21, 22:46   #4
jocelynl
 
Sep 2002

2·131 Posts
Default

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 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 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?
jocelynl is offline   Reply With Quote
Old 2003-06-22, 00:14   #5
S80780
 
Jan 2003
far from M40

1758 Posts
Default

No, each prime is factor of at most one mersenne. See Will Edgington's Mersenne Page for a proof.

Benjamin
S80780 is offline   Reply With Quote
Old 2003-06-22, 14:09   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2003-06-22, 14:27   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1C1416 Posts
Default

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 it`s 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.
cheesehead is offline   Reply With Quote
Old 2003-06-22, 15:45   #8
jocelynl
 
Sep 2002

1000001102 Posts
Default

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.
jocelynl is offline   Reply With Quote
Old 2003-06-23, 00:16   #9
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

11216 Posts
Default

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. [edit] 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
Maybeso is offline   Reply With Quote
Old 2003-06-23, 01:59   #10
jocelynl
 
Sep 2002

2×131 Posts
Default

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 F-1 is not very fast since I have to go up to 79.3M
jocelynl is offline   Reply With Quote
Old 2003-06-23, 20:04   #11
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2×137 Posts
Default

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

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.