mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-05-25, 12:18   #1
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2·211 Posts
Default 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.
bur is offline   Reply With Quote
Old 2021-05-25, 12:50   #2
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

Quote:
Originally Posted by bur View Post
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
charybdis is offline   Reply With Quote
Old 2021-05-25, 13:06   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·1,193 Posts
Default

Quote:
Originally Posted by bur View Post
... 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
bsquared is offline   Reply With Quote
Old 2021-05-25, 13:06   #4
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2×211 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-05-25, 13:59   #5
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

Quote:
Originally Posted by bur View Post
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.
charybdis is offline   Reply With Quote
Old 2021-05-25, 16:49   #6
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

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
charybdis is offline   Reply With Quote
Old 2021-08-04, 09:21   #7
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2·211 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-08-04, 09:57   #8
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

11000000002 Posts
Default

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.
kruoli is offline   Reply With Quote
Old 2021-08-04, 12:15   #9
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

Quote:
Originally Posted by bur View Post
@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...
charybdis is offline   Reply With Quote
Old 2021-08-04, 12:22   #10
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2×211 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-08-04, 16:36   #11
charybdis
 
charybdis's Avatar
 
Apr 2020

547 Posts
Default

Quote:
Originally Posted by bur View Post
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
charybdis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How are the large factors more than 100 digits found? Ensigm Factoring 5 2020-08-26 21:10
how much time does it need to factor a number of 289 digits? eric YAFU 5 2018-05-10 12:59
who can help me factor this 155 digits number sinide Factoring 12 2010-11-09 01:05
who can factor this 128 digits number? aaa120 Factoring 19 2010-09-04 09:16
Predict number of digits in factor of 3,499+ 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.