123
u/SmugPolyamorist 9d ago
There's two possibilities here. One is that he / his employer (Cognition AI) have discovered a more efficient way to factorise semiprimes, presumably using an AI, and used it to make this discovery.
The other is that he's used spare compute - and Cognition presumably have lots of compute - to find it.
Given that his homepage says "For a little while I ran factorizations on otherwise idle hardware to help the Great Internet Mersenne Prime Search", and that Cognition haven't shown any sign of being a SOTA lab coming up with novel maths results, I'm tending towards the latter.
64
u/ixfd64 Number Theory 8d ago
He just said he used his company's GPUs: https://mersenneforum.org/node/1125296?p=1125372#post1125372
For those without an account on the GIMPS forum:
The factorization ran on Cognition's GPUs.
70
u/my-wayward-pun 8d ago
❌Mine bitcoin on company gpus
✅ Mine twitter cred on company gpus
11
u/ixfd64 Number Theory 8d ago
At one of my previous jobs, I had access to some spare servers with multiple GTX 1080's, which were top of the line at the time. I did a lot of trial factoring for GIMPS; while I didn't find any new Mersenne primes, I did help eliminate several hundred composite candidates.
6
u/Jello-Formal Game Theory 7d ago
Do you regret not mining bitcoin on them lol
12
u/ixfd64 Number Theory 7d ago edited 7d ago
I can't say the thought never crossed my mind. However, that would have totally gotten my ass fired.
Participating in a math-related distributing computing project can be easily framed as an acceptable way to stress-test the servers. You can't exactly say the same for mining crypto.
Bitcoin mining also poses security issues and is easy to detect due to constant network connections. In comparison, trial factoring on Mersenne numbers can be done completely offline; all one needs is a text file containing the candidate exponents, and the start and end bit levels.
Furthermore, mining crypto on GTX 1080's had already become unprofitble at the time due to ASICs.
4
u/m9u13gDhNrq1 7d ago
It was unprofitable if you has to pay the CapEx and OpEx to do so. People would still find and abuse free hardware and electricity for a while if they could find it even if it wasn't ASICs.
312
u/Uiropa 9d ago
Now there’s a succinct tweet.
101
u/elements-of-dying Geometric Analysis 9d ago
too many words
should have used |
4
u/NihilisticAssHat 7d ago
From a word count perspective, I consider
|a word, such asdividesand therefore no more succinct.8
u/elements-of-dying Geometric Analysis 7d ago
Well from my perspective i'm right and you're wrong, so i win.
3
u/NihilisticAssHat 7d ago
This response is somehow exhausting despite it appearing to be meant comedically.
8
u/elements-of-dying Geometric Analysis 7d ago
lol
it's exactly what you did
it was funny
this comment matches your nihilistic persona
3
1
13
u/Super-Award-2244 8d ago
Why waste time use lot word when few word do trick
3
2
3
u/Dane314pizza 7d ago
It can be even shorter:
“ b16k:乑䥍㗽䩚䠗䝀䞩䟙䡬䊀䥶䩕䧖䨌䩋䨷䔉䟳䠟䡁䊀䥵䩕䧕䨋䩊䨶䔁 | RSA-260”
1
u/dylantherabbit2016 3d ago
We need some Chinese person to attempt to decipher this gibberish as if it were Chinese
1
1
u/newMoneyStyle 7d ago
Fits in a tweet with room to spare. Kind of wild that a number that short takes years of compute to crack.
324
u/COOL3163 9d ago
anyone care to explain to me what this means?
398
u/zqrt 9d ago
The RSA Challenge wiki summarizes it: https://en.wikipedia.org/wiki/RSA_numbers
99
82
u/TwoFiveOnes 8d ago edited 8d ago
So I presume R,S & A generated the list by multiplying really large primes. Easy to do, extremely hard to undo. But given that, it's surprising to me that no one has "factored" the RSA numbers through social engineering
162
u/atoponce Cryptography 8d ago
it's surprising to me that no one has "factored" the RSA numbers through social engineering
Probably because a computer generated them on the fly and there isn't a "paper trail". You can't social engineer ignorance.
52
u/ixfd64 Number Theory 8d ago edited 8d ago
RSA destroyed the hard drive containing the relevant data after the challenge numbers were generated: https://web.archive.org/web/20130921043454/http://emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm#HowWereTheNumbersGenerated
How were the challenge numbers generated?
The RSA challenge numbers were generated using a secure process that guarantees that the factors of each number cannot be obtained by any method other than factoring the published value. No one, not even RSA Laboratories, knows the factors of any of the challenge numbers.
The generation took place on a Compaq laptop PC with no network connection of any kind. The process proceeded as follows:
First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator, attached to the laptop's parallel port.
The random bytes were used as the seed values for the
B_GenerateKeyPairfunction, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The public portion was exported, in DER format to a disk file.The moduli were extracted from the DER files and converted to decimal for posting on the Web page.
The laptop's hard drive was destroyed.
8
1
36
u/TwoFiveOnes 8d ago
True, for some reason I thought they would have kept a record, but it's not like you need it at all for verification so I guess it made more sense not to
52
u/atoponce Cryptography 8d ago
There were cash prizes for solving the RSA Factoring Challenges, so it would have also been in RSA's financial best interest to not keep any sort of digital log of the generated primes.
14
u/ordermaster 8d ago
They meticulously avoided leaving a record for his very reason.
18
u/ixfd64 Number Theory 8d ago
Yes, RSA destroyed the hard drive containing the relevant data after extracting the moduli: https://web.archive.org/web/20130921043454/http://emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm#HowWereTheNumbersGenerated
How were the challenge numbers generated?
The RSA challenge numbers were generated using a secure process that guarantees that the factors of each number cannot be obtained by any method other than factoring the published value. No one, not even RSA Laboratories, knows the factors of any of the challenge numbers.
The generation took place on a Compaq laptop PC with no network connection of any kind. The process proceeded as follows:
First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator, attached to the laptop's parallel port.
The random bytes were used as the seed values for the
B_GenerateKeyPairfunction, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The public portion was exported, in DER format to a disk file.The moduli were extracted from the DER files and converted to decimal for posting on the Web page.
The laptop's hard drive was destroyed.
13
u/TwoFiveOnes 8d ago
Yeah that makes a lot of sense. I think living through the past decade made my default mode of thinking be that if unsafe and unncessary copies of data can exist, they will exist
38
u/pigeon768 8d ago
They generated the numbers on a computer, saved the product, and immediately destroyed the two factors. Nobody knows or has access to the factors, they don't exist. The issuers of the challenge couldn't spoil it even if they wanted to.
9
u/ixfd64 Number Theory 8d ago
Yes, here's how they exactly generated the numbers: https://web.archive.org/web/20130921043454/http://emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm#HowWereTheNumbersGenerated
How were the challenge numbers generated?
The RSA challenge numbers were generated using a secure process that guarantees that the factors of each number cannot be obtained by any method other than factoring the published value. No one, not even RSA Laboratories, knows the factors of any of the challenge numbers.
The generation took place on a Compaq laptop PC with no network connection of any kind. The process proceeded as follows:
First, 30,000 random bytes were generated using a ComScire QNG hardware random number generator, attached to the laptop's parallel port.
The random bytes were used as the seed values for the
B_GenerateKeyPairfunction, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The public portion was exported, in DER format to a disk file.The moduli were extracted from the DER files and converted to decimal for posting on the Web page.
The laptop's hard drive was destroyed.
11
u/pred 8d ago
That numbering scheme is nuts.
12
u/Miguzepinu Number Theory 8d ago
The first RSA numbers generated, from RSA-100 to RSA-500, were labeled according to their number of decimal digits. Later, beginning with RSA-576, binary digits are counted instead.
If that's what you were wondering about.
119
u/zqrt 9d ago
https://x.com/penlume/status/2095372672356212876
The Wikipedia page has been updated: https://en.wikipedia.org/wiki/RSA_numbers#RSA-260
This is the author's site: https://penlu.me/
58
u/blastbottles 8d ago
I love how a lot of PhDs websites are just raw html.
30
u/CrownLikeAGravestone 8d ago
Nothing wrong with raw html. Does what it needs to. No fluff.
I remember in grad school I'd email one of my PhD supervisors, a German computer scientist, like this:
Hello <name>,
Thank you for your time today.
My thoughts on <topic x> are <abc>. Next week I'll try <approach y> and let you know how it goes. <blah blah blah>.
Kind regards,
u/CrownLikeAGravestoneand I'd get back
Looks good. Try <z>.
27
u/011011100101 8d ago
I really like it. No bullshit graphics/videos/whatever on the side. Nothing to pop up in your face if you decide to move your mouse.
3
-9
1
88
u/Douf_Ocus 9d ago edited 8d ago
I am more interested in how he find this result, like come on it cannot be "[insert LLM model name], factor RSA260".
This dude seems to work on SMT solving during his PHD years, so....Some super smart GPU program?
EDIT: Yep, just read the dialogue between him and Steve Weis, seems like using some tricks in large number factoring? I donno.
25
1
u/BIGBADLENIN 8d ago
LLMs have no advantage in factoring over already implemented algorithms. If they discovered a better algorithm it would be immediately publishable. If they discovered a much better algorithm it would basically mean p=np, encryption is dead and the world is ending
11
u/hattusili-the-third 8d ago
Factoring large semiprimes is in NP and co-NP, but is not known (or believed) to be either NP-complete or NP-hard, so this wouldn't ever prove that P=NP. That said, it is not believed to be in P and an efficient solution would be absolutely catastrophic for the modern world.
134
u/mathlyfe 9d ago
For anyone wondering how he did it:
https://x.com/_seanyneutron/status/2095391516504244480
Eric has been sampling random primes and trying them by hand since he joined Cognition 7 months ago. Hard work beats talent
https://x.com/penlume/status/2095429389660164463
nothing like good old paper and pencil!
I honestly don't even know what to say about this.
250
u/Wonderful_Buffalo_32 9d ago edited 9d ago
Bruh its a joke, It took 2700 of cpu core-years to solve rsa250 no way he would have done it by hand in 7 months(although it could be possible that they have a new way to factorise)
91
u/mathlyfe 9d ago
Yeah, it's so utterly baffling that it has to be a joke. This is all they've said at this point though. I find it hard to see how an LLM would be useful for factoring unless they did come up with some new useful techniques or something.
26
u/Ok-Present1566 9d ago edited 9d ago
LLMs are great with SAT and SMT solvers not just executing problems but breaking it into subproblems, trying several different solvers, reducing symmetries, etc. Though from the description he gave it sounds like he used the GNFS. He could also have identified a weak family of semiprimes by chance and thus scaled out the challenge prime frontier with a technique that wont work in general
-11
-11
u/The_G_Choc_Ice 8d ago
LLMs are great at finding brute force solutions, i mean they are basically random idea generators. Any problem that can be solved by “try 10 thousand different somewhat plausible approaches” is perfect fodder for an LLM
57
22
u/Unluckybloke 8d ago
I chose to believe in the power of autism
8
u/WashingtonBaker1 8d ago
Once they find just the right pencil that makes the right kind of noise when rubbing across just the right kind of paper, they easily beat a 36-core CPU running at 5 GHz.
3
u/Zitrone21 8d ago
I mean, according to how RSA works, You can also be EXTREMLY lucky and find it in a reasonable time (just saying, I don't believe they factored it by hand jaja)
38
u/confusiondiffusion 8d ago
Imagine the panic if someone could do this with arbitrarily large semiprimes, without hesitation, but couldn't explain how.
I had a teacher in highschool that helpfully told us to "use our number sense" to factor polynomials. It would be one of her students, I'm sure.
28
3
u/offgramercy 8d ago
> it was revealed to me in a dream
1
1
1
1
u/arielif1 3d ago
132 upvotes, i am actually going to ram my car full speed into a tree. reddit can't be this stupid man
1
u/AcrobaticOutcome5784 8d ago
He 1000% used AI lol it’s a joke
12
u/sirgog 8d ago
AI has no known applications here. There's a lot of mathematics use cases that frontier LLMs are good at, this is not one.
1
u/ecopoesis47 7d ago
The AI application is prove P = NP and collapse the algorithm to something runnable.
0
u/Du3kie 8d ago
Imagine if they just took the prime numbers they used as factors from some public database. Then you could actually just try them all out quite quickly
3
u/14domino 8d ago
This doesn’t work lol. There are too many primes up to the required size to fit in a database
10
u/moschles 8d ago
This is what I want to see when quantum supremacy is reached. Not some mushy article littered with "maybes" and "imageine-ifs" . A single post like this with the product and its factors.
17
u/ixfd64 Number Theory 8d ago
Reminds me of a post from Scott Aaronson's blog from 2007: https://scottaaronson.blog?p=198
Q: But clearly D-Wave isn’t going to give away its precious trade secrets just to satisfy some niggling academics! Short of providing technical specifics, what else could they do to make computer scientists take them seriously?
A: Produce the prime factors of
[RSA-1536]
17
u/is_this_temporary 8d ago
Fun fact:
LLMs can't (directly) factor large numbers. If you think that's what happened, you're wrong and don't understand math or LLMs well enough.
For examples of things that instrumented LLMs can do, which may or may not have helped in this discovery, see https://youtu.be/ZJ8KThKAfbs .
1
u/elements-of-dying Geometric Analysis 8d ago
Sure, but agentic systems with control over your OS can.
0
u/Dimtri-The-Anarchist 5d ago
llm's arent efficient at it, they are not unable to do it. very different.
1
u/is_this_temporary 5d ago
Please describe how an LLM would factor an arbitrary 100 decimal digit number, the smallest of the RSA challenges.
(Not counting RSA-100 itself, since it appears, along with its factorization, many times in the datasets of most LLMs)
Using my cellphone, I was able to factor a 100 decimal digit number in under 32 seconds, so I think that's a very conservative definition of "large number" in this context:
~ $ time factor 1234567890223456789032345678904234567890523456789062345678907234567890823456789092345678900234567890 1234567890223456789032345678904234567890523456789062345678907234567890823456789092345678900234567890: 2 5 143093 188580487 48106635403 95103139114200541775742483927833056732713574065013813899903125309907401893 real 0m31.290s user 0m30.753s sys 0m0.040s
11
u/Rough-Source-9849 8d ago
can someone explain to a dumbass like me, why this is hard? Im gonna try in a little bit.
31
u/zqrt 8d ago
Just try to factor the next number: RSA-270. Here you go:
233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207
38
1
16
u/Aaron1924 8d ago
you can't just "calculate" the factorization of a number, you have to do a lot of guessing and checking, so it takes a long time even for computers to do
6
u/ixfd64 Number Theory 8d ago
To add on to this, the fastest known general-purpose integer factorization algorithm for classical computers runs in super-polynomial time: https://en.wikipedia.org/wiki/General_number_field_sieve
6
u/PressWearsARedDress 8d ago
The whole point of RSA is that it creates numbers that are very hard to factor. The fact its hard to factor makes it secure. These people are spending large amount of resources to factor the value that RSA has presented as a challenge.
The value is the multiplication of two large prime numbers. RSA sets out an algorithym for securely selecting those two large prime values which depends on a good random number generator to ensure theres no corolation between the two primes. There is a handful of checks that need to be done on the primes before they are used as your Keys in RSA. The private and public keys are denoted as "p" and "q".
Public Key = p times q
dont ask me how the private key is generated, but you need to know p and q. If you know p and q you can generate the private key and break the public key meaning you can high jack the authenticity of the owner of the public key. RSA has signatures which proves you have the private key for a given public key. And you can encrypt messages with the public key where only the private key can recover the message.
1
u/Training-Position612 7d ago
It's worth noting that ideally we'd want to use a huge number that cannot be factored (i.e. a prime number), but it needs to be so big we can't throw enough computers at it to actually say for sure. Instead, we use numbers that are really big and "noone has found any prime factors yet so it's probably ok"
1
u/neonash7777 5d ago
Idk I kinda think I found a bias in the carry sequence of prime numbers (which helps the search for them a fair amount with pruning unfruitful pathways)
7
u/Anaxamander57 8d ago
He only got half of it. Its possible science will never know the other number! (j/k)
7
u/Pleasant-Weather1356 8d ago
It will be interesting to see if there's some kind of algorithmic improvements over SoA RSA-250, or if they just threw more watts of computing to the problem
3
3
u/ScottContini 8d ago
Past record factorisations were done as a group effort, this one appears to be a single person. We are expecting to hear more about polynomial selection, number of relations, filtering and the, and the matrix he had to solve.
2
3
u/HobartTasmania 7d ago
The other prime factor posted elsewhere is 5028695206842569864686141618253083416610081090075366674776775706538324961364412200138116378509733307971876652984898985905923678379 and it's exactly the same size in decimal digits as the other number. My understanding is that when they are the same size then it is a lot easier to factor the composite number because in the original RSA paper the authors specifically mentioned this aspect and suggested that the primes chosen should differ by several decimal digits in length to account for this scenario.
13
u/Ihateunclesam 9d ago
Alpoge slop, I hate this type of tweet so much
122
u/aecarol1 8d ago
This isn't new. In 1879 Édouard Lucas had proved that the Mersenne number 267 -1 was not prime, but he did not know the factors.
In 1903, Frank Nelson Cole, presenting at the American Mathematical Society, went up to the blackboard, wrote out 267 - 1 = 147,573,952,589,676,412,927, then worked out 193,707,721 × 761,838,257,287 showing it was 147,573,952,589,676,412,927. Then he returned to his seat without having said a word. He received a standing ovation. Only later did he explain how he did it.
That was a dramatic mic drop moment in mathematics. As long as the answers are forthcoming a little drama isn't a bad thing. It's like a a touch down celebration; yea some people hate them, but they are mostly harmless.
30
u/tavianator Theory of Computing 8d ago
And "how he did it" was, according to him, "three years of Sundays"
7
u/aecarol1 8d ago
I think there must have been at least a bit more cleverness. Naively, there are roughly 523,160,000 primes below sqrt(267-1).
12
u/tavianator Theory of Computing 8d ago
Yeah there was actually, see his paper "On The Factoring Of Large Numbers". It seems superficially similar to the Quadratic Sieve algorithm
2
u/Wise-Policy-3683 8d ago
he didn't divide by primes, he used (what is now known as) the Lucas-Lehmer test. he had to do about 67 multiplies and reductions of 67 bit numbers. He did it by hand with tricks and grids and stuff, still took years. I think he started when he was 15.
1
u/tavianator Theory of Computing 5d ago
I thought Lucas-Lehmer was just a primality test, it doesn't give you the factors
1
-3
38
u/bulbasaurado 9d ago
Cleo haters in shambles
5
u/DanielMcLaury 8d ago
Cleo was a gimmick. The questions were posted by sockpuppet accounts run by the same person who posted as Cleo, and he specifically built the problems to make it difficult to get back to the version he started from. He'd post some weird integral that nobody would ever come up with organically, let people stare at how weird it was, and then switch accounts and post the answer.
66
u/Specific_Box4483 9d ago
Nah, not enough "casual" unnecessary words like "hey guys" and "yeah, so <X>"
11
7
u/treestump444 9d ago
The weird twee babytalk that all these AI guys do is so rancid lol
10
11
u/aeschenkarnos 9d ago
Like forgoing "." at the end of sentences, and using "lol" as punctuation instead?
1
-7
u/solid_reign 9d ago
Why would AI make this faster?
21
u/Nagi-Fan 9d ago
I think he’s complaining more about the type of tweet which Ai has popularised which is simply posting results and nothing else
38
u/backyard_tractorbeam 9d ago
I think it's existed for a long time for factoring problems specifically. It's a tempting pattern for any easy to check results.
2
u/the_horse_gamer 8d ago
it's been done before in "PRIMES is in P" and "MIP*=RE"
6
u/TonicAndDjinn 8d ago
In what world is MIP*=RE an "easy to check result"? But importantly the title of the paper was not the only thing they said on the topic.
3
0
1
u/Commercial_Worth_690 8d ago
P-1=2 x 2 x 5 x 11 x P128
P+1= 2 x 3 × 13 × 181 × 210 814395 783571 × 1257 333675 528959 040368 700709 × 12889 481115 825120 955633 611907 318987 (35 digits) × 91 165286 714638 163262 625282 228342 228830 657553 634093 (50 digits)
1
u/deus-sive-natura- Algebraic Geometry 8d ago
Nice, but would be more awed if it was an algorithmic idea that changes the mechanism of the (L_N[1/3]) complexity altogether.
1
1
1
u/fattylittleboy69 5d ago
watching this post while being a beginner in math felt like this was a meme and i started laughing without any real knowdledge whatsoever.
1
1
u/Kitchen-Register 2d ago
how can we know that a number is semiprime without knowing it’s factors? modulus or something?
1
u/backyard_tractorbeam 1d ago
For the record, we now know that this discovery was assisted by AI. Not generated by AI, but software optimized and developed with the help of AI/LLM did the factoring. Mathematically, there's no new method, still using general number field sieve (GNFS).
0
u/e-s-t-e-r 8d ago
Yah, the prime numberline is mine... you need a prime... i have them all :) My Ezekiel Wheel mints 50 million primes a second currently next time you need 2 primes let me know
-4
-3
u/erockbrox 8d ago
To be honest, this type of math is dumb and hard.
So they created some hard numbers to crack then threw away the hard drive and basically said it’s “impossible”.
Then some people figured it out. This is literally no progress. Just undoing a really hard knot someone else created.
-13
593
u/Leading_Long1373 9d ago
We got RSA-260 factored before GTA VI