mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Lone Mersenne Hunters

Reply
 
Thread Tools
Old 2011-01-15, 16:33   #67
rajula
 
rajula's Avatar
 
"Tapio Rajala"
Feb 2010
Finland

32×5×7 Posts
Default

Quote:
Originally Posted by drh View Post
M51443083 has a factor: 25320591696138535897675469195834877349466521
25320591696138535897675469195834877349466521 = 857285347808257713679 x 29535780310340488803799

Quote:
I'm also assuming that this is composite since it is so large. I'm still very new at this, and learning. Can you tell me what you are doing, or using to tell if these numbers are composite or not?
One easy way is to use http://www.alpertron.com.ar/ECM.HTM.
rajula is offline   Reply With Quote
Old 2011-01-15, 23:39   #68
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by drh View Post
Can you tell me what you are doing, or using to tell if these numbers are composite or not?
A really neat trick is to use the P+1 method with the same bounds as the original P-1 test. This has a 50% chance per run of resolving the two factors, and will usually do so in a fraction of the processor time that other methods would take.

Code:
$ echo "25320591696138535897675469195834877349466521" | ecm -c 0 -pp1 60000
GMP-ECM 6.2 [powered by GMP 4.2.2] [P+1]
Input number is 25320591696138535897675469195834877349466521 (44 digits)
Using B1=60000, B2=19419970, polynomial x^1, x0=2552205880
Step 1 took 88ms
Step 2 took 96ms
Run 2 out of 0:
Using B1=60000, B2=19419970, polynomial x^1, x0=1936717407
Step 1 took 80ms
[factor found by P-1]
********** Factor found in step 2: 857285347808257713679
Found probable prime factor of 21 digits: 857285347808257713679
Probable prime cofactor 29535780310340488803799 has 23 digits
$
Not that other methods take much processor time, but I think this is a neat 'hack'.
Mr. P-1 is offline   Reply With Quote
Old 2011-01-16, 19:22   #69
drh
 
drh's Avatar
 
Jan 2011
Cincinnati, OH

22×52 Posts
Default

Just wanted to thank lorgix, Mr. P-1, and rajula for responding, and getting me started down the path of understanding, as I'm not a mathematician. I'm sure I'll have lots more questions.

Doug
drh is offline   Reply With Quote
Old 2011-01-16, 23:13   #70
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by drh View Post
Can you tell me what you are doing, or using to tell if these numbers are composite or not?
A simple heuristic is, if its size is more than double the TF limits, then it's almost certainly composite. P-1 (to the limits chosen by Prime95) rarely finds prime factors much more than about 100 bits, and rarely finds composite factors less than double the TF limits (since this would imply a missed TF-sized factor.)

The quickest way to prove these numbers composite would be a PrP test, which wouldn't tell us the prime factors. In practice, we don't bother, because we're interested in the prime factors anyway, and factoring them is so easy. Theoretically, if a large P-1 factor should resist factorisation for any length of time, we might begin to suspect it to be prime after all. To prove a number of that size prime, I'd use Pari/GP's isprime() function. There are several other tools capable of proving much larger numbers prime.

Last fiddled with by Mr. P-1 on 2011-01-16 at 23:13
Mr. P-1 is offline   Reply With Quote
Old 2011-01-17, 09:19   #71
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

3×5×41 Posts
Default

Another find thanks to Suyama's extension;

P-1 found a factor in stage #2, B1=85000, B2=1742500.
M2294807 has a factor: 4743377217925125644071

k= 3^3*5*751*3851*2647063

---

You're welcome drh! I'm learning too, heck we all are.

I usually use http://factordb.com/, that site stores the factor as well.

But all the other suggestions are great too.
lorgix is offline   Reply With Quote
Old 2011-01-17, 18:25   #72
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by lorgix View Post
Another find thanks to Suyama's extension;
E?
Mr. P-1 is offline   Reply With Quote
Old 2011-01-17, 18:31   #73
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

3·5·41 Posts
Default

Actually the output doesn't say.

But it always uses E=6 under similar (to the ones in question) circumstances.
lorgix is offline   Reply With Quote
Old 2011-01-17, 19:44   #74
drh
 
drh's Avatar
 
Jan 2011
Cincinnati, OH

6416 Posts
Default

From TF -

M80307593 has a factor: 144625571114343550097
drh is offline   Reply With Quote
Old 2011-01-17, 23:51   #75
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

22218 Posts
Default

Quote:
Originally Posted by lorgix View Post
Actually the output doesn't say.

But it always uses E=6 under similar (to the ones in question) circumstances.
That's curious. Normally it give the E value in the result.txt file, if it's higher than 2.

How many relative primes out of how many were you able to do per pass?
Mr. P-1 is offline   Reply With Quote
Old 2011-01-18, 08:07   #76
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

26716 Posts
Default

All 480 in one pass. 498MB.

I used to think the same. But it appears to me now that it doesn't do that if a factor is found.

More recent find below, where Suyama's extension wasn't needed. Still used E=6, but doesn't show it here for some reason.

P-1 found a factor in stage #2, B1=90000, B2=1755000.
M2299571 has a factor: 103653914718894079697
lorgix is offline   Reply With Quote
Old 2011-01-18, 08:12   #77
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

11478 Posts
Default

Close or what?

P-1 found a factor in stage #2, B1=95000, B2=1947500.
M2444359 has a factor: 1588994437060952149274017

k= 2^4*3*31*41*197*13901*1945487
lorgix is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Turn off GCC sse-using optimizations? ewmayer Programming 3 2016-09-30 07:15
AMD goes inane jasong jasong 18 2013-11-15 22:54
When I run PRIME95, my computer threatens to turn off Rafael Information & Answers 12 2012-01-02 19:38
A fond farewell rogue Lounge 10 2008-11-21 05:25
turn off your integrated Snd card in CMOS nngs Hardware 0 2005-05-20 01:31

All times are UTC. The time now is 13:24.

Sun Sep 20 13:24:56 UTC 2020 up 10 days, 10:35, 1 user, load averages: 1.76, 1.56, 1.48

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.