4 ms·
Factorization of RSA-250 (2020)
- rwmj 5y agoWe're over a 10th of the way to RSA-2048! (joke) https://en.wikipedia.org/wiki/RSA_numbers https://en.wikipedia.org/wiki/RSA_numbers
- anderskaseorg 5y agoFor those who don’t get the joke: RSA-250 is named for the number of decimal digits (250 decimal digits, 829 bits), while RSA-2048 is named for the number of binary digits (617 decimal digits, 2048 bits), so we’re two-fifths of the way by length, not a tenth. On the other hand, given the complexity of current factorization algorithms, RSA-2048 is going to take something like 200 billion times more CPU power; of course, algorithmic and computational advances are likely to decrease that. The implications for RSA-1024 are more pressing: that’s only going to take about 200 times more CPU power.
- bzxcvbn 5y agoA tenth of the way in log scale is not much. There's a 1219 bits difference between RSA250 and RSA2048. And 2^1219 is around 10^367. We're not talking about 100 billion times more CPU time. We're talking about around a billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion times more.
- anderskaseorg 5y agoNo. The relevant algorithm is not one that counts up from 2 to n and performs trial division. It’s the massively faster general number field sieve, whose complexity is approximately exp((64/9)^⅓ (ln n)^⅓ (ln ln n)^⅔), which is about 6.43897⋅10²³ for RSA-250 and 1.52374⋅10³⁵ for RSA-2048. https://en.wikipedia.org/wiki/General_number_field_sieve https://en.wikipedia.org/wiki/General_number_field_sieve
- yuliyp 5y agoMore like a 40% by that logic. It seems like there's inconsistency around which numbers are counted using decimal digits and which ones are counted using bits. This one is 250 decimal digits, or 829 bits.
- ncc-erik 5y agoFound in 2700 core-years, verified in < 1 core-second >>> 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367*33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711 == 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937 True
- svnpenn 5y agoThat a ratio of 85 billion to 1, ouch
- londons_explore 5y agoThe point of RSA is to have a much higher ratio than that...
- ncc-erik 5y agoMy measurement was imprecise and that probably throws things off: python -m timeit '64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367*33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711 == 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937' 500000 loops, best of 5: 496 nsec per loop So roughly 2 verifications per core-millisecond, ~170 quadrillion ratio?
- oasisbob 5y agoAccording to the message headers, this announcement occurred in February 2020.
- gus_massa 5y agoIt was discussed here in 2020 but it didn't get too many comments https://news.ycombinator.com/item?id=22816167 https://news.ycombinator.com/item?id=22816167 (30 points | April 8, 2020 | 5 comments)
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- pvg 5y agoRelated, with a bunch of comments that apply The Factorization of RSA-240, Dec 2019, 36 comments https://news.ycombinator.com/item?id=21696438 https://news.ycombinator.com/item?id=21696438
- dvh 5y agoI'm trying RSA-896 in a screensaver for about a year, so far I have nothing. The reward for this one is 75k.
- anderskaseorg 5y agoFYI the challenge ended 15 years ago; there are no more cash rewards.
- dvh 5y agoThanks. Now I have to start buying lottery tickets to daydream.
- cabirum 5y ago2700 core-years is about 21 128-core c6i instances, $3.59856/hour each. One year costs about $665000, can be done if one really needs it
- sterlind 5y agoyou could probably do it for cheaper using a larger pool of preemptable instances. I think you may end up saving money buying your own blades (21x4 Intel Xeon 32-core CPUs = ~$210K, I'm assuming motherboards + power + ram is less than 3x that.) I didn't factor in AMD's 128-core Epyc processors or Xeon Phis because I don't know enough about their suitability.. do you need AVX-512 for this kind of thing?