Noob question about YAFU usage

[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 :)

[Batalov]

Technically, first thing: a product of two 108-digit numbers will have at least 215 digits.

[bsquared]

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 :)

Your english is great!

Short answer:
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).

Longer answer:
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.

[no73]

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.

[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.

[penlu]

Do you know anything more about these factors, e.g. that their difference is fairly small...?

[Uncwilly]

Sounds like encryption keys or some such. Why might one want to factor them????

[CRGreathouse]

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).

[bsquared]

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?

[jwaltos]

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.

[CRGreathouse]

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.