The OPTIMAL algorithm for factoring!
2023 ж. 31 Нау.
39 751 Рет қаралды
Our program:
github.com/polylog-cs/univers...
RSA factoring challenge: en.wikipedia.org/wiki/RSA_Fac...
Big thanks to: Tomáš Gavenčiak, Matěj Konečný, Jan Petr, Hanka Rozhoňová, Tom Sláma
Our Patreon: / polylog
Credits:
To make this video, we used manim, a Python library: docs.manim.community/en/stable/
The color palette we use is solarized: ethanschoonover.com/solarized/
music: Thannoid by Blue Dot Sessions: app.sessions.blue/browse/trac...
music: Ride of the Valkyries from R. Wagner from wikimedia commons
My computer is currently using 80% of its memory to find the factorization of 15. In other words, it will crash asymptotically.
Nailed it asymptotically
They say memory's cheap nowadays
😄
maybe 15 is a hidden gem prime - i dont get why my comment hasnt showed up (or i cant see it)
Awesome, it can also be used to find ideal chess moves, or reduce GPT4 down to an optimal set of weights! Very versatile, though it does take a computer that's a little faster than mine.
Yep, although it is a bit more tricky! The way we use this trick works very well for "NP problems" where checking is easy and computing hard. You can also use it for more complicated problems like finding ideal chess moves, but you need to throw in one more idea (I want to drop link to this in the video description of the followup video).
Currently attempting to find the factorization of 8. Truly masterful work, this will bring a revolution 😂
A wise usage of memory :^)
Wow, you got past 4?
@@PolylogCS Look at Mr. Chips over here, getting over 2!
Well 8 is not the product of two primes, thus even with infinite power you won’t find out…
@@romain.guillaume jokes on you, I'm checking complex numbers as well
April 1st should go into history as being the day the Internet was broken.
Indeed
wtheckkkk
This is a pretty neat example of how misleading asymptotic complexity can be. :)
Yep :)
Running simultaneously is very clever. This was the first solution I thought of with respect to "asymtoticaly optimal" but didnt know how to get around the Halting Problem
This technique is called "dovetailing."
a lecture into why smaller big O doesnt always mean faster, wonderful
Just save the prime factors before multiplication. O(1). Easy. I don't understand why the engineer forget the obvious solution to just always pack the prime factors alongside the product.
i think for security. the products are sent over the internet and valid receiver finds out the primes. if invalid receivers get the primes bad things can happen.
@@anupbarua6151 why don't you encrypt them then?
@@Megaranator i studied these things a long ago, i think they de-encrypt the messages by the primes. send the primes alongside the message? why? now will you encrypt the primes also?
@@anupbarua6151 yes. enough recursions in and it's gotta be not worth it go trough all the that decrypting for the attackers right? /s (I hope you know that the video and the comments are a joke)
@@Megaranator all jokes aside.
Brazissimo Reminds me of some of the more "Creative" sorting algorithms that got thrown around when I was in school 😆
I was a bit thrilled until I saw we were April 1st... Good one!
Oh, tricky! If it was linear in execution time (1 step of n-1, 2 steps of n-2, 3 steps of n-3), then it would be the square of the most efficient algorithm Instead, since it is exponential, the sum of the terms becomes linear instead! Amazing!
had several confusions... then i realized that the date arithmetic revealed critical context.
If only every channel would do an April Fool's day video. I'd give you extra points if I could for the fact that you used my favorite esoteric language. All that's needed is the program to generate a BF program from an input algorithm. That would really sell it.
is this the same situaiton as the sorting algorithm that just makes a new cpu thread for each element and just tells them to wait as long as their input number says? yeah its the best possible time complexity, but thats not necessarily a good thing.
Sleep sort!
Great video! 🤣😂 We are eager to see its first commercial implementation. 😂😂
Coming soon!
I see, some universal turing machine stuff is coming
this is... beautiful.
omg the thumbnail is so good
Universal search!
I wonder how does this algorithm deal with Encabulator?
Tha computer program either has all the composite numbers precompiled and looks up the solution (or that its a prime number) or its just a composition of all the bf programs starting with the shortest one.
So I am now waiting for getting answer of 15 for last 5 days, should I continue?? 😢
Took a course with Levin, he's a genius
Get your algorithms! We have the finest and freshest algorithms! Step right up!
Small mistake.size of the number with d digits is 9*10^(d-1). Most significant digit cannot zero right? It will have only 9 possible digits.
I thought this was going to be about Shor's algorithm. Nice surprise 😊
Can't believe I fell for it...
I'll bet if someone wrote that code in assembly he'd crack rsa
I saw mention of the "Brainfuck" language, so I ran away screaming.
So if I find a d^2 factoring algorithm I shall worry for my life or expect a Field medal?
Both.
I'm so glad that viewing your video wasn't a waste of my time. --
I knew when I saw BrainFuck in the code this was gonna be a wild one
What is the memory complexity of this algorithm?
Wow! Does this prove that P = PN?
Factorization is not known to be np complete, so regardless of whether the alg is polytime, it wouldn’t be enough to prove p=np
(Or rather I should say, *wasnt* known to be NP complete. I came up with quite a marvelous proof this morning…)
Turns out, you can use this trick also to get asymptotically optimal algorithm for any NP complete problem! (but it gets a bit more tricky, for factoring it's easier to explain what's happening)
I don't quite get it. It draws a large triangle with two dots at the end of each line and at some point freezes, it acts the same with any input.
The triangle is there to help you understand what's happening, but try to look at the code, too!
woah
Me watching the video on April 5, trying to figure out why a brainfck interpreter is relevant to factorization
8 months passed so far, any news on this?
I would but I'm a pretty average dev lol so I doubt I could make it better 😂😂😂 . But, this is great thanks
Anyone else reading these types of ads in the smug yet smarmy and sultry voice of a Hollywood commercial advertisement? "He breaks RSA with this one trick, Computer scientists hate him!"
my PC reported this: File "it.py", line 11 def __init__(self, program: str, input: str): ^ SyntaxError: invalid syntax
NOT ME NOT ON APRIL FIRST! NEVER! EVER! NEVER ME!
Fermat invented this solution before, even if he didn't have the space to write it on his napkin
Wow and this was created without any understanding of the general number field sieve. 😆
i wonder why this video was uploaded 1st april :)
i forget april 1st videos still exist after april the 1st. i can get fooled all year round (;
Is it true ?
They said that it couldn’t be done.
Le risultanze della tavola di lettura , ASCII.
You didnt get me... Its April 1th. Nice try though
People still play that game?
@@Stopinvadingmyhardware this video is a material proof
I actually watched this on the 13th of April. It took me a while to appreciate the humor of it. It made me smile. :)
I got kyphosis watching this.
I recommend optimizing python more. This could probably go a lot fast by eliminating while loops, and going with for loops instead, which run in C code in the python runtime. I'm not sure what all that brainfuck is about, but whatever... Might try finding a more optimal way to evaluate commands than branching all over the place.... Slow. And, just use sets instead of lists... Your eating memory.
The words might be hint brainfuck and universal search.
why do programmers have to name classes such weird names *1:28*
So, you didn't even TRY to come up with a good factoring algorithm? Also, how can we "know" that there isnt an algorithm which gets better than 10^d factoring time?
There are algorithms that do better than 10^d... (e.g the general number field sieve) - this whole video is meant as a joke.
this is the universal search algorithm, which can be mathematically proven to be optimal it's also extremely impractical
Actually the basic flaw in their assertion, is that all solution paths are similar, and have the same algorithmic costs. This is clearly false in that brute force trials, sieve, statistical attacks, and symbolic SAT attacks all have very different solution complexities. For example, certain classes of two prime products can be solved by SAT in a few minutes or hours, others have no solution via SAT like most of the RSA numbers. When SAT can factor certain 512 bit two prime products in hours, then it's pretty clear the assertion made in this work is flawed, IE their algorithm is not the lower bound. This is further complicated by the fact that precompuation attacks will also reduce the time needed to solve a particular class of factoring, by using precomputed partial solutions that are then easily brute forced to solve the remaining portion of the factors. Rainbow tables are one example, which are used to crack passwords which have a similar computational complexity as certain factoring algorithms.
I'm not a programmer. Is "brainfuckexecution" a system command?
Yes, indeed 😂
haha blazni
I havent watched the video yet, but im guessing its social engineering.
Not really, it's legit! Go and watch it, I think you'll enjoy it!
You can't keep this secret for yourself
The Python listing that starts at 1:28 has nothing to do with the prime algorithm or the narration at this point. What gives? Did you insert the wrong file into the video?
April 1st, 2023
Or at least you think you can. As maths are not perfect.
ok, but how will you do numbers with more than two factors, like 21790298087899097494373776975583044612659582164942154887813609701190909992130650129784168219399742498394590?