mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2019-01-08, 19:37   #1
no73
 
Dec 2018

2 Posts
Default 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 :)
no73 is offline   Reply With Quote
Old 2019-01-08, 19:40   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·11·281 Posts
Default

Technically, first thing: a product of two 108-digit numbers will have at least 215 digits.
Batalov is offline   Reply With Quote
Old 2019-01-08, 19:47   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×19×59 Posts
Default

Quote:
Originally Posted by no73 View Post
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.
bsquared is offline   Reply With Quote
Old 2019-01-08, 19:54   #4
no73
 
Dec 2018

2 Posts
Default

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.
no73 is offline   Reply With Quote
Old 2019-01-08, 20:05   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D2316 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2019-01-08, 20:22   #6
penlu
 
Jul 2018

111112 Posts
Default

Do you know anything more about these factors, e.g. that their difference is fairly small...?
penlu is offline   Reply With Quote
Old 2019-01-08, 20:40   #7
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

100100000001112 Posts
Default

Sounds like encryption keys or some such. Why might one want to factor them????
Uncwilly is offline   Reply With Quote
Old 2019-01-09, 20:16   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

174A16 Posts
Default

Quote:
Originally Posted by bsquared View Post
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).
CRGreathouse is offline   Reply With Quote
Old 2019-01-09, 21:00   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·19·59 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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?
bsquared is offline   Reply With Quote
Old 2019-01-09, 23:59   #10
jwaltos
 
jwaltos's Avatar
 
Apr 2012

2·181 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
jwaltos is offline   Reply With Quote
Old 2019-01-10, 03:43   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

174A16 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Noob Question Pickwun Information & Answers 7 2017-11-07 19:17
yafu.pl Usage Currently EdH FactorDB 37 2016-09-11 18:37
yafu memory usage for ecm Johnatan YAFU 5 2016-06-13 11:28
Noob Question: What to use bozocv Msieve 36 2015-12-31 00:12
Noob question xago666 Information & Answers 3 2008-03-11 01:35

All times are UTC. The time now is 09:51.

Thu Jan 28 09:51:21 UTC 2021 up 56 days, 6:02, 0 users, load averages: 3.86, 3.45, 2.91

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.