20210525, 12:18  #1 
Aug 2020
79*6581e4;3*2539e3
2·211 Posts 
36 digits factor found with 5@11e3
This just happened: :D
Code:
>> fac: factoring 806356762568382460200879316696793327418130624871374647321550096097097503013220765541420108836088301525674014325593933853460499052214392622383079153369572706890268028646894251 fac: using pretesting plan: normal fac: using tune info for qs/gnfs crossover div: primes less than 10000 fmt: 1000000 iterations rho: x^2 + 3, starting 1000 iterations on C174 rho: x^2 + 2, starting 1000 iterations on C174 rho: x^2 + 1, starting 1000 iterations on C174 pm1: starting B1 = 150K, B2 = gmpecm default on C174 fac: setting target pretesting digits to 53.54 fac: sum of completed work is t0.00 fac: work done at B1=2000: 0 curves, max work = 30 curves fac: 30 more curves at B1=2000 needed to get to t53.54 ecm: 30/30 curves on C174, B1=2K, B2=gmpecm default fac: setting target pretesting digits to 53.54 fac: t15: 1.00 fac: t20: 0.04 fac: sum of completed work is t15.18 fac: work done at B1=11000: 0 curves, max work = 74 curves fac: 74 more curves at B1=11000 needed to get to t53.54 ecm: 5/74 curves on C174, B1=11K, B2=gmpecm default ecm: found c36 factor = 440152471934945015138192794987703257 
20210525, 12:50  #2  
Apr 2020
547 Posts 
Quote:
Your c36 factors as p17 * p20. Let p be the probability that a single curve at B1=11000 finds p17, and q the probability that it finds p20. Then the probability of finding at least one of the factors on a given curve is p+qpq. The probability of finding both p17 and p20 is pq. So the probability that both factors are first found on the same curve is pq/(p+qpq), which comes out as around 1 in 127 for this particular example. Last fiddled with by charybdis on 20210525 at 12:50 

20210525, 13:06  #3  
"Ben"
Feb 2007
3·1,193 Posts 
Quote:
Code:
05/25/21 08:03:06, **************************** 05/25/21 08:03:06, Starting factorization of 806356762568382460200879316696793327418130624871374647321550096097097503013220765541420108836088301525674014325593933853460499052214392622383079153369572706890268028646894251 05/25/21 08:03:06, using pretesting plan: deep 05/25/21 08:03:06, no tune info: using qs/gnfs crossover of 100 digits 05/25/21 08:03:06, no tune info: using qs/snfs crossover of 75 digits 05/25/21 08:03:06, **************************** 05/25/21 08:03:06, rho: x^2 + 3, starting 1000 iterations on C174 05/25/21 08:03:07, rho: x^2 + 2, starting 1000 iterations on C174 05/25/21 08:03:07, rho: x^2 + 1, starting 1000 iterations on C174 05/25/21 08:03:07, pm1: starting B1 = 150K, B2 = gmpecm default on C174 05/25/21 08:03:07, current ECM pretesting depth: 0.00 05/25/21 08:03:07, scheduled 30 curves at B1=2000 toward target pretesting depth of 58.00 05/25/21 08:03:08, Finished 30 curves using GMPECM method on C174 input, B1=2k, B2=gmpecm default 05/25/21 08:03:08, current ECM pretesting depth: 15.18 05/25/21 08:03:08, scheduled 74 curves at B1=11000 toward target pretesting depth of 58.00 05/25/21 08:03:08, prp17 = 14725232912672749 (curve 2 stg1 B1=11000 sigma=3953191221 thread=0) 05/25/21 08:03:08, Finished 1 curves using GMPECM method on C174 input, B1=11k, B2=gmpecm default 05/25/21 08:03:08, current ECM pretesting depth: 15.25 05/25/21 08:03:08, scheduled 73 curves at B1=11000 toward target pretesting depth of 52.67 05/25/21 08:03:10, prp21 = 144271075053970988861 (curve 29 stg2 B1=11000 sigma=3180447036 thread=0) 05/25/21 08:03:10, Finished 28 curves using GMPECM method on C158 input, B1=11k, B2=gmpecm default 05/25/21 08:03:10, current ECM pretesting depth: 17.14 05/25/21 08:03:10, scheduled 45 curves at B1=11000 toward target pretesting depth of 46.00 05/25/21 08:03:10, prp20 = 29891036328270462493 (curve 17 stg2 B1=11000 sigma=2464115041 thread=0) 05/25/21 08:03:10, Finished 16 curves using GMPECM method on C138 input, B1=11k, B2=gmpecm default 05/25/21 08:03:10, current ECM pretesting depth: 18.22 05/25/21 08:03:10, scheduled 29 curves at B1=11000 toward target pretesting depth of 39.67 05/25/21 08:03:11, Finished 29 curves using GMPECM method on C119 input, B1=11k, B2=gmpecm default 05/25/21 08:03:11, current ECM pretesting depth: 20.24 05/25/21 08:03:11, scheduled 214 curves at B1=50000 toward target pretesting depth of 39.67 05/25/21 08:03:16, Finished 28 curves using GMPECM method on C119 input, B1=50k, B2=gmpecm default 05/25/21 08:03:16, ecm work completed: 05/25/21 08:03:16, t15: 11.17 05/25/21 08:03:16, t20: 2.37 05/25/21 08:03:16, t25: 0.18 05/25/21 08:03:16, t30: 0.01 05/25/21 08:03:16, estimated sum of completed work is t20.90 05/25/21 08:03:16, c119 cofactor = 12698277665702007683889275815276693326593280837281482940452961346094193789732001920277335420071981852156946378079178463 05/25/21 08:03:16, Total factoring time = 9.3754 seconds 

20210525, 13:06  #4  
Aug 2020
79*6581e4;3*2539e3
2×211 Posts 
Ok, good thing is that now I don't feel bad about not having the sigma value. Also now I understand why mersenne.ca lists all the composites from the individual prime factors.
Quote:
bsquared, it was, thanks, good to know. c36 = 440152471934945015138192794987703257 (curve 6 stg2 B1=11000 sigma=2297172961 thread=0) Last fiddled with by bur on 20210525 at 13:08 

20210525, 13:59  #5 
Apr 2020
547 Posts 
p+q is the probability that we find p17 + the probability that we find p20. This isn't the same as the probability that we find at least one factor, because the event of finding both factors has been counted twice. We have to subtract pq so that it's only counted once.

20210525, 16:49  #6 
Apr 2020
547 Posts 
Not that finding prime factors this size with B1=11000 is impossible, of course...
Code:
Input number is 2620519254999982956944693806722047228671931874901767343016731580641103591846137660932998377365079349 (100 digits) Using B1=11000, B2=1873422, polynomial x^1, sigma=1:2652427188 Step 1 took 9ms Step 2 took 10ms ********** Factor found in step 2: 4356499732216851745669859500125914813 Found prime factor of 37 digits: 4356499732216851745669859500125914813 Prime cofactor 601519434425972878158110031787827846949715201404814409296346073 has 63 digits 
20210804, 09:21  #7 
Aug 2020
79*6581e4;3*2539e3
2·211 Posts 
I recently at least got this one:
Code:
Input number is 1166141325000052111361764605105595818472679462069856528077275056603926551634558842276025432804497163836863036435254739761264198526235617987476538533483079075943 (160 digits) Using B1=250000, B2=128992510, polynomial Dickson(3), sigma=0:2996313125 Step 1 took 432ms Step 2 took 210ms ********** Factor found in step 2: 139872296439366881230578341055973791779 Found prime factor of 39 digits: 139872296439366881230578341055973791779 Composite cofactor 8337185809382644180327727108013902691602138775718932279278016755751082707643832077409550981021468083800019835676234158317 has 121 digits Since B2 is 128,992,510, that was a close call... :) @charybdis, I checked it with http://www.wraithx.net/math/ecmprobs/ecmprobs.html and with the default 86 curves that was just a 0.0004 % chance, nearly one in a million. I also tried calculating the group order using https://www.mersenneforum.org/showpo...55&postcount=7, but it had too large factors, is it due to the 1: for sigma? Or did I get the requirements of B1/B2 on the group order completely wrong? Last fiddled with by bur on 20210804 at 09:32 
20210804, 09:57  #8 
"Oliver"
Sep 2017
Porta Westfalica, DE
1100000000_{2} Posts 
There is a more advanced script:
http://www.mersenneforum.org/showpos...2&postcount=10 The other code seems to use another parameterization (0). If you set param=1 in the code in the link, it should work. If you have problems with the code, I posted a version with other whitespaces in the same thread. I'm not sure why that caused problems for me. 
20210804, 12:15  #9  
Apr 2020
547 Posts 
Quote:


20210804, 12:22  #10  
Aug 2020
79*6581e4;3*2539e3
2×211 Posts 
Nice script, I pasted it to a file, read it from there and everything worked fine, thanks. In case someone is interested, the group order of charybdis' factor is:
4356499732216851749111826681360557808 = 2^4 · 3^3 · 41 · 43^2 · 59 · 79 · 607 · 1093 · 1303 · 1429 · 4327 · 6089 · 876871 So it's even nicely within the limits. edit: Quote:
Last fiddled with by bur on 20210804 at 12:25 

20210804, 16:36  #11  
Apr 2020
547 Posts 
Quote:
This isn't what I did. Last fiddled with by charybdis on 20210804 at 16:36 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How are the large factors more than 100 digits found?  Ensigm  Factoring  5  20200826 21:10 
how much time does it need to factor a number of 289 digits?  eric  YAFU  5  20180510 12:59 
who can help me factor this 155 digits number  sinide  Factoring  12  20101109 01:05 
who can factor this 128 digits number?  aaa120  Factoring  19  20100904 09:16 
Predict number of digits in factor of 3,499+  lazy  Miscellaneous Math  0  20070622 12:14 