mersenneforum.org > YAFU Noob question about YAFU usage
 Register FAQ Search Today's Posts Mark Forums Read

 2019-01-08, 19:37 #1 no73   Dec 2018 216 Posts Noob question about YAFU usage Hello, as a math and prime number lover i've been following and using yafu for about 3 years but because of my insufficent computer skills sometimes im not able to use it. I better ask the question directly, Lets say we have a '214 digit' number and we know that there are only 2 factors of it and the factors are both 108 digits. For example, '108 digits x 108 digits = 214 digits'. In this situation, how can i tell yafu to look out for only 108 digits numbers to factorize the 214 digits number? I mean i know that there are 2 factors only and they are 108 digits. With this knowledge, there is no need to lose time and look for other numbers. Is there any usage option for this? ps, sorry for my bad english but i hope you understand what i want to say :)
 2019-01-08, 19:40 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·13·359 Posts Technically, first thing: a product of two 108-digit numbers will have at least 215 digits.
2019-01-08, 19:47   #3
bsquared

"Ben"
Feb 2007

3,373 Posts

Quote:
 Originally Posted by no73 Hello, as a math and prime number lover i've been following and using yafu for about 3 years but because of my insufficent computer skills sometimes im not able to use it. I better ask the question directly, Lets say we have a '214 digit' number and we know that there are only 2 factors of it and the factors are both 108 digits. For example, '108 digits x 108 digits = 214 digits'. In this situation, how can i tell yafu to look out for only 108 digits numbers to factorize the 214 digits number? I mean i know that there are 2 factors only and they are 108 digits. With this knowledge, there is no need to lose time and look for other numbers. Is there any usage option for this? ps, sorry for my bad english but i hope you understand what i want to say :)

If you know the size of the factors and they are both large, then you can probably skip directly to the number field sieve. In yafu you would do this with the command "nfs(your_number)". But you shouldn't do this (see below).

Assuming this isn't a number with a special form (e.g., equal to something like a^b - c, with a,b,c "smal"), which it probably isn't because of the equal size of the factors, then it would rank among the most difficult factorizations ever attempted by humans. Yafu will not be successful in factoring it. To attempt it, you'll need hundreds of computer cores sustained over a period of months to years, along with a fairly manual process using different tools (CADO or combination of msieve, ggnfs) in a way that yafu isn't designed to optimize. Others on the forum have more experience and could maybe provide more specific guidance if you are determined enough to proceed.

 2019-01-08, 19:54 #4 no73   Dec 2018 2 Posts wow i wasn't really expecting answers that fast :) @Batalov thanks for correcting i was trying to give examples from nowhere but you are right my example was wrong. @bsquared, ok i think understand it. thank you for your kindness and time to give explanation.
 2019-01-08, 20:05 #5 bsquared     "Ben" Feb 2007 3,373 Posts Here is a reference point: the factorization of RSA220 It took ~370 CPU-years of sieving effort, in 2016 computer-years. And that's just the sieving. The arguably more difficult matrix-solve stage took weeks on an Infiniband-interconnected cluster.
 2019-01-08, 20:22 #6 penlu   Jul 2018 31 Posts Do you know anything more about these factors, e.g. that their difference is fairly small...?
 2019-01-08, 20:40 #7 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 11·853 Posts Sounds like encryption keys or some such. Why might one want to factor them????
2019-01-09, 20:16   #8
CRGreathouse

Aug 2006

2×29×103 Posts

Quote:
 Originally Posted by bsquared Here is a reference point: the factorization of RSA220 It took ~370 CPU-years of sieving effort, in 2016 computer-years. And that's just the sieving. The arguably more difficult matrix-solve stage took weeks on an Infiniband-interconnected cluster.
FWIW, a 214-digit number would be 19% - 24% easier than RSA-220 by naive scaling of the GNFS asymptotic with o(1) = 0. So ~300 core-years of sieving (not hard) on the machines they used (Xeon E5-2650) or about 128 years on EC2 c5.xlarge (crudely scaled by Passmark -- they're Xeon Platinum 8124Ms). At current spot prices, in the cheapest region, the sieving cost is a little more than $42,000. It's harder to guess what the LA would cost, but it's definitely a non-commodity job, so$100,000+ seems reasonable. So definitely doable -- even by an individual -- but not easily. The best approach would be to wait a few years for prices to come down, especially on memory (for LA).

2019-01-09, 21:00   #9
bsquared

"Ben"
Feb 2007

3,373 Posts

Quote:
 Originally Posted by CRGreathouse FWIW, a 214-digit number would be 19% - 24% easier than RSA-220 by naive scaling of the GNFS asymptotic with o(1) = 0. So ~300 core-years of sieving (not hard) on the machines they used (Xeon E5-2650) or about 128 years on EC2 c5.xlarge (crudely scaled by Passmark -- they're Xeon Platinum 8124Ms). At current spot prices, in the cheapest region, the sieving cost is a little more than $42,000. It's harder to guess what the LA would cost, but it's definitely a non-commodity job, so$100,000+ seems reasonable. So definitely doable -- even by an individual -- but not easily. The best approach would be to wait a few years for prices to come down, especially on memory (for LA).
Nice analysis. And that reminds me, with a supremely impressive effort WraithX actually did a comparable factorization (C210) using Amazon spot instances, costing about $7600 in 2014. +5 years and +5 digits and maybe one could do the OP's number for about the same? 2019-01-09, 23:59 #10 jwaltos Apr 2012 Standing, top right. 373 Posts Quote:  Originally Posted by CRGreathouse FWIW.... I'll second B^2's opinion of your assessment. You covered all bases. I wasn't aware of Passmark so your post provided me with a bit of unexpected help also. Ty. Last fiddled with by jwaltos on 2019-01-10 at 00:01 2019-01-10, 03:43 #11 CRGreathouse Aug 2006 2·29·103 Posts Quote:  Originally Posted by bsquared Nice analysis. And that reminds me, with a supremely impressive effort WraithX actually did a comparable factorization (C210) using Amazon spot instances, costing about$7600 in 2014. +5 years and +5 digits and maybe one could do the OP's number for about the same?
Gosh, WraithX needed a lot less effort for his run than the naive GNFS relation would have suggested. It would probably even be cheaper today to factor a C214 than it was for him to factor the C210. My numbers look way off; I'm guessing the o(1) assumption was what killed it.

 Similar Threads Thread Thread Starter Forum Replies Last Post Pickwun Information & Answers 7 2017-11-07 19:17 EdH FactorDB 37 2016-09-11 18:37 Johnatan YAFU 5 2016-06-13 11:28 bozocv Msieve 36 2015-12-31 00:12 xago666 Information & Answers 3 2008-03-11 01:35

All times are UTC. The time now is 22:55.

Mon Mar 8 22:55:42 UTC 2021 up 95 days, 19:07, 0 users, load averages: 0.88, 1.41, 1.69