As I told you before Shor's algorithm allows to effectively search for a period of some periodic function. Now, how does this helps us with factoring? Let's see. Again, we have a big composite number N which consists of two different primes. We randomly choose some number a smaller than n and co-prime to it. If we choose randomly number a and it appears to be not co-prime to N. Then we don't need all the following since we can just compute the greatest common divisor of a and N. If it is not one, it will be one of these numbers p or q. So, a and N are relatively prime. We defined function fa like this, like it maps integer number x natural number x to a raised to the power of x modulo N. All such as, all such numbers less than N and co-prime to it from here, in a group, under modulo N. So, there exists such smallest number r. So, that if we raise a in the power r, we get one modulo N and r is the smallest such integer. This r has to be also the period of this function fa. Since if you compute a in the power of x plus r, modulo N is equals to a power x multiplied by a power r which is one. We get just a power of x modulo N. So, this r is the period of this function. You remember that Shor's algorithm allows us to search for periods. So, imagine that we employed Shor's algorithm. For this function fa defined by this random number a, we found this value r, it's periods. Now, let's assume that we are lucky today and these are happens to be even. Now, what does it gives us? Well, let's rewrite this identity like this, a the power r minus one equals to zero modulo N. Since r is even, what we have here is the difference of squares. Everybody knows what to do with difference of squares when you see one, you decompose it. So, we decomposed like this, ar divided by two plus one and the same minus one. This equals to zero modulo N. So, this means that N divides this product. Now, we can be sure that N does not divide this factor. Because if it is this factor was divisible by N, that would mean that a in the power r divided by two equals to one modulo N. This contradicts to our assumption that, r is the smallest integer for which this have identity holds. So, this is obviously not true. Let's assume that we are even more lucky today and this factor and also doesn't divide these factors. So, we write it like this, a in the power of r divided by two not equal minus one modulo N. So, these are our assumptions which depends on our luck. In this case, we have two factors and divides their product but doesn't divide any of these factors separately. This means that the factors of N itself, p and q are situated in different terms, factors here. We can search for it by Euclidean algorithm. So, this is all wonderful and exciting but we must not forget that we employed some luck among with this reason. Now, we have to estimate how much luck do we really need. So, how much luck do we need for those assumptions to be true? So, put your [inaudible] assumptions. The first was that r is even. The second was this. Well, let's introduce two new numbers, a one is, a in the field is that modulo p and a two is, a in the field is that modulo q. We are going to introduce all the orders for these numbers in those fields r one of [inaudible]. The smallest number such as a one in the power r one equals to one modulo p and r two is the smallest such a natural number. That a two in the power r two equals to one modulo q. Now, we have these that a in the power of r, a in the r equals to one modulo pq and again, conclude that a in the power r goes to one modulo p also. This r and this a in this field is a one. So, a one in the power of r equals to one modulo p. From this and this, we can conclude that r is multiple of r one. The same reasoning for the field Zq gives us that r is a multiple of r two. Even more, let's consider any number s which is also multiple of this both numbers, r one and r two. Then a modulo a in the power of s equals to one modulo p and also equals to one modulo q. At the same time, we should going to write like a in the power s equals to p multiplied by some integer k one plus one. At the same time a in the power s goes to q multiplied by some integer k2 plus 1, and we are going to subtract this one from other to get this pk1 equals to qk2. Now, q does not divide p. That means that q has must to divide k1 and then these equation, we can rewrite like a power of s equals to pq some integer reaches k1 divided by q. So, note this is integer plus one, which means that a to the power s equals to one modulo pq which is N. So, for any number which divides both r one which is a multiple of both r1 and r2, it has also to be a multiple of r and r is itself a multiple of this r1 and r2 which means that r is the least common multiple of these numbers. Now let's decompose these two numbers r1 and r2 like this. What I want, I want to extract the powers of two and N. So, we have for r1, we have c1 as power for two in it and for r2 we have c2. Then remember that r is the least common multiple of these two numbers. So, this two in the power c one multiplied by some odd integer and two in the power c2 multiplied by another odd integer. Now, let's assume that c1 and c2 are not equal. For example, c1 is bigger than c2. Then this least common multiple, r, would have, of course, it is a multiple of r2 so it will have r2 in it and its factor representation. Also, it will have at least 1, 2 because c1 is bigger than c2 and maybe some integer. Okay, what we see here is that r in this case when c1 is bigger than c2 or whatever. Maybe c2 is bigger than c1. In this case, r is even and our first condition is met, and more if you a in the power r divided by 2. This is a in the power r 2 multiplied by some integer and it is one modulo q as we remember which does not equal to minus one modulo q if q is bigger than two. This means that it also does not equal minus one modulo pq and we see that the second condition is also met only if we have inequality. All these powers of two in numbers r1 and r2. Now, how likely is that to have different powers of two in this representation of r1 and r2. The short answer is, it is rather likely. It appears that this powers here in this numbers r1 and r2. Then to be greater than in ordinary random numbers. Let's see it for ourselves. So, let's take a closer look at the fields Zp and Z modulo q. Let's decompose p like this. So, we have to extract the power of two and it's closest neighbor p minus 1 and s here is some odd number and k is greater or equal to one and the same for Zq. If q equal to two and some power l multiplied by some other odd integer plus one and l also greater or equal to one. Okay. Since Zp and Zq are fields, they have primitive elements in them. Here, we will call it b, and this element b generates the whole field. So, the powers of b form all the elements of the field and we have only b elements of this field. So, the order of b would be b minus one which is two in power of k multiplied by s and this equals to one modulo p. Okay. Now, a1 is itself the element of this field Zp. So, it is b in some power. Let's call it m. We remember that a1 in power r1 is one and it is also b in power mr1 and this one modulo p. So, we have these and these and this means for us that r1 is multiple of 2ks and since a is a random number, for us m is also a random number and the same reasoning here. Instead of m we'll have some n here multiplied by r2 is a multiple of two in the power ls1. Okay. The worst case for us here if we have not multiple here what this if mr1 equals to 2l power k multiplied by s and here nr2 equal to two power ls1. Because you already see that the number of twos in this r1 and r2 depend on number of twos in these random numbers. Again, the worst case is if k equals to l and equals to one. Because in this case, we would have the least number of variations for number of 2s in r2 and r1. For example, if m and n appear to be odd, then r1 and r2 would have exactly one two in them and if both these m and n appear to be even, then r2 and r1 will be odd. So, in this first case, the probability that we are not lucky is the probability of two randomly chosen numbers have the same auditing and the probability of that is one-half, and that means that with at least these probability one-half, we are lucky and one-half doesn't sound too bad. So, this let it be the probability of our luck, and we can now proceed further to the quantum Fourier transform.