The OPTIMAL algorithm for factoring!
Вставка
- Опубліковано 31 бер 2023
- 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)
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
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).
This is a pretty neat example of how misleading asymptotic complexity can be. :)
Yep :)
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.
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."
I was a bit thrilled until I saw we were April 1st... Good one!
Brazissimo
Reminds me of some of the more "Creative" sorting algorithms that got thrown around when I was in school 😆
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.
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!
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.
Great video! 🤣😂 We are eager to see its first commercial implementation. 😂😂
Coming soon!
I wonder how does this algorithm deal with Encabulator?
I see, some universal turing machine stuff is coming
omg the thumbnail is so good
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?? 😢
this is... beautiful.
I'll bet if someone wrote that code in assembly he'd crack rsa
I knew when I saw BrainFuck in the code this was gonna be a wild one
Can't believe I fell for it...
I thought this was going to be about Shor's algorithm. Nice surprise 😊
Get your algorithms! We have the finest and freshest algorithms! Step right up!
Universal search!
Took a course with Levin, he's a genius
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 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!
Me watching the video on April 5, trying to figure out why a brainfck interpreter is relevant to factorization
I'm so glad that viewing your video wasn't a waste of my time.
--
What is the memory complexity of this algorithm?
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.
8 months passed so far, any news on this?
Where’s the other video
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!"
Fermat invented this solution before, even if he didn't have the space to write it on his napkin
my PC reported this:
File "it.py", line 11
def __init__(self, program: str, input: str):
^
SyntaxError: invalid syntax
woah
Wow and this was created without any understanding of the general number field sieve. 😆
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)
Is it true ?
I got kyphosis watching this.
i forget april 1st videos still exist after april the 1st. i can get fooled all year round (;
NOT ME NOT ON APRIL FIRST! NEVER! EVER! NEVER ME!
They said that it couldn’t be done.
Le risultanze della tavola di lettura , ASCII.
I would but I'm a pretty average dev lol so I doubt I could make it better 😂😂😂 . But, this is great thanks
i wonder why this video was uploaded 1st april :)
The words might be hint brainfuck and universal search.
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. :)
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
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.
why do programmers have to name classes such weird names *1:28*
I'm not a programmer. Is "brainfuckexecution" a system command?
Yes, indeed 😂
haha blazni
You can't keep this secret for yourself
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.
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
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!
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?