mersenneforum.org 36 digits factor found with 5@11e3
 Register FAQ Search Today's Posts Mark Forums Read

 2021-05-25, 12:18 #1 bur     Aug 2020 79*6581e-4;3*2539e-3 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 = gmp-ecm 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=gmp-ecm 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=gmp-ecm default ecm: found c36 factor = 440152471934945015138192794987703257 According to Wraithx' probability calculator that was a 1:1.77 million chance. It seems yafu doesn't save the sigma it used though, all I found was a temporary file containing the sigma for the subsequent 50k run.
2021-05-25, 12:50   #2
charybdis

Apr 2020

547 Posts

Quote:
 Originally Posted by bur This just happened: :D Code: ecm: found c36 factor = 440152471934945015138192794987703257 According to Wraithx' probability calculator that was a 1:1.77 million chance. It seems yafu doesn't save the sigma it used though, all I found was a temporary file containing the sigma for the subsequent 50k run.
The probability calculator only works for prime factors. That factor is composite, and the probability of finding a composite factor on a given curve is the product of the probabilities of finding each of its prime factors. This is much more likely than finding a prime factor of the same size.

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+q-pq. 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+q-pq), which comes out as around 1 in 127 for this particular example.

Last fiddled with by charybdis on 2021-05-25 at 12:50

2021-05-25, 13:06   #3
bsquared

"Ben"
Feb 2007

3·1,193 Posts

Quote:
 Originally Posted by bur ... It seems yafu doesn't save the sigma it used though, all I found was a temporary file containing the sigma for the subsequent 50k run.
It should be in factor.log. Example:

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 = gmp-ecm 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 GMP-ECM method on C174 input, B1=2k, B2=gmp-ecm 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 GMP-ECM method on C174 input, B1=11k, B2=gmp-ecm 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 GMP-ECM method on C158 input, B1=11k, B2=gmp-ecm 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 GMP-ECM method on C138 input, B1=11k, B2=gmp-ecm 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 GMP-ECM method on C119 input, B1=11k, B2=gmp-ecm 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 GMP-ECM method on C119 input, B1=50k, B2=gmp-ecm 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

2021-05-25, 13:06   #4
bur

Aug 2020
79*6581e-4;3*2539e-3

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:
 Then the probability of finding at least one of the factors on a given curve is p+q-pq
Why the -pq? Wouldn't that mean exactly one factor?

bsquared, it was, thanks, good to know.
c36 = 440152471934945015138192794987703257 (curve 6 stg2 B1=11000 sigma=2297172961 thread=0)

Last fiddled with by bur on 2021-05-25 at 13:08

2021-05-25, 13:59   #5
charybdis

Apr 2020

547 Posts

Quote:
 Originally Posted by bur Why the -pq? Wouldn't that mean exactly one factor?
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.

 2021-05-25, 16:49 #6 charybdis     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
 2021-08-04, 09:21 #7 bur     Aug 2020 79*6581e-4;3*2539e-3 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 With group order: 2^3 · 3 · 7^2 · 13 · 79 · 157 · 233 · 463 · 983 · 2203 · 136343 · 181889 · 127323943 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 2021-08-04 at 09:32
 2021-08-04, 09:57 #8 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 11000000002 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.
2021-08-04, 12:15   #9
charybdis

Apr 2020

547 Posts

Quote:
 Originally Posted by bur @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 thought the might be a hint that nefarious methods may have been involved...

2021-08-04, 12:22   #10
bur

Aug 2020
79*6581e-4;3*2539e-3

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:
 I thought the might be a hint that nefarious methods may have been involved...
Aha! I had a suspicion, but didn't know it was possible. ;) But for large factors it's not possible to construct something like this? Otherwise the ECM records would be somewhat pointless.

Last fiddled with by bur on 2021-08-04 at 12:25

2021-08-04, 16:36   #11
charybdis

Apr 2020

547 Posts

Quote:
 Originally Posted by bur Aha! I had a suspicion, but didn't know it was possible. ;) But for large factors it's not possible to construct something like this? Otherwise the ECM records would be somewhat pointless.
I think it is possible to contrive things like this, but you would need to pick the factor and sigma carefully, so I don't think you can find a p100 factor by SNFS and then construct an ECM curve that finds it.

This isn't what I did.

Last fiddled with by charybdis on 2021-08-04 at 16:36

 Similar Threads Thread Thread Starter Forum Replies Last Post Ensigm Factoring 5 2020-08-26 21:10 eric YAFU 5 2018-05-10 12:59 sinide Factoring 12 2010-11-09 01:05 aaa120 Factoring 19 2010-09-04 09:16 lazy Miscellaneous Math 0 2007-06-22 12:14

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

Sat Dec 4 05:24:18 UTC 2021 up 133 days, 23:53, 0 users, load averages: 1.00, 1.52, 1.57