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).
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
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.
@@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)
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!
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.
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.
damn it, you had to add the comment about python at the end. I was gleefully getting ready to leave a shit comment like "creates fastest algorithm possible.....implements it in python" lol, ok, n/m. I actually paused paused to read the code. good one :)
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!"
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 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.
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?
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.
It is not necessary to show the program. It is necessary to show the demonstration: 1. of the algorithm used (in pseudocode) or 2. the demonstration of the complexity...the rest is meaningless.
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?
ok, but how will you do numbers with more than two factors, like 21790298087899097494373776975583044612659582164942154887813609701190909992130650129784168219399742498394590?
![[Part 1] ทารกน้อยถูกทิ้ง👶 หญิงชราเก็บขวดขายเลี้ยงดูเขาจนโต #โลกการละคร](http://i.ytimg.com/vi/nPTDvFCExks/mqdefault.jpg)
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
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).
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.
I knew when I saw BrainFuck in the code this was gonna be a wild one
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!
Universal search!
Get your algorithms! We have the finest and freshest algorithms! Step right up!
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!
omg the thumbnail is so good
Can't believe I fell for it...
I see, some universal turing machine stuff is coming
I'm so glad that viewing your video wasn't a waste of my time.
--
I saw mention of the "Brainfuck" language, so I ran away screaming.
Took a course with Levin, he's a genius
this is... beautiful.
I'll bet if someone wrote that code in assembly he'd crack rsa
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.
I thought this was going to be about Shor's algorithm. Nice surprise 😊
What are the asymptotic time and space complexities of your algorithm?
So I am now waiting for getting answer of 15 for last 5 days, should I continue?? 😢
damn it, you had to add the comment about python at the end. I was gleefully getting ready to leave a shit comment like "creates fastest algorithm possible.....implements it in python"
lol, ok, n/m. I actually paused paused to read the code. good one :)
I wonder how does this algorithm deal with Encabulator?
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.
So if I find a d^2 factoring algorithm I shall worry for my life or expect a Field medal?
Both.
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!"
Me watching the video on April 5, trying to figure out why a brainfck interpreter is relevant to factorization
Fermat invented this solution before, even if he didn't have the space to write it on his napkin
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)
NOT ME NOT ON APRIL FIRST! NEVER! EVER! NEVER ME!
What is the memory complexity of this algorithm?
i wonder why this video was uploaded 1st april :)
my PC reported this:
File "it.py", line 11
def __init__(self, program: str, input: str):
^
SyntaxError: invalid syntax
Wow and this was created without any understanding of the general number field sieve. 😆
Where’s the other video
It's a April fools video
i forget april 1st videos still exist after april the 1st. i can get fooled all year round (;
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!
They said that it couldn’t be done.
dude did i see brain[REDACTED] ???
I would but I'm a pretty average dev lol so I doubt I could make it better 😂😂😂 . But, this is great thanks
8 months passed so far, any news on this?
It's a april fools video
The words might be hint brainfuck and universal search.
Is it true ?
I got kyphosis watching this.
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. :)
Le risultanze della tavola di lettura , ASCII.
woah
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.
I'm not a programmer. Is "brainfuckexecution" a system command?
Yes, indeed 😂
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
why do programmers have to name classes such weird names *1:28*
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.
You can't keep this secret for yourself
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!
haha blazni
It is not necessary to show the program. It is necessary to show the demonstration: 1. of the algorithm used (in pseudocode) or 2. the demonstration of the complexity...the rest is meaningless.
Or at least you think you can.
As maths are not perfect.
is this a joke? brainfuck? its brute force or am I looking at the wrong code?
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
ok, but how will you do numbers with more than two factors, like 21790298087899097494373776975583044612659582164942154887813609701190909992130650129784168219399742498394590?