There have been a few comments about the names "polynomial and exponential" -- they seem off to viewers who are coming from a CS background. I'm a cryptographer and algorithmic number theorist, and in my area this terminology is standard. And in fact, it _does_ agree with the standard CS approach to complexity, but it takes a moment to see why. Check out 7:18 where I address this issue. The point is that it's polynomial/exponential in the size of the input that is fed to the computer, and the size of the input is log(N), the number of digits of N (because that's what you feed to the computer, the digits of N). What's actually confusing is that somehow we think of factoring as an algorithm that takes in N. But it doesn't -- factoring is actually an algorithm that takes in a decimal representation of N. But I see now that I should have approached this differently for an audience with some CS background. Thanks for all your support and comments!
Well, I strongly disagree. Notion of time complexity is telling how something grow based on its arguments. So, if you say O(log(N)) it grows logarithmically over N, and if you say O(N) it grows linearly over N. If you want to say that N is exponential, then say D = number of digits, and write down time complexity as O(10^D), and it is exponential over D. Or O(D) would be linear over D. Explanation at 7:18 is just an excuse for us who has CS background. For other people it's just disinformation for almost 2 minutes. Everyone who study CS will agree that algorithm saying 1 to N is *linear* over N. And, the only way to say it's exponential, is to clarify that it's exponential over number of digits. You should say it clearly from the beginning, to not confuse everyone who learns it in the first place! But you decide to make excuse afterwards, to make confused people to be even more confused. Regarding to how in number theory usually say, there is common notion to have N as number of *digits*, and thus complexity of say from 1 to number itself is O(10^N) because N is now number of digits! For example, Pollard-Strassen time complexity noted O(n^(1/4) log n) where n is number itself. While Karatsuba multiplication time complexity is O(n^1.58) where n is number of digits. Even though Pollard-Strassen O(n^(1/4) log n) we all interested in factorization regarding number of digits, so it's called exponential (over number of digits). And, as addition, I'll say that many well known algorithms has multiple variables in time complexity. Easiest example is breadth first search algorithm, its time complexity O(|V| + |E|), and you can say that it's linear over number of vertices and edges, but it would be mistake if you say it's exponential. But, if we have task where there are always all edges between all vertices, then |E| = O(|V|^2) and O(|V| + |E|) becomes O(|V|^2) and you can say its time complexity is quadratic over number of vertices.
@@r75shell Youpi, someone talking precisely the things that I teach this semester. I teach complexity and calculability (NP completness). A core idea is the following. Suppose that A and B are decision problems (e.g. is a graph 3 colorable?) and that there is a prograpm f:A->B is a function which transforms yes instances in A to yes instances in B and no instances in A to no instances in B. If these is an algorithm to decide B, then there is an algorithm to decide A: just decide f(A). But it may be that the size of f(A) is much bigger than the size of A. There can be an exponential blow up. Then this encoding f is not that interresting. We thus say that A is polynomialy reducible to B is the size of f(A) is polynomialy bounded by the size of A. Now the link to you argument with Proof of Concept. Some problems can contain integers. For exemple, given a graph G and an integer k, is G k-colorable. Or given a set of linear integer equations, does there exist an integer solution. There, the encoding of the integer matters. Some problems that are difficult (i.e. NP hard) if the integers are encoded in binary can become easy if they are encoded in unary (5 is encoded by 11111). An example of such a problem is 2-partition. Some problems remain hard regardless of the encoding. An example of such a problem is 3-partition. And the general assumption is that all integers are encoded in binary form. Thus Proof of Concept is right. Indeed, you rarely encode numbers in unary, thus, as she explains, the size of the input (which is what we care about) is not n but log n. Thus a polynomial algorithm on numbers is polynomial is the log of these numbers. The example that you give with graphs is interesting because any encoding of a general graph on n vertices has size at least n. Thus this "size of the encoding of numbers" is most of the time not a problem for graphs. Indeed, in the case of k-coloring, obviously if k is greater than the number of vertices, the answer is yes. We can thus assume that k is at most the number of vertices of the graph, and the encoding of k "take no additional place".
@@fredericmazoit1441 what you describe reminds me different time complexity notation. I don't remember its name, but it's about time complexity for compressed input. Also, there is time complexity where you also take into consideration representation of each value. So, for example number with value V would take log(V) to store. Thus, graph with V vertices without edges would just take log(V) bits to tell that there is V vertices. But then, edge would need 2 * log(V) bits to store two indices. So eventually, graph with V vertices and E edges would take log(V) + 2 * log(V) * E bits, which is already O(log(V) * E) and thus my claim that breadth first search works in O(V + E) becomes invalid because O(V + E + log V + 2 * log(V) * E) is O(V + E log V). Also space complexity would be different. Probably there is some method to compress it and avoid that, but it doesn't matter if I clarify format in which it's stored is exactly as I described above, then complexity is correct. My point, is each time when complexity is stated, it should be clearly stated in what terms it's polynomial/linear in the first place, if it's educational video. Or, if it was by mistake it should be in other video clarified. If you make excuses in the same video after your words, it's bad from narrative side.
@@r75shell Another comment: You've been lied ! You probably think that bubblesort runs in O(n²) time when n is the size of the list to be sorted, and that mergesort (having complexity O(n.log n) is optimal). Right ? False ! The complexity of bubblesort being n² supposes that the numbers have constant size (e.g. 64 bits), and that each comparison can be done in constant time. But if the integers have constant size, then bucketsort (in O(n)) is more efficient that mergesort. If you are sorting bignums, this operation takes O(size of the representation of the numbers). This is obvious if you try to sort lists of strings (with the lexicographic order). Now why are your teachers been lying to you ? To make things simpler. Indeed even the "real" complexity of bubblesort is not obvious. And in "real life applications", the assumption that numbers have constant size and that comparison can be done in constant time is sensible. Now obviously, when doing crypto stuff, the assumption that numbers have constant is false., and we have to go back to the real stuff.
So well done! As Kate’s non-mathematician mother, I’ll just add how much I enjoyed Lehmer’s poetic insistence on the beauty of pure math despite some feeling, even in its practitioners, that it needs papering over with practicality. Reminds me of Henry David Thoreau’s words: “Many men go fishing all of their lives without knowing that it is not fish they are after."
As Kate’s random youtube viewer, only going by this video, you’ve done an awesome job as a mother. She is someone I respect and aspire to emulate. Well done.
wonderful pacing, great tangents for the human context, great summing-up of parts so i don't lose the story if i glaze my eyes over some details. gives me the kind of hype for math Vi Hart's videos did in high school! I watch a lot of math videos on here, and this is my favorite in a long time. i didn't know about these paper things, very cool!
I watched this video in its entirety. I did not check its view count. I thought to myself multiple times on just how high-quality the production is. The handwriting is neat and elegant. The video is a mix of visualized ideas and their mathematic representations in parts such that one never overshadows the other. The topic itself is excellent, something I'd never heard of yet am now intrigued by. The narration presents concepts in ways that are clear and concise yet offer a wealth of room for independent thought. This video has (2^2 x 307) views. *This is the definition of criminally underappreciated content.*
Well, when I got here, it had made its way up nearly a dozen fold to 14,419 views (prime), and reloading after stepping away for an errand before completing my own viewing, it's now up to 31 x 479 views, which is indeed an order of dozenal magnitude (if I might coin that?), so... I guess the algorithm is catching on to it? Yay! It is indeed good. I stumbled a bit on the recurrence relations, but in the end, I think I mostly understood, and I certainly enjoyed the journey. Thanks, Kate/PoC! P.S. Oh, hey, just noticed this was a #SoME1 entry... Cool! And I see you have lots more content. I'll explore!
This was great! The summer exposition of Math has really spoiled us in the community with fantastic videos. Interestingly a lot of the techniques used here reminded me of algorithms we used to find primes, always neat to see old things from a new perspective.
This is an amazing video. So many moments where my head hurts then suddenly it just becomes clear exactly what you're saying. Really good explanations.
I love the Farey Sequence and all of the wonderful patterns it forms. I was once absolutly sure I was on the verge of constructing an algorithm for constructing/finding twin primes and by extension proving the twine prime conjector and fame and fortune. I did not, but I always feel a jolt of excitment whenever I hear about Farey sequences. There are too many patterns not to expect to find plenty of interesting and fun mathematics.
This video is really amazing! The history of hand factorization fascinates me, from Fermat mistakenly believing 2^32+1 was prime (he missed the "small" factor 641) to F. N. Cole factoring 2^67-1 in "three years of Sundays". This topic isn't covered as much now that computers can do what they do, but by studying it we're doubling down on that great quote by Lehmer, even as factorization has found practical applications.
Thank you, great video! You struck a good balance between visual thinking and symbolic thinking (a lot of math youtubers are visual but too unrigorous/hand-wavey, or rigorous but too unmotivated/mysterious). Great work!
Your comment made me smile! Actually, when I was a kid, my parents brought them home from the university as notecards, since they had leftover boxes there. Now I wish I'd kept some, but we just used the backs for grocery lists.
@@BrightBlueJim I envy you that experience! It may not have been high-powered computation by today's standards, but it must have been exciting to be at the forefront of new technology.
Punch cards are fun in that whenever I mention doing programming to anyone older than 50 they will inevitably start talking about how they had to punch programs into cards. Then they'll ask me to help them figure out the facebook login page. I'm convinced punch cards were actually cursed talismans that sucked the computer prowess out of people.
@@Colopty Allowing for the likelihood that you're just having some fun, the two things aren't related at all. Both are user interfaces for making use of computers, but that's about all they have in common. Punch cards were an early (but not the earliest) way of entering commands and data on a line-by-line basis, and this transferred almost seamlessly into line-based terminals using either electromechanical teleprinters or electronic displays with associated keyboards. But either of these required a lot of learning on the user's part, since they had to know what commands were available to type at any given moment, and the exact syntax of those commands. The introduction of the graphical user interface based on the WIMP principle, integrating (w)indows on a screen, (i)cons, (m)enus, and a (p)ointing device, made computers usable by people with little or no knowledge about how computers actually worked. Which was a great thing, because people could do useful things with computers without having to know anything about them. The down side of this is that application developers invented their own visual languages, many developed independently of others, so that instead of just knowing how "computers" worked, the user had to know how to operate each application. I have been involved with computer development for over fifty years, as everything from a user to a software developer to a hardware engineer building embedded computer systems. But none of this experience helps in the slightest when I pick up a new cell phone whose user controls have been completely reinvented by the manufacturer. I JUST WANT TO ADD A NEW CONTACT!!!!!!!!!! Since you mentioned Facebook, this is another problem: you CAN NOT learn Facebook. It is simply not possible, because Facebook can (and does) change its user interface on a daily basis. Familiar commands disappear overnight, being moved to a different menu that I can only assume made some kind of sense to somebody at Facebook. I don't use Facebook myself, but I DO use UA-cam in my evening job, which is live-streaming sports events. It's often an adventure when I go to do something I do every week, only to find that UA-cam has "improved" its user interface, and I get to go on an easter egg hunt just to do my job. Invariably, the on-line help lags behind the live changes, so it's sink or swim when it comes down to "will I be able to stream tonight?". So yeah, I'm that guy. But I would amend your observation: it is user interfaces that change at the whims of unknown and largely clueless people, that suck the computer prowess out of people. But maybe you're right - using punched cards did condition me to expect that something that works one day will also work the next, so yeah, my failing.
This has been one of the most enjoyable videos I've found in a while . Especially loved the reminder of the simple human beauty of mathematics! The long and softly read excerpts are something so sorely missing from a lot of more individualised mathematics videos out there. If it pleases, please keep this up!
Thanks for a well constructed presentation. In roughly 65 years of recreational math I'd never encounter Lehmer's Disks. About 15 years ago I informally explored the patterns in continued fractions for square roots near 'N squared'. Fun Stuff. Enjoyed the video.
Your intuition is totally correct! Those "bubbles" I drew over the Farey subdivision can be considered geodesics in the upper half plane model of the hyperbolic plane. Hyperbolic geometry has a big role to play in continued fractions. Here are some links: homepages.warwick.ac.uk/~masbb/HypGeomandCntdFractions-2.pdf and www.asiapacific-mathnews.com/06/0602/0010_0014.pdf
As a first time viewer and a lover of math, this was beyond what I expected clicking on around midnight. Tons of details and very well spoken. That was beautiful. Great job. Now, I have to get/make a set of Factor Stencils
08:55 The AKS primality test published in 2002 shows that checking if a number is prime or not (not factoring) is polynomial, though it may be impractical for large numbers
So essentially we can throw one additional guess at the number in polynomial time, the guess that there are no nontrivial factors of our number. Neat, but yeah not a real improvement to factoring the number
Sending encouragement! The works done by these deep thinkers from the past gives one hope for humanity…much needed. These examples only help us if people like you find, study and share them with others. Thanks so much for your hard work to share this. I look forward to more :).
This was an excellent informative video. As someone who doesn’t have a mathematics background I was able to follow along and understand it fully. Which is awesome for me every time I’ve seen these stencils before I’ve always just thought “that would some cool looking art.” Now I know what it does and how to use it that art can be even more fun.
Wow, this is a really cool video about a topic that I absolutely never would've heard about otherwise. The presentation is very engaging and easily kept me interested the whole time. I think I audibly said "woah, huh, that's so neat" at several points.
Farey - I am reminded of a couple of things. 1) riding in the car on long trips and seeing the patterns created by orchards; 2) learning x-ray crystallography.
Really cool explanation! Loved the 'practical' analogies and examples! I was genuinely surprised that the video ended where it did, could have easily watched another 10 minutes of explaining how the placing of the holes in the stencils was computed!
Very good video on a very interesting and uncommonly covered topic. Reminds me of slide rules. One thing that I found particularly interesting was Lehmer's mechanical computing device, which I had not heard of before. I knew of the Antikythera mechanism, Babbage, and Lovelace, but not that. The subject is also of particular interest to me because of my interest in the idea of being "ahead of one's time" (which I think is a misnomer) and when and how people end up in such a state.
What is the -pattern- on each stencil? I get the sieve concept in general, the recurrence relations and the Farey-Stern-Brocot tree, but for each stencil...the circular pattern of holes... where does that come from? Presumably you don't have to make it circular...what would it look like if the stencils were rectangular... what would the pattern look like then?
Hey, I was the 1000th like! Very nice explanation! As a Comp-Sci nerd, your descriptions of polynomial time algorithms vs exponential ones blew my mind. I am used to thinking of them from a different perspective, and It's cool to see it another way.
intense, a paper fast fourier transform, amazing video. The farey subdivision would be the energy distribution of natural frequencies to make a unit square wavelet
Can you explain this a bit more? what does the unit square wavelet correspond to- a prime factor? and natural frequencies of what, perhaps you mean the number line's size up to a given magnitude? I looked up each of the terms you used but can't put it together. thanks :)
I could not sleep, so made tea at 03:50. (That’s the time I made tea! - not a marker in the video - as UA-cam has interpreted.) UA-cam’s algorithm gave me this video to watch, and I liked the look of the punched stencils. I watched, with an old degree in CS with Cybernetics. The maths runs too quickly for me, and I can’t follow the reasoning at speed. So, watch it again - which I shall do. The bit I really liked was Lehmer’s words on enjoying the beauty of something just for what it is, (at 10:14 in) rather than fighting for a reason for it; or an outcome from it that’s ‘useful’. I enjoyed this video because it produced something I thought beautiful - both the theory and the circular stencils with their precise holes. It returned me to high-school maths lessons, and punching holes in colourful paper - the cerebral equivalent, for me, of ‘motherhood and apple pie’. Most enjoyable, and beautifully video’d and composed. Presently, I don’t understand the number written at the top of each stencil. So, more tea, and another runthrough … Matt Lee
Amazing presentation! I am impressed with the "analog computers" (stencils & Geo Board) but even more with the explanation how they represent the "formula math". There are a number of topics in this video that would deserve their own detailed explanation. Well done, keep up the good work!
While the Geo Board is an analog computer, the stencils are not. There is no parameter that is analogous to the number being processed. Each hole position represents a specific, discrete number, whose physical position on the disc is arbitrary (which is why it makes no difference whether they are in this spiral pattern or in the pattern of holes on a computer punch card. This is digital.
In fact, each stencil is an implementation of a read-only memory with a word size of 1 bit, where the address is the physical location on the disc, and its output is 1 or 0, where 1 is represented by a hole. Stacking multiple discs creates an AND function of the outputs of the discs that are stacked. Again, purely digital.
Great video- Your stencils (and video) are much nicer than mine! And thanks for giving a complete and understandable explanation- I'm not a number theorist so I never really fully understood it in my bones. Thanks!
Your videos are wonderful! I love computing machines -- I find it fascinating to see arithmetic take physical form. I recommend everyone who enjoys the idea of factor stencils check out your channel!
@@ProofofConceptMath You two should do a collaboration where you use Chris's calculating machines to find the Q-values of a number and then use your stencils to test them.
Great video! The slope N^(1/2) thing at 17:30 caught me off guard at first because it seemed unmotivated. It took me embarrassingly long to figure out it was explained later. But once I understood that I really enjoyed it!
This is fantastic. I'm very tempted to make some of these stencils myself, it seems like an incredibly fun project to really understand the math thoroughly. Either way, thank you for a delightful and informative video.
You can! There's a github link in the description, or you can program a better version from scratch. The paper cutting machine is really fun to play with.
This is absolutely amazing, wow! I know of Lehmer from "Lehmer LCGs" which can be used for generating pseudo-random numbers. I had no idea about this amazing topic-- I'll be adding this to my "watch again" list. You are so freaking cool @__@
I feel like the section sieving for primes with quadratic residues would benefit greatly from some examples while the following section how many stencils are needed really didn't need that much explanation. I had to watch the quadratic residues section a few times to get into my head what x, n and the rest were (still not 100 on those btw) but when you said, each stencil gives half the number of numbers, I got it immediately.
Regarding how this algorithm doesn't circumvent the exponential nature of the problem, in addition to the stencils taking exponential time to make, they also take exponential time to use (technically). Once you assemble your stencil stack, you have to determine which holes aren't blocked. In a practical sense, we can scan practical sized stencils pretty quickly, but as you keep scaling up the number of primes represented on the stencils, the time to check them will increase linearly in the number of prime factors you need to check (so exponential in the number of digits of the input, N). Any method which would actually spot all the open primes simultaneously would effectively be doing massive parallel computation, so the actual time might be subexponential in that case, but you'd still be doing exponential computation in a technical sense. Also, the time taken stays small only as long as your parallel computation method could also be scaled indefinitely. In other words, if you have infinite computation resources, almost everything looks like constant time... 😁 Anyway, great video. I had to watch it a few times because it was easy to miss that the prime is used as them modulus when calculating whether to punch a hole for that prime. I kept wondering what "n" was in that case because obviously you don't know the input number ("N") at the point you are preparing the stencils. But eventually, I caught that detail and finally understood. As I said, neat video.
That was a really beautiful metaphor about wandering the wilderness and believing for some reason that you must haev a net or gathering bag -- some purpose for being out there
At 6:00 that is not an exponential algorithm. That's a linear algorithm. Linear is if it takes n steps for n items. Exponential is if it takes x^n for n items where x>1. At 6:18 that isn't a polynomial algorithm. That's a logarithmic algorithm. Polynomial is where it takes a + bn + cn^2 + dn^3 … steps. These are very different and how are you getting this wrong?
I don't understand how the successive values of the variable Q are calculated. I can't find the same thing as in the video or the provided PDF. Let N=8416909 (like in the video). For Q0, I find 1108 by applying the formula Q0=N-P². On the other hand, I have a problem from Q1 and for the other Qs. According to the recurrence formula : Q1 = S1 × (P0-P_-1)+Q_-1 = 5 × (2901-0)+1 = 14506. But, this is supposed to be 1311. Then, for Q2: Q2 = S2 × (P1-P0)+Q0 = 4 × (2639-2901)+1108 = 60. Whereas it is marked that it is supposed to be 1244. What am I missing?
Oh my gosh! Thank you (and one or two others today) so much for pointing this out! I'm so sorry! I made a copying error (I was copying, instead of computing live, for the sake of the video quality). I have edited my description on the video to reflect this, but full details and correction can now be found at math.colorado.edu/~kstange/stencils/stencil-users-guide.pdf. Please let me know if you find any further issues.
I didn't find the time complexity explanation confusing, I thought it was pretty standard in CS to evaluate complexity based on the size of the representation when the operations over the numbers aren't "free"
Computational complexity isn't the end of everything. In fact, there is already a polynomial algorithm to find a factor, but it requires a quantum computer, which currently can only carry
The one-time code generator you show at 9:30, while manufactured by RSA Security, does not use the RSA algorithm or anything else based on prime factorization.
@@ProofofConceptMath You're welcome! It is based on a SHA-1 HMAC of a counter using a 128-bit to 256-bit key. In this particular case the counter is derived from a clock (usually, seconds since the Unix epoch divided by 30). See RFC 4226 (counter-based) and RFC 6238 (time-based) for details.
At around a minute, you're doing some calculations involving P, Q, and S. They look fine, except every line in which you compute Q is wrong: 5(2901 - 0) + 1 = 14506, not 1311 4(2639 - 2901) + 1108 = 60, not 1244 4(2605 - 2639) + 1311 = 1175, not 2247 However, rearranging the "P" values inside the parentheses, you can get the Q values you claim: 5(2901 - 2639) + 1 = 1311 4(2639 - 2605) + 1108 = 1244 4(2605 - 2371) + 1311 = 2247 etc. Did you mean these latter, rather than those former? Overall, lots of good content here - WELL DONE!! Fred
You are right! Thank you (and one or two others today) so much for pointing this out! I'm so sorry! I made a copying error (I was copying, instead of computing live, for the sake of the video quality). I have edited my description on the video to reflect this, but full details and correction can now be found at math.colorado.edu/~kstange/stencils/stencil-users-guide.pdf. Please let me know if you find any further issues.
@@ProofofConceptMath Splendid! This method intrigues me, having had a bit more than passing interest in a few areas of number theory for years. So I wanted to see this corrected, for benefit of all other viewers of your video. And you've come through with flying colors, taking my comment as constructive, not hostile, criticism. Another adherent of the principle that the math is perfect; while sometimes we mathematicians are less so. Fred
Is anyone able to help me understand the statement at 13:20? If we take the case of N = 10, which gives quadratic residues mod N of {0,1,4,5,6,9}. The prime divisors of 10 are 2 and 5. The quadratic residues mod 5 are {0,1,4} and those of 2 are {0,1}. x = 5,6 and 9 are all cases where the Fundamental Principle is failing to hold. What am I missing? Is the logic meant to be the other way around?
Great stuff! I LOL on the "rather abitrary decimal system famously dictated by our biological makeup". Reminded me of Tom Lehrer's song New Math in which he said: "Base eight is just like base ten really - If you're missing two fingers"
You are right! Thank you (and a few others) so much for pointing this out! I'm so sorry! I made a copying error (I was copying, instead of computing live, for the sake of the video quality). I have edited my description on the video to reflect this, but full details and correction can now be found at math.colorado.edu/~kstange/stencils/stencil-users-guide.pdf. Please let me know if you find any further issues.
What puzzles me: Why do the stencils show 3 as prime factor of 8416909? It's not divisible by 3. I mean the number down right of the equal sign, when 631 x 13339 is displayed. Is it just "not yet" covered or not completely visible?
This seems a little bit similar to bloom filters. Thinking. In a (simpler but somewhat broken/inefficient version of a) bloom filter, for each input, for each bit, about half the time the hash will have that bit, and here, for each residue, and each prime, about half the time the prime will have that residue (provided that the residue is smaller than the prime). [correction: in an actual bloom filter, I guess instead of each bit having a 50/50 chance, instead there is supposed to be a uniform distribution of which k of the n bits will be set to 1, not just a single hash. Whatever. That makes it more complicated and makes the analogy worse. I guess I’m just describing a worse version of bloom filters instead of the good version.] With a bloom filter, [the following might have gotten some polarities flipped because it is by memory, but the general idea is basically the same] you take the OR of all the hashes of the items in the list to be recognized, and then if an item is hashed, if it is in the list, all the bits in its hash will be there, so it can be seen to be “maybe in the list”. And, if the hash of something has a bit set that the filter doesn’t have, it definitely isn’t in the list. With these filters, I suppose the analogy would be that the number to be factored corresponds to, the list of items to potentially recognize? Or, like, the prime factorization would correspond to that list. Where, a prime is only potentially a factor of the number if, all of residues of the number are residues of the prime, and so, if the prime lacks a residue (if the item’s hash has a bit set which is not set in the filter) then the prime is not a factor (the element is not in the list). So, the residues correspond to the different bits I guess? (And the analogy has some true/false flipped around I guess) So, uh, I guess that analogy kinda works? Though, with a bloom filter you don’t get a list of items that might be in the list.. Hmm. Thinking I might be trying to go about this analogy in the wrong way
So couldn't Lehmer stencils be modeled virtually in a large enough computer algorithm to factor any size number. Creation of the algorithm would be exponential, but using it would be polynomial once created.
Well, modern RSA uses 2048 bit keys, so using the estimates in the video, factoring with this method would need a deck of 2^1024 stencils, each 2^1024 positions in size. Storing these, even electronic versions, would be challenging. Modern estimates put the number of atoms in the universe at about 2^265.
I'm working through your example to get a better understanding of how the recurrence equations relate to the rational approximations of the square roots, and I'm confused by the calculations you've written down at the beginning. For your second Q value, you've written Q = 5 * (2901 - 0) + 1 = 1311, but 5 * 2901 + 1 is 14506. Similarly, for the third Q value you have Q = 4 * (2639 - 2901) + 1108 = 1244, but that expression actually equals 60. However, 1311 = 5 * (2901 - 2639) + 1, and 1244 = 4 * (2639 - 2605) + 1108 - i.e. the values you'd get if you used P_n instead of P_(n-2) in the formulas you show. What are these values actually supposed to be?
Oh my gosh! Thank you so much for pointing this out! I'm so sorry! I made a copying error (I was copying, instead of computing live, for the sake of the video quality). I have edited my description on the video to reflect this, but full details and correction can be found at math.colorado.edu/~kstange/stencils/stencil-users-guide.pdf. Please let me know if you find any further issues.
Nit: it's more than twice as hard to do multiplication or division of twice as many digits. There's no known linear multiplication algorithm, and I'm going to take a stab in the dark and say a student wasn't doing FFT on paper by hand, so it's likely at least 4x as hard to use twice as many digits with a reasonable algorithm that a human would use.
Hehe, yes, it was long division by hand, and I suppose the paper gets twice as long as well as twice as wide, at least... in any case, you are right! Thanks for the nit.
This is super cool, but at the same time a bit depressing with how useless it has become, because now anyone who knows any programming language can easily factor any number up to 100 million knowing only the definition of what the word "factor" means, and anyone who knows that you can have at most one prime factor bigger than sqrt(n) can instantly factor numbers in the quintillions. It's wild to think that this used to be something that was hard to do.
Briefly touched too many related topics, to show how this thing work briefly. It's sad how much time it would need to explain everything related at some good level. :(
Prime numbers are weird and beautiful, aren't they? So, I have a question: is it a matter of computational power for the human race to be able to factor huge (by that I mean gargantuan type gigantic-ish ones) numbers? No matter how many algorithms we come up with and no matter how many contraptions we build and process in order to understand the deepest insights on the mysteries of how numbers work, will it always be futile to alleviate the mystery part of the way the numbers work? Will it always be like wandering blindly in the woods? Can the human race ever achieve a polynomial complexity algorithm? PS. Love your video totally. Well done, it's awesome! And so is mathematics, is it not?
> So, I have a question: is it a matter of computational power for the human race to be able to factor huge (by that I mean gargantuan type gigantic-ish ones) numbers? If I'm understanding you correctly, I think the answer is yes, sort of. Broadly there are three ways we might factor a number: * Trying lots of options one by one, either after we get the number (basic trial division), or going through them in advance (Lehmer stencils). This is the best we can currently do, but it needs huge amounts of computing power. That's hard to get for big numbers and basically impossible for gargantuan ones. * Trying lots of options _at once_ \*, with physics hacks (e.g. Shor's algorithm for quantum computers). This is technically and mathematically clever, but it still boils down to "try lots of things". No deep truths about the prime numbers here. It's also really limited by _quantum_ computing power - currently our most powerful quantum computers can only factor 2-digit numbers. * Using a deep understanding of number theory to factor them more quickly (maybe involving proofs of the Riemann hypothesis and/or P=NP). Currently we have no idea how to do this, or if it's even possible, despite the brainpower (and computer assistance) of our smartest mathematicians.
\* From reading the Wikipedia article it sounds like Shor's option tries lots of options at once, but I don't think I've got the whole picture; the experts don't seem to describe quantum computers that way.
Why are you calling a logarithmic algorithm polynomial and a linear algorithm exponential? Did I miss something Ah wait a minute you're saying it's polynomial in the digits of N, not in N. That was kinda confusing for a second but I got it now, nevermind that's my bad.
Yup, you got it. When I want to factor a number N, the input is actually the number written out in decimal (or binary or whatnot) notation. So the size of the input is the number of digits, not the number itself. For example, 100 has size '3', because it has 3 digits. So an algorithm that takes log(N)^2 time to factor N is taking X^2 time in the input size X. It's "polynomial" for this reason. It's the same definitions as in a CS class, but the trick is what you consider the "size" of the input. When factoring N, the size of the input is log(N) -- the number of digits. (This is admittedly a point I should perhaps have addressed a little differently in the video.)
@@ProofofConceptMath I had the same moment of confusion and realization as pendragon. By "convention" (akak one of the rules people assume but never mention so is it even real) I'm used to "N" being the count of a thing. Maybe it would have been clearer to use "D" or O(# of digits) or something. I really enjoyed this video. Weirdly, I'd heard of the mediant operation, but never the Farey sequence. What a gem!
There have been a few comments about the names "polynomial and exponential" -- they seem off to viewers who are coming from a CS background. I'm a cryptographer and algorithmic number theorist, and in my area this terminology is standard. And in fact, it _does_ agree with the standard CS approach to complexity, but it takes a moment to see why. Check out 7:18 where I address this issue. The point is that it's polynomial/exponential in the size of the input that is fed to the computer, and the size of the input is log(N), the number of digits of N (because that's what you feed to the computer, the digits of N). What's actually confusing is that somehow we think of factoring as an algorithm that takes in N. But it doesn't -- factoring is actually an algorithm that takes in a decimal representation of N. But I see now that I should have approached this differently for an audience with some CS background. Thanks for all your support and comments!
Yeah, in CS, N itself is the size of the input - a linear-time algorithm is called O(N), for instance.
Well, I strongly disagree. Notion of time complexity is telling how something grow based on its arguments. So, if you say O(log(N)) it grows logarithmically over N, and if you say O(N) it grows linearly over N. If you want to say that N is exponential, then say D = number of digits, and write down time complexity as O(10^D), and it is exponential over D. Or O(D) would be linear over D.
Explanation at 7:18 is just an excuse for us who has CS background. For other people it's just disinformation for almost 2 minutes. Everyone who study CS will agree that algorithm saying 1 to N is *linear* over N. And, the only way to say it's exponential, is to clarify that it's exponential over number of digits. You should say it clearly from the beginning, to not confuse everyone who learns it in the first place! But you decide to make excuse afterwards, to make confused people to be even more confused.
Regarding to how in number theory usually say, there is common notion to have N as number of *digits*, and thus complexity of say from 1 to number itself is O(10^N) because N is now number of digits! For example, Pollard-Strassen time complexity noted O(n^(1/4) log n) where n is number itself. While Karatsuba multiplication time complexity is O(n^1.58) where n is number of digits. Even though Pollard-Strassen O(n^(1/4) log n) we all interested in factorization regarding number of digits, so it's called exponential (over number of digits).
And, as addition, I'll say that many well known algorithms has multiple variables in time complexity. Easiest example is breadth first search algorithm, its time complexity O(|V| + |E|), and you can say that it's linear over number of vertices and edges, but it would be mistake if you say it's exponential. But, if we have task where there are always all edges between all vertices, then |E| = O(|V|^2) and O(|V| + |E|) becomes O(|V|^2) and you can say its time complexity is quadratic over number of vertices.
@@r75shell Youpi, someone talking precisely the things that I teach this semester.
I teach complexity and calculability (NP completness). A core idea is the following.
Suppose that A and B are decision problems (e.g. is a graph 3 colorable?) and that there is a prograpm f:A->B is a function which transforms yes instances in A to yes instances in B and no instances in A to no instances in B. If these is an algorithm to decide B, then there is an algorithm to decide A: just decide f(A). But it may be that the size of f(A) is much bigger than the size of A. There can be an exponential blow up. Then this encoding f is not that interresting. We thus say that A is polynomialy reducible to B is the size of f(A) is polynomialy bounded by the size of A.
Now the link to you argument with Proof of Concept.
Some problems can contain integers. For exemple, given a graph G and an integer k, is G k-colorable. Or given a set of linear integer equations, does there exist an integer solution. There, the encoding of the integer matters. Some problems that are difficult (i.e. NP hard) if the integers are encoded in binary can become easy if they are encoded in unary (5 is encoded by 11111). An example of such a problem is 2-partition. Some problems remain hard regardless of the encoding. An example of such a problem is 3-partition.
And the general assumption is that all integers are encoded in binary form. Thus Proof of Concept is right. Indeed, you rarely encode numbers in unary, thus, as she explains, the size of the input (which is what we care about) is not n but log n. Thus a polynomial algorithm on numbers is polynomial is the log of these numbers.
The example that you give with graphs is interesting because any encoding of a general graph on n vertices has size at least n. Thus this "size of the encoding of numbers" is most of the time not a problem for graphs. Indeed, in the case of k-coloring, obviously if k is greater than the number of vertices, the answer is yes. We can thus assume that k is at most the number of vertices of the graph, and the encoding of k "take no additional place".
@@fredericmazoit1441 what you describe reminds me different time complexity notation. I don't remember its name, but it's about time complexity for compressed input. Also, there is time complexity where you also take into consideration representation of each value. So, for example number with value V would take log(V) to store. Thus, graph with V vertices without edges would just take log(V) bits to tell that there is V vertices. But then, edge would need 2 * log(V) bits to store two indices. So eventually, graph with V vertices and E edges would take log(V) + 2 * log(V) * E bits, which is already O(log(V) * E) and thus my claim that breadth first search works in O(V + E) becomes invalid because O(V + E + log V + 2 * log(V) * E) is O(V + E log V). Also space complexity would be different. Probably there is some method to compress it and avoid that, but it doesn't matter if I clarify format in which it's stored is exactly as I described above, then complexity is correct.
My point, is each time when complexity is stated, it should be clearly stated in what terms it's polynomial/linear in the first place, if it's educational video. Or, if it was by mistake it should be in other video clarified. If you make excuses in the same video after your words, it's bad from narrative side.
@@r75shell Another comment: You've been lied !
You probably think that bubblesort runs in O(n²) time when n is the size of the list to be sorted, and that mergesort (having complexity O(n.log n) is optimal). Right ? False !
The complexity of bubblesort being n² supposes that the numbers have constant size (e.g. 64 bits), and that each comparison can be done in constant time. But if the integers have constant size, then bucketsort (in O(n)) is more efficient that mergesort.
If you are sorting bignums, this operation takes O(size of the representation of the numbers). This is obvious if you try to sort lists of strings (with the lexicographic order).
Now why are your teachers been lying to you ?
To make things simpler. Indeed even the "real" complexity of bubblesort is not obvious. And in "real life applications", the assumption that numbers have constant size and that comparison can be done in constant time is sensible.
Now obviously, when doing crypto stuff, the assumption that numbers have constant is false., and we have to go back to the real stuff.
So well done! As Kate’s non-mathematician mother, I’ll just add how much I enjoyed Lehmer’s poetic insistence on the beauty of pure math despite some feeling, even in its practitioners, that it needs papering over with practicality. Reminds me of Henry David Thoreau’s words: “Many men go fishing all of their lives without knowing that it is not fish they are after."
As Kate’s random youtube viewer, only going by this video, you’ve done an awesome job as a mother. She is someone I respect and aspire to emulate. Well done.
@@matthewpugh5965 as yet another random viewer, I agree.
@@madkirk7431 I'm here claiming my stake in this video at less than 11,000 views before it blows up.
You have a wonderful daughter!! Very clear.
Your daughter literally helped catalyze a transformation in my perspective on numbers
wonderful pacing, great tangents for the human context, great summing-up of parts so i don't lose the story if i glaze my eyes over some details. gives me the kind of hype for math Vi Hart's videos did in high school! I watch a lot of math videos on here, and this is my favorite in a long time. i didn't know about these paper things, very cool!
I watched this video in its entirety.
I did not check its view count.
I thought to myself multiple times on just how high-quality the production is. The handwriting is neat and elegant. The video is a mix of visualized ideas and their mathematic representations in parts such that one never overshadows the other. The topic itself is excellent, something I'd never heard of yet am now intrigued by. The narration presents concepts in ways that are clear and concise yet offer a wealth of room for independent thought.
This video has (2^2 x 307) views.
*This is the definition of criminally underappreciated content.*
Thank you! That's such a nice comment! And I love that you factored the views!
Well, when I got here, it had made its way up nearly a dozen fold to 14,419 views (prime), and reloading after stepping away for an errand before completing my own viewing, it's now up to 31 x 479 views, which is indeed an order of dozenal magnitude (if I might coin that?), so... I guess the algorithm is catching on to it? Yay! It is indeed good. I stumbled a bit on the recurrence relations, but in the end, I think I mostly understood, and I certainly enjoyed the journey. Thanks, Kate/PoC!
P.S. Oh, hey, just noticed this was a #SoME1 entry... Cool! And I see you have lots more content. I'll explore!
@@ProofofConceptMath well, as we all know, for many UA-camrs, views are always a factor... 😁
I got a comment asking for chapters, and so I've added those! Thanks!
This was great!
The summer exposition of Math has really spoiled us in the community with fantastic videos.
Interestingly a lot of the techniques used here reminded me of algorithms we used to find primes, always neat to see old things from a new perspective.
This is an amazing video. So many moments where my head hurts then suddenly it just becomes clear exactly what you're saying. Really good explanations.
it's hard for me to convey in words just how much I enjoyed this video. amazing!
I love the Farey Sequence and all of the wonderful patterns it forms. I was once absolutly sure I was on the verge of constructing an algorithm for constructing/finding twin primes and by extension proving the twine prime conjector and fame and fortune. I did not, but I always feel a jolt of excitment whenever I hear about Farey sequences. There are too many patterns not to expect to find plenty of interesting and fun mathematics.
I cannot believe you have so few subscribers. This is a criminally under-promoted channel.
This video is really amazing! The history of hand factorization fascinates me, from Fermat mistakenly believing 2^32+1 was prime (he missed the "small" factor 641) to F. N. Cole factoring 2^67-1 in "three years of Sundays". This topic isn't covered as much now that computers can do what they do, but by studying it we're doubling down on that great quote by Lehmer, even as factorization has found practical applications.
Shrink those paper patterns down to micro size and use lithography to burn a result on a chip
Thank you, great video! You struck a good balance between visual thinking and symbolic thinking (a lot of math youtubers are visual but too unrigorous/hand-wavey, or rigorous but too unmotivated/mysterious). Great work!
"The punch cards you've seen at computer museums."
Sigh.
Your comment made me smile! Actually, when I was a kid, my parents brought them home from the university as notecards, since they had leftover boxes there. Now I wish I'd kept some, but we just used the backs for grocery lists.
@@ProofofConceptMath Yes, well, I've actually PUNCHED programs on those cards and fed them into a card reader, back in my (first) college days.
@@BrightBlueJim I envy you that experience! It may not have been high-powered computation by today's standards, but it must have been exciting to be at the forefront of new technology.
Punch cards are fun in that whenever I mention doing programming to anyone older than 50 they will inevitably start talking about how they had to punch programs into cards. Then they'll ask me to help them figure out the facebook login page. I'm convinced punch cards were actually cursed talismans that sucked the computer prowess out of people.
@@Colopty Allowing for the likelihood that you're just having some fun, the two things aren't related at all. Both are user interfaces for making use of computers, but that's about all they have in common. Punch cards were an early (but not the earliest) way of entering commands and data on a line-by-line basis, and this transferred almost seamlessly into line-based terminals using either electromechanical teleprinters or electronic displays with associated keyboards. But either of these required a lot of learning on the user's part, since they had to know what commands were available to type at any given moment, and the exact syntax of those commands. The introduction of the graphical user interface based on the WIMP principle, integrating (w)indows on a screen, (i)cons, (m)enus, and a (p)ointing device, made computers usable by people with little or no knowledge about how computers actually worked. Which was a great thing, because people could do useful things with computers without having to know anything about them.
The down side of this is that application developers invented their own visual languages, many developed independently of others, so that instead of just knowing how "computers" worked, the user had to know how to operate each application.
I have been involved with computer development for over fifty years, as everything from a user to a software developer to a hardware engineer building embedded computer systems. But none of this experience helps in the slightest when I pick up a new cell phone whose user controls have been completely reinvented by the manufacturer. I JUST WANT TO ADD A NEW CONTACT!!!!!!!!!!
Since you mentioned Facebook, this is another problem: you CAN NOT learn Facebook. It is simply not possible, because Facebook can (and does) change its user interface on a daily basis. Familiar commands disappear overnight, being moved to a different menu that I can only assume made some kind of sense to somebody at Facebook. I don't use Facebook myself, but I DO use UA-cam in my evening job, which is live-streaming sports events. It's often an adventure when I go to do something I do every week, only to find that UA-cam has "improved" its user interface, and I get to go on an easter egg hunt just to do my job. Invariably, the on-line help lags behind the live changes, so it's sink or swim when it comes down to "will I be able to stream tonight?".
So yeah, I'm that guy. But I would amend your observation: it is user interfaces that change at the whims of unknown and largely clueless people, that suck the computer prowess out of people. But maybe you're right - using punched cards did condition me to expect that something that works one day will also work the next, so yeah, my failing.
This has been one of the most enjoyable videos I've found in a while . Especially loved the reminder of the simple human beauty of mathematics! The long and softly read excerpts are something so sorely missing from a lot of more individualised mathematics videos out there. If it pleases, please keep this up!
The Farey subdivision (or the resulting graph) is sometimes called the Stern-Brocot Tree.
Thanks for a well constructed presentation. In roughly 65 years of recreational math I'd never encounter Lehmer's Disks. About 15 years ago I informally explored the patterns in continued fractions for square roots near 'N squared'. Fun Stuff.
Enjoyed the video.
Out of all the SoME videos, this one is my personal favorite. Well done. At not even 13K views, however, this video is dreadfully underappreciated!
Such an awesome visualization! It kinda reminds me of hyperbolic projections...
Your intuition is totally correct! Those "bubbles" I drew over the Farey subdivision can be considered geodesics in the upper half plane model of the hyperbolic plane. Hyperbolic geometry has a big role to play in continued fractions. Here are some links: homepages.warwick.ac.uk/~masbb/HypGeomandCntdFractions-2.pdf and www.asiapacific-mathnews.com/06/0602/0010_0014.pdf
As a first time viewer and a lover of math, this was beyond what I expected clicking on around midnight. Tons of details and very well spoken. That was beautiful. Great job. Now, I have to get/make a set of Factor Stencils
08:55 The AKS primality test published in 2002 shows that checking if a number is prime or not (not factoring) is polynomial, though it may be impractical for large numbers
So essentially we can throw one additional guess at the number in polynomial time, the guess that there are no nontrivial factors of our number. Neat, but yeah not a real improvement to factoring the number
Sending encouragement! The works done by these deep thinkers from the past gives one hope for humanity…much needed. These examples only help us if people like you find, study and share them with others. Thanks so much for your hard work to share this. I look forward to more :).
This was an excellent informative video. As someone who doesn’t have a mathematics background I was able to follow along and understand it fully. Which is awesome for me every time I’ve seen these stencils before I’ve always just thought “that would some cool looking art.” Now I know what it does and how to use it that art can be even more fun.
Wow! Hard to express how much I've enjoyed this video! Well done, perfectly narrated. More of this, please!
Watched the whole video with full attention, this is truly amazing! Thank you for making these high quality explanation!!
Wow, this is a really cool video about a topic that I absolutely never would've heard about otherwise. The presentation is very engaging and easily kept me interested the whole time. I think I audibly said "woah, huh, that's so neat" at several points.
Really enjoyed this! I loved seeing the machines and physical models of prime numbers!
Farey - I am reminded of a couple of things. 1) riding in the car on long trips and seeing the patterns created by orchards; 2) learning x-ray crystallography.
Really cool explanation! Loved the 'practical' analogies and examples! I was genuinely surprised that the video ended where it did, could have easily watched another 10 minutes of explaining how the placing of the holes in the stencils was computed!
Very good video on a very interesting and uncommonly covered topic. Reminds me of slide rules. One thing that I found particularly interesting was Lehmer's mechanical computing device, which I had not heard of before. I knew of the Antikythera mechanism, Babbage, and Lovelace, but not that. The subject is also of particular interest to me because of my interest in the idea of being "ahead of one's time" (which I think is a misnomer) and when and how people end up in such a state.
Fascinating and wonderfully narrated. Thanks for the fantastic video!
What is the -pattern- on each stencil? I get the sieve concept in general, the recurrence relations and the Farey-Stern-Brocot tree, but for each stencil...the circular pattern of holes... where does that come from? Presumably you don't have to make it circular...what would it look like if the stencils were rectangular... what would the pattern look like then?
Hey, I was the 1000th like! Very nice explanation! As a Comp-Sci nerd, your descriptions of polynomial time algorithms vs exponential ones blew my mind. I am used to thinking of them from a different perspective, and It's cool to see it another way.
intense, a paper fast fourier transform, amazing video. The farey subdivision would be the energy distribution of natural frequencies to make a unit square wavelet
Can you explain this a bit more? what does the unit square wavelet correspond to- a prime factor? and natural frequencies of what, perhaps you mean the number line's size up to a given magnitude? I looked up each of the terms you used but can't put it together. thanks :)
Great video that i watch every once in a while.
I could not sleep, so made tea at 03:50. (That’s the time I made tea! - not a marker in the video - as UA-cam has interpreted.) UA-cam’s algorithm gave me this video to watch, and I liked the look of the punched stencils. I watched, with an old degree in CS with Cybernetics. The maths runs too quickly for me, and I can’t follow the reasoning at speed. So, watch it again - which I shall do. The bit I really liked was Lehmer’s words on enjoying the beauty of something just for what it is, (at 10:14 in) rather than fighting for a reason for it; or an outcome from it that’s ‘useful’. I enjoyed this video because it produced something I thought beautiful - both the theory and the circular stencils with their precise holes. It returned me to high-school maths lessons, and punching holes in colourful paper - the cerebral equivalent, for me, of ‘motherhood and apple pie’. Most enjoyable, and beautifully video’d and composed.
Presently, I don’t understand the number written at the top of each stencil. So, more tea, and another runthrough …
Matt Lee
Amazing presentation! I am impressed with the "analog computers" (stencils & Geo Board) but even more with the explanation how they represent the "formula math".
There are a number of topics in this video that would deserve their own detailed explanation. Well done, keep up the good work!
While the Geo Board is an analog computer, the stencils are not. There is no parameter that is analogous to the number being processed. Each hole position represents a specific, discrete number, whose physical position on the disc is arbitrary (which is why it makes no difference whether they are in this spiral pattern or in the pattern of holes on a computer punch card. This is digital.
In fact, each stencil is an implementation of a read-only memory with a word size of 1 bit, where the address is the physical location on the disc, and its output is 1 or 0, where 1 is represented by a hole. Stacking multiple discs creates an AND function of the outputs of the discs that are stacked. Again, purely digital.
The quotes of the beauty of math outside practical applications sum up math programs I've written. Haven't contributed much to my career with it...
Great video- Your stencils (and video) are much nicer than mine! And thanks for giving a complete and understandable explanation- I'm not a number theorist so I never really fully understood it in my bones. Thanks!
Your videos are wonderful! I love computing machines -- I find it fascinating to see arithmetic take physical form. I recommend everyone who enjoys the idea of factor stencils check out your channel!
@@ProofofConceptMath You two should do a collaboration where you use Chris's calculating machines to find the Q-values of a number and then use your stencils to test them.
Great video!
The slope N^(1/2) thing at 17:30 caught me off guard at first because it seemed unmotivated. It took me embarrassingly long to figure out it was explained later. But once I understood that I really enjoyed it!
This is fantastic. I'm very tempted to make some of these stencils myself, it seems like an incredibly fun project to really understand the math thoroughly. Either way, thank you for a delightful and informative video.
You can! There's a github link in the description, or you can program a better version from scratch. The paper cutting machine is really fun to play with.
You give me equal 3b1b and vi hart vibes, and I don't understand how you only have 708 subscribers.
Thanks! This is just my first "real" attempt at a UA-cam video. :) UA-cam only noticed it existed this week!
This is absolutely amazing, wow!
I know of Lehmer from "Lehmer LCGs" which can be used for generating pseudo-random numbers. I had no idea about this amazing topic-- I'll be adding this to my "watch again" list.
You are so freaking cool @__@
I feel like the section sieving for primes with quadratic residues would benefit greatly from some examples while the following section how many stencils are needed really didn't need that much explanation. I had to watch the quadratic residues section a few times to get into my head what x, n and the rest were (still not 100 on those btw) but when you said, each stencil gives half the number of numbers, I got it immediately.
This... was great! Really enjoyed it. That's all I wanted to say. Have a nice day!
Regarding how this algorithm doesn't circumvent the exponential nature of the problem, in addition to the stencils taking exponential time to make, they also take exponential time to use (technically).
Once you assemble your stencil stack, you have to determine which holes aren't blocked. In a practical sense, we can scan practical sized stencils pretty quickly, but as you keep scaling up the number of primes represented on the stencils, the time to check them will increase linearly in the number of prime factors you need to check (so exponential in the number of digits of the input, N). Any method which would actually spot all the open primes simultaneously would effectively be doing massive parallel computation, so the actual time might be subexponential in that case, but you'd still be doing exponential computation in a technical sense. Also, the time taken stays small only as long as your parallel computation method could also be scaled indefinitely.
In other words, if you have infinite computation resources, almost everything looks like constant time... 😁
Anyway, great video. I had to watch it a few times because it was easy to miss that the prime is used as them modulus when calculating whether to punch a hole for that prime. I kept wondering what "n" was in that case because obviously you don't know the input number ("N") at the point you are preparing the stencils. But eventually, I caught that detail and finally understood. As I said, neat video.
Ngl that farey subdivision quip showed in a series of dreams about a particular forest.
Excellent! I love the doodle style, please keep it up--subscribed!
That was a really beautiful metaphor about wandering the wilderness and believing for some reason that you must haev a net or gathering bag -- some purpose for being out there
wow this is really well done!! we love the hand-drawn visuals and animations, really makes the whole thing come to life
At 6:00 that is not an exponential algorithm. That's a linear algorithm. Linear is if it takes n steps for n items. Exponential is if it takes x^n for n items where x>1. At 6:18 that isn't a polynomial algorithm. That's a logarithmic algorithm. Polynomial is where it takes a + bn + cn^2 + dn^3 … steps. These are very different and how are you getting this wrong?
I enjoyed the video-never heard of this method before. Wouldn't 9:49 be a good point to mention Shor's quantum algorithm?
Here from 3Blue1Brown. Excited to watch!
the style of your videos reminds me of vihart, my childhood
Great video, great topic and great execution! Bravo!
If only my undergrad intro to number theory module was taught like this... 😥
Amazing video
I don't understand how the successive values of the variable Q are calculated. I can't find the same thing as in the video or the provided PDF.
Let N=8416909 (like in the video).
For Q0, I find 1108 by applying the formula Q0=N-P².
On the other hand, I have a problem from Q1 and for the other Qs. According to the recurrence formula :
Q1 = S1 × (P0-P_-1)+Q_-1 = 5 × (2901-0)+1 = 14506. But, this is supposed to be 1311.
Then, for Q2:
Q2 = S2 × (P1-P0)+Q0 = 4 × (2639-2901)+1108 = 60. Whereas it is marked that it is supposed to be 1244.
What am I missing?
See my similar comment. Shuffling the "P"s can produce the claimed Q values.
Not sure yet what that does to the recursion formulae . . .
Fred
Oh my gosh! Thank you (and one or two others today) so much for pointing this out! I'm so sorry! I made a copying error (I was copying, instead of computing live, for the sake of the video quality). I have edited my description on the video to reflect this, but full details and correction can now be found at math.colorado.edu/~kstange/stencils/stencil-users-guide.pdf. Please let me know if you find any further issues.
I didn't find the time complexity explanation confusing, I thought it was pretty standard in CS to evaluate complexity based on the size of the representation when the operations over the numbers aren't "free"
Puh...thanks universe...I was thinking: hey that should work with continuous fractions...and there it is.
Nice work! This is really impressive. :)
Computational complexity isn't the end of everything. In fact, there is already a polynomial algorithm to find a factor, but it requires a quantum computer, which currently can only carry
The one-time code generator you show at 9:30, while manufactured by RSA Security, does not use the RSA algorithm or anything else based on prime factorization.
Thank you for this clarification! I didn't realize that.
@@ProofofConceptMath You're welcome! It is based on a SHA-1 HMAC of a counter using a 128-bit to 256-bit key. In this particular case the counter is derived from a clock (usually, seconds since the Unix epoch divided by 30). See RFC 4226 (counter-based) and RFC 6238 (time-based) for details.
What the hell did I just see? Thank god for the computers.
Nice! The equations went by a bit too fast for me. I'm gonna read the accompanying pdf and give it another watch to consolidate.
Question: can we use Hamiltonian monte Carlo to figure out the coordinates of these punches and then 3d print such stencils?
Thanks so much for such a great video!
That was very interesting!
very cool
Thank you for this wonderful video!
At around a minute, you're doing some calculations involving P, Q, and S.
They look fine, except every line in which you compute Q is wrong:
5(2901 - 0) + 1 = 14506, not 1311
4(2639 - 2901) + 1108 = 60, not 1244
4(2605 - 2639) + 1311 = 1175, not 2247
However, rearranging the "P" values inside the parentheses, you can get the Q values you claim:
5(2901 - 2639) + 1 = 1311
4(2639 - 2605) + 1108 = 1244
4(2605 - 2371) + 1311 = 2247
etc.
Did you mean these latter, rather than those former?
Overall, lots of good content here - WELL DONE!!
Fred
You are right! Thank you (and one or two others today) so much for pointing this out! I'm so sorry! I made a copying error (I was copying, instead of computing live, for the sake of the video quality). I have edited my description on the video to reflect this, but full details and correction can now be found at math.colorado.edu/~kstange/stencils/stencil-users-guide.pdf. Please let me know if you find any further issues.
@@ProofofConceptMath Splendid!
This method intrigues me, having had a bit more than passing interest in a few areas of number theory for years.
So I wanted to see this corrected, for benefit of all other viewers of your video.
And you've come through with flying colors, taking my comment as constructive, not hostile, criticism. Another adherent of the principle that the math is perfect; while sometimes we mathematicians are less so.
Fred
This is great stuff
Is anyone able to help me understand the statement at 13:20?
If we take the case of N = 10, which gives quadratic residues mod N of {0,1,4,5,6,9}.
The prime divisors of 10 are 2 and 5.
The quadratic residues mod 5 are {0,1,4} and those of 2 are {0,1}.
x = 5,6 and 9 are all cases where the Fundamental Principle is failing to hold. What am I missing? Is the logic meant to be the other way around?
5,6,9 are 0,1,4 mod 5
and 4,5,6,9 are 0,1,0,1 mod 2
so they are quadratic residues mod 5 and 2
Love your work!
This is amazing!
Great stuff!
I LOL on the "rather abitrary decimal system famously dictated by our biological makeup". Reminded me of Tom Lehrer's song New Math in which he said: "Base eight is just like base ten really - If you're missing two fingers"
I'm getting some viheart vibes, it doesn't rly match but still love it!
You may want to s/14/49/ the sqr(7) example shown at 17:10 for the sake of clarity.
I think you mean, show/explain that I'm reducing mod n? Yes, that's a helpful suggestion, thank you!
Formula for: Qn should read Q(n) = S(n) . (P(n-1) - P(n)) + Q(n-2). Q(1) = 5 . (2901 - 2639) + 1 = 1311,
where P(-1)=0, Q(-1) = 1.
You are right! Thank you (and a few others) so much for pointing this out! I'm so sorry! I made a copying error (I was copying, instead of computing live, for the sake of the video quality). I have edited my description on the video to reflect this, but full details and correction can now be found at math.colorado.edu/~kstange/stencils/stencil-users-guide.pdf. Please let me know if you find any further issues.
What puzzles me: Why do the stencils show 3 as prime factor of 8416909? It's not divisible by 3. I mean the number down right of the equal sign, when 631 x 13339 is displayed. Is it just "not yet" covered or not completely visible?
Amazing video!
This seems a little bit similar to bloom filters. Thinking. In a (simpler but somewhat broken/inefficient version of a) bloom filter, for each input, for each bit, about half the time the hash will have that bit, and here, for each residue, and each prime, about half the time the prime will have that residue (provided that the residue is smaller than the prime).
[correction: in an actual bloom filter, I guess instead of each bit having a 50/50 chance, instead there is supposed to be a uniform distribution of which k of the n bits will be set to 1, not just a single hash. Whatever. That makes it more complicated and makes the analogy worse. I guess I’m just describing a worse version of bloom filters instead of the good version.]
With a bloom filter, [the following might have gotten some polarities flipped because it is by memory, but the general idea is basically the same] you take the OR of all the hashes of the items in the list to be recognized, and then if an item is hashed, if it is in the list, all the bits in its hash will be there, so it can be seen to be “maybe in the list”. And, if the hash of something has a bit set that the filter doesn’t have, it definitely isn’t in the list.
With these filters, I suppose the analogy would be that the number to be factored corresponds to, the list of items to potentially recognize? Or, like, the prime factorization would correspond to that list.
Where, a prime is only potentially a factor of the number if, all of residues of the number are residues of the prime, and so, if the prime lacks a residue (if the item’s hash has a bit set which is not set in the filter) then the prime is not a factor (the element is not in the list).
So, the residues correspond to the different bits I guess?
(And the analogy has some true/false flipped around I guess)
So, uh, I guess that analogy kinda works?
Though, with a bloom filter you don’t get a list of items that might be in the list..
Hmm.
Thinking I might be trying to go about this analogy in the wrong way
Wow, what an interesting topic! I'd never heard of Bloom filters. I'll have to dig into it a bit more. Thank you!
so how many stencils to break cryptography?
So couldn't Lehmer stencils be modeled virtually in a large enough computer algorithm to factor any size number. Creation of the algorithm would be exponential, but using it would be polynomial once created.
Well, modern RSA uses 2048 bit keys, so using the estimates in the video, factoring with this method would need a deck of 2^1024 stencils, each 2^1024 positions in size. Storing these, even electronic versions, would be challenging. Modern estimates put the number of atoms in the universe at about 2^265.
Love this!
1:08 How did you make a square root so fast? 😮
So how big would you need these circles to be in order to crack RSA? You know, hypothetically?
I LOVE YOUR LETTERS
Amazing!!
I'm working through your example to get a better understanding of how the recurrence equations relate to the rational approximations of the square roots, and I'm confused by the calculations you've written down at the beginning. For your second Q value, you've written Q = 5 * (2901 - 0) + 1 = 1311, but 5 * 2901 + 1 is 14506. Similarly, for the third Q value you have Q = 4 * (2639 - 2901) + 1108 = 1244, but that expression actually equals 60. However, 1311 = 5 * (2901 - 2639) + 1, and 1244 = 4 * (2639 - 2605) + 1108 - i.e. the values you'd get if you used P_n instead of P_(n-2) in the formulas you show. What are these values actually supposed to be?
Oh my gosh! Thank you so much for pointing this out! I'm so sorry! I made a copying error (I was copying, instead of computing live, for the sake of the video quality). I have edited my description on the video to reflect this, but full details and correction can be found at math.colorado.edu/~kstange/stencils/stencil-users-guide.pdf. Please let me know if you find any further issues.
I have made that exact mistake before when trying to write up a solution. Thanks for the info!
Good old Farey Addition...
Subscribed
Nifty !
Is this girl the new Vihart?
"bridges and universes"
There was a mistake in 8:14, you say less or equal to but the symbol is less only
You are right, I wasn't careful enough there. If N is a square, then it's possible a=b=sqrt(N).
ooooh, I thought the title said "refactor" as in code refactor
Nit: it's more than twice as hard to do multiplication or division of twice as many digits. There's no known linear multiplication algorithm, and I'm going to take a stab in the dark and say a student wasn't doing FFT on paper by hand, so it's likely at least 4x as hard to use twice as many digits with a reasonable algorithm that a human would use.
Hehe, yes, it was long division by hand, and I suppose the paper gets twice as long as well as twice as wide, at least... in any case, you are right! Thanks for the nit.
This is super cool, but at the same time a bit depressing with how useless it has become, because now anyone who knows any programming language can easily factor any number up to 100 million knowing only the definition of what the word "factor" means, and anyone who knows that you can have at most one prime factor bigger than sqrt(n) can instantly factor numbers in the quintillions. It's wild to think that this used to be something that was hard to do.
Briefly touched too many related topics, to show how this thing work briefly. It's sad how much time it would need to explain everything related at some good level. :(
Prime numbers are weird and beautiful, aren't they? So, I have a question: is it a matter of computational power for the human race to be able to factor huge (by that I mean gargantuan type gigantic-ish ones) numbers? No matter how many algorithms we come up with and no matter how many contraptions we build and process in order to understand the deepest insights on the mysteries of how numbers work, will it always be futile to alleviate the mystery part of the way the numbers work?
Will it always be like wandering blindly in the woods?
Can the human race ever achieve a polynomial complexity algorithm?
PS. Love your video totally. Well done, it's awesome! And so is mathematics, is it not?
> So, I have a question: is it a matter of computational power for the human race to be able to factor huge (by that I mean gargantuan type gigantic-ish ones) numbers?
If I'm understanding you correctly, I think the answer is yes, sort of. Broadly there are three ways we might factor a number:
* Trying lots of options one by one, either after we get the number (basic trial division), or going through them in advance (Lehmer stencils). This is the best we can currently do, but it needs huge amounts of computing power. That's hard to get for big numbers and basically impossible for gargantuan ones.
* Trying lots of options _at once_ \*, with physics hacks (e.g. Shor's algorithm for quantum computers). This is technically and mathematically clever, but it still boils down to "try lots of things". No deep truths about the prime numbers here. It's also really limited by _quantum_ computing power - currently our most powerful quantum computers can only factor 2-digit numbers.
* Using a deep understanding of number theory to factor them more quickly (maybe involving proofs of the Riemann hypothesis and/or P=NP). Currently we have no idea how to do this, or if it's even possible, despite the brainpower (and computer assistance) of our smartest mathematicians.
\* From reading the Wikipedia article it sounds like Shor's option tries lots of options at once, but I don't think I've got the whole picture; the experts don't seem to describe quantum computers that way.
Why are you calling a logarithmic algorithm polynomial and a linear algorithm exponential? Did I miss something
Ah wait a minute you're saying it's polynomial in the digits of N, not in N. That was kinda confusing for a second but I got it now, nevermind that's my bad.
Yup, you got it. When I want to factor a number N, the input is actually the number written out in decimal (or binary or whatnot) notation. So the size of the input is the number of digits, not the number itself. For example, 100 has size '3', because it has 3 digits. So an algorithm that takes log(N)^2 time to factor N is taking X^2 time in the input size X. It's "polynomial" for this reason. It's the same definitions as in a CS class, but the trick is what you consider the "size" of the input. When factoring N, the size of the input is log(N) -- the number of digits. (This is admittedly a point I should perhaps have addressed a little differently in the video.)
@@ProofofConceptMath I had the same moment of confusion and realization as pendragon. By "convention" (akak one of the rules people assume but never mention so is it even real) I'm used to "N" being the count of a thing. Maybe it would have been clearer to use "D" or O(# of digits) or something.
I really enjoyed this video. Weirdly, I'd heard of the mediant operation, but never the Farey sequence. What a gem!