 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Factoring from the factor-1 (https://www.mersenneforum.org/showthread.php?t=712)

 jocelynl 2003-06-21 00:40

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 2003-06-21 02:49

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.

Re: Factoring from the factor-1

[quote="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[/quote]
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.[/quote]
A few [i]what[/i] to test?

 jocelynl 2003-06-21 22:46

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?

 S80780 2003-06-22 00:14

No, each prime is factor of at most one mersenne. See [url=http://www.garlic.com/~wedgingt/mersenne.html]Will Edgington's Mersenne Page[/url] for a proof.

Benjamin

[quote="S80780"]No, each prime is factor of at most one mersenne. See [url=http://www.garlic.com/~wedgingt/mersenne.html]Will Edgington's Mersenne Page[/url] for a proof.[/quote]
Correction: Each prime is a factor of at most one [b]prime-exponent[/b] 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.

[quote="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.[/quote]
So, are you saying your method of finding factors of Mersenne numbers requires completely factoring (Mersenne number - 1) in each case?

[u]That[/u] task, in general, is [u]not[/u] 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.

 jocelynl 2003-06-22 15:45

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.

 Maybeso 2003-06-23 00:16

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: [url=http://groups.yahoo.com/group/primenumbers/files/FactoringPrograms/P17mod8.html]P17mod8.html[/url] -- just click view/source.  updated version [/edit]

I haven't ported it to [b]c[/b] 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

 jocelynl 2003-06-23 01:59

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

 Maybeso 2003-06-23 20:04

Are you factoring F-1 completely before testing candidates with powermod? Alex Kruppa &amp; 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 &amp; 1) == 0) { fm1 >>= 1; earlyout = 1; }
while (fm1 % 3 == 0) { fm1 /= 3; earlyout = 1; }
while (fm1 % 5 == 0) { fm1 /= 5; earlyout = 1; }
if (earlyout &amp;&amp; pow2mod(fm1, f) != 1) return 0;

for (p = 7, d = 1; p*p &lt;= fm1; p += mod30diff[d], d = (d+1)&amp;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 [b]increases [/b]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

All times are UTC. The time now is 05:01.