The OPTIMAL algorithm for factoring!

[@alansmithee7549]

My computer is currently using 80% of its memory to find the factorization of 15. In other words, it will crash asymptotically.

[@minoubrc4773]

Nailed it asymptotically

[@SuperNolane]

They say memory's cheap nowadays

[@hadibq]

😄

[@TymexComputing]

maybe 15 is a hidden gem prime - i dont get why my comment hasnt showed up (or i cant see it)

[@santius0]

Currently attempting to find the factorization of 8. Truly masterful work, this will bring a revolution 😂

[@alansmithee7549]

A wise usage of memory :^)

[@PolylogCS]

Wow, you got past 4?

[@jerichaux9219]

@@PolylogCS Look at Mr. Chips over here, getting over 2!

[@romain.guillaume]

Well 8 is not the product of two primes, thus even with infinite power you won’t find out…

[@paulkanja]

​@@romain.guillaume jokes on you, I'm checking complex numbers as well

[@RadioactivePretzels]

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.

[@PolylogCS]

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).

[@y_arml]

April 1st should go into history as being the day the Internet was broken.

[@productlog5895]

Indeed

[@ruscul7155]

wtheckkkk

[@YellowBunny]

This is a pretty neat example of how misleading asymptotic complexity can be. :)

[@PolylogCS]

Yep :)

[@machitoons]

a lecture into why smaller big O doesnt always mean faster, wonderful

[@electra_]

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

[@circuitcraft2399]

This technique is called "dovetailing."

[@redsteph]

I was a bit thrilled until I saw we were April 1st... Good one!

[@timschulz9563]

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.

[@anupbarua6151]

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]

@@anupbarua6151 why don't you encrypt them then?

[@anupbarua6151]

@@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?

[@Megaranator]

@@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)

[@anupbarua6151]

@@Megaranator all jokes aside.

[@lane_m]

Brazissimo Reminds me of some of the more "Creative" sorting algorithms that got thrown around when I was in school 😆

[@purplenanite]

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!

[@thomasmackay4]

had several confusions... then i realized that the date arithmetic revealed critical context.

[@anon_y_mousse]

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.

[@bailey6112]

I knew when I saw BrainFuck in the code this was gonna be a wild one

[@9fran9rosatti9]

omg the thumbnail is so good

[@johnchessant3012]

Universal search!

[@casenc]

Can't believe I fell for it...

[@reversefulfillment9189]

Get your algorithms! We have the finest and freshest algorithms! Step right up!

[@AlessandroBottoni]

Great video! 🤣😂 We are eager to see its first commercial implementation. 😂😂

[@PolylogCS]

Coming soon!

[@oresteszoupanos]

I saw mention of the "Brainfuck" language, so I ran away screaming.

[@Tumbolisu]

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.

[@kangalio]

Sleep sort!

[@2kadrenojunkie]

this is... beautiful.

[@aidangomez9852]

Took a course with Levin, he's a genius

[@personanongrata987]

I'm so glad that viewing your video wasn't a waste of my time. --

[@johannesrauch8931]

I see, some universal turing machine stuff is coming

[@vnc.t]

I'll bet if someone wrote that code in assembly he'd crack rsa

[@TymexComputing]

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.

[@scottwilliams895]

[@rutvikrana512]

So I am now waiting for getting answer of 15 for last 5 days, should I continue?? 😢

[@mihajloantic4422]

I wonder how does this algorithm deal with Encabulator?

[@hansisbrucker813]

I thought this was going to be about Shor's algorithm. Nice surprise 😊

[@Darth_Bateman]

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!"

[@lefteriseleftheriades7381]

Me watching the video on April 5, trying to figure out why a brainfck interpreter is relevant to factorization

[@kephalopod3054]

What are the asymptotic time and space complexities of your algorithm?

[@347573]

Fermat invented this solution before, even if he didn't have the space to write it on his napkin

[@VCC1316]

So if I find a d^2 factoring algorithm I shall worry for my life or expect a Field medal?

[@PolylogCS]

Both.

[@rohithpokala]

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.

[@Nioub]

Wow! Does this prove that P = PN?

[@toebel]

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

[@toebel]

(Or rather I should say, *wasnt* known to be NP complete. I came up with quite a marvelous proof this morning…)

[@PolylogCS]

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)

[@logician1234]

What is the memory complexity of this algorithm?

[@SK_1337]

NOT ME NOT ON APRIL FIRST! NEVER! EVER! NEVER ME!

[@simonstebbins3838]

Wow and this was created without any understanding of the general number field sieve. 😆

[@HoSza1]

8 months passed so far, any news on this?

[@Amazing._Games]

It's a april fools video

[@Daniel-ng8fi]

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 :)

[@nonsencephilosophy]

i wonder why this video was uploaded 1st april :)

[@Amonimus]

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.

[@PolylogCS]

The triangle is there to help you understand what's happening, but try to look at the code, too!

[@ferverrel5519]

Where’s the other video

[@Amazing._Games]

It's a April fools video

[@priyanshugoel3030]

The words might be hint brainfuck and universal search.

[@tokajileo5928]

my PC reported this: File "it.py", line 11 def __init__(self, program: str, input: str): ^ SyntaxError: invalid syntax

[@Dardasha_Studios]

I got kyphosis watching this.

[@ski3r3n]

dude did i see brain[REDACTED] ???

[@rujon288]

i forget april 1st videos still exist after april the 1st. i can get fooled all year round (;

[@trinitrotoluene3D]

why do programmers have to name classes such weird names *1:28*

[@handsanitizer2457]

I would but I'm a pretty average dev lol so I doubt I could make it better 😂😂😂 . But, this is great thanks

[@Stopinvadingmyhardware]

They said that it couldn’t be done.

[@rafaelmarcos9733]

I came here just solve a simple programming problem... I think I'll rely on the traditional method.

[@otbot8925]

You didnt get me... Its April 1th. Nice try though

[@Stopinvadingmyhardware]

People still play that game?

[@codeway4374]

@@Stopinvadingmyhardware this video is a material proof

[@ryanqvincent144]

I actually watched this on the 13th of April. It took me a while to appreciate the humor of it. It made me smile. :)

[@aze4308]

woah

[@aashsyed1277]

Is it true ?

[@angelamusiema]

Le risultanze della tavola di lettura , ASCII.

[@simonwillover4175]

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?

[@pigworts2]

There are algorithms that do better than 10^d... (e.g the general number field sieve) - this whole video is meant as a joke.

[@the_cheese_cultist]

this is the universal search algorithm, which can be mathematically proven to be optimal it's also extremely impractical

[@totally_lost1602]

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.

[@JonDisnard]

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.

[@briankleinschmidt3664]

I'm not a programmer. Is "brainfuckexecution" a system command?

[@parryadrian]

Yes, indeed 😂

[@JohnDlugosz]

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?

[@einSteppenwolf]

April 1st, 2023

[@supposta6860]

You can't keep this secret for yourself

[@danielfaller5617]

I havent watched the video yet, but im guessing its social engineering.

[@PolylogCS]

Not really, it's legit! Go and watch it, I think you'll enjoy it!

[@luisrocha241]

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.

[@hhehe24]

haha blazni

[@wanfuse]

is this a joke? brainfuck? its brute force or am I looking at the wrong code?

[@RicardoSantos-oz3uj]

Or at least you think you can. As maths are not perfect.

[@SoI-]

ok, but how will you do numbers with more than two factors, like 21790298087899097494373776975583044612659582164942154887813609701190909992130650129784168219399742498394590?