mersenneforum.org fond of a factor? Turn yourself in to become inane
 Register FAQ Search Today's Posts Mark Forums Read

2011-01-15, 16:33   #67
rajula

"Tapio Rajala"
Feb 2010
Finland

32×5×7 Posts

Quote:
 Originally Posted by drh 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.

2011-01-15, 23:39   #68
Mr. P-1

Jun 2003

7×167 Posts

Quote:
 Originally Posted by drh 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'.

 2011-01-16, 19:22 #69 drh     Jan 2011 Cincinnati, OH 22×52 Posts 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
2011-01-16, 23:13   #70
Mr. P-1

Jun 2003

7×167 Posts

Quote:
 Originally Posted by drh 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

 2011-01-17, 09:19 #71 lorgix     Sep 2010 Scandinavia 3×5×41 Posts 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.
2011-01-17, 18:25   #72
Mr. P-1

Jun 2003

7×167 Posts

Quote:
 Originally Posted by lorgix Another find thanks to Suyama's extension;
E?

 2011-01-17, 18:31 #73 lorgix     Sep 2010 Scandinavia 3·5·41 Posts Actually the output doesn't say. But it always uses E=6 under similar (to the ones in question) circumstances.
 2011-01-17, 19:44 #74 drh     Jan 2011 Cincinnati, OH 6416 Posts From TF - M80307593 has a factor: 144625571114343550097
2011-01-17, 23:51   #75
Mr. P-1

Jun 2003

22218 Posts

Quote:
 Originally Posted by lorgix 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?

 2011-01-18, 08:07 #76 lorgix     Sep 2010 Scandinavia 26716 Posts 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
 2011-01-18, 08:12 #77 lorgix     Sep 2010 Scandinavia 11478 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post ewmayer Programming 3 2016-09-30 07:15 jasong jasong 18 2013-11-15 22:54 Rafael Information & Answers 12 2012-01-02 19:38 rogue Lounge 10 2008-11-21 05:25 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