If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains ***.kastatic.org** and ***.kasandbox.org** are unblocked.

Main content

Current time:0:00Total duration:7:04

congratulations we've reached a branching point in our lesson now a few different ideas have been introduced so it's important to orient ourselves here before moving forward in various directions now what motivated this lesson well we learned about RSA encryption and RSA depended on two things one that prime factorization is difficult so if I multiply two big Prime's together p1 and p2 and I give you n I can trust or feel secure in knowing that you'll take a long time to find those Prime's and maybe more than your lifetime also to RSA requires that those large Prime's I generated was easy meaning I could just quickly generate a large prime so let's return to the first problem difficulty of prime factorization well what is it about prime factorization or just prime numbers themselves which make problems hard and to find out we began with a core problem given X is X prime or composite which is a primality test now we ended up building some solutions to this problem and in doing so we realize that this problem was computationally expensive that is there was no instant solution to this problem as our input number grew the amount of time or the amount of steps involved for our algorithm to find the solution also grew and how much it grew we actually understand better now because we can predict this search space using the prime number theorem so the real issue can be thought of as a graph where on the vertical axis we have the number of steps our algorithm takes so you can just think of it as time and on the x axis is the input size and as input size increased so did time and the problem we had is that the shape of this curve is unacceptable because in our case once n hit even 20 digits we can no longer solve the problem in the worst case and if we threw an input hundreds of digits long at our algorithm we can all agree it would not work in our case it would crash so it's practically impossible to check if large input is prime using our current strategies now let's return to the first point factorization realize based on our current understanding in this lesson factorization has to be harder than a primality test that is there are more steps involved in finding the prime factorization of some number versus just telling me if a number is prime since remember factorization requires us to find all the prime factors for some input end whereas a prime ala t-test only requires that we find one divisor and a nice reminder of this is that some users have actually turned these prime allottee tests into prime factorization algorithms simply by repeating after it finds its first divisor so the primary test is just kind of a subroutine inside the main factorization algorithm so if we return to this graph a factorization algorithm would be something like this as input grows our factorization algorithm would be above this prime allottee test line and realize that in any situation we always have a computational limit that is the number of primitive steps we can calculate which is based on our computer power computing power in any given situation and the amount of time we had and you could think of this as a horizontal line or a threshold on this graph anything above this line is out of reach not feasible to solve and in this lesson we were limited by the Rovers onboard computer which was fairly slow which is why we couldn't run prime ality tests ion numbers with even 20 digits however even if we had say a thousand computers running for a year this would simply just push this horizontal line up to some other threshold and this would allow us to run tests on larger numbers but as you can see we would always hit some limit where the input is large enough that we can no longer solve the problems again now this leads to many interesting question paths however all identify the two I'm going to explore next first of all so far I have not been very precise about these growth curves though it would be helpful if imagine for any algorithm you give me no matter what it's trying to solve and no matter what machine it's even running on we could draw some corresponding growth curve on this graph simply by looking at the description of the algorithm if we could do this we could identify categories of certain growth shapes which tell us how difficult a problem will be to solve and in this way we could understand an algorithm before we even run it that's very important to think about and I could you could hand me your algorithm written on a piece of paper and I could look at it now say I know this algorithm is not solvable with the input size needed and this leads us to a lesson on time complexity an incredibly important conceptual tool we will need and if you've ever heard oh this runs in polynomial time or exponential time these are terms which come out of time complexity next many of you have been wondering well how are we generating these random Prime's in practice the second point I made about RSA well let's just walk through it quickly to generate a large random prime number hundreds of digits long we need to follow these instructions generate a random number test if it's prime if it's prime we're done if not try again until we hit a prime now in this three-step procedure what's most important is the second step test if it's prime if we can't do that step this won't work so how is this working today well it's based on a subtle alteration to our problem definition and more importantly the use of randomness and this leads us to another lesson on random algorithms and now finally if there are any other lingering question paths you have please post them below and we can plan lessons for example there are some deeper mathematics we have yet to explore in order to speed up our existing trial division primality tests and what else are you thinking of please share below