Hello everyone. Welcome to the fourth week of our course dedicated to potentially the most significant result in the field of quantum computer. I'm talking about Peter Shor's algorithm for function period finding. Why this result is so important? I hope because it allows us to factor big composite numbers, and as you probably know for the classical computations, this program is believed to be hard. Suppose that we have two big primes, p and q, p not equals to q, and we calculated their product. It should go, and big. Now, all of these tasks finding big primes and multiplication are feasible for classical computations. Suppose that these primes are 10,000 digits each approximately. So, this n will be like 20,000 digits, and now you have lost this p and q, but you still haven't. So, the task is to find p and q. Since n is a finite number, and n number has only one set of primes of factors, they can do this by brute force search from two square root of n since at least one of the factors, actually one of the factors has to be less than this square root, and we can just take any number from this interval from two to square root of n, tried to divide n by this number, and see if we have the remainder, and if you don't succeed, we find both factors. Now, the problem is that for this size of p and q like 10,000 digits, and we can do the search quickly enough. Honestly, we can do it, we can perform it in a universal lifetime assuming the reasonable growth of our computing power. Okay. Brute force doesn't work here, maybe something else does. Well, maybe, but to our current knowledge there's no classical algorithm that can perform significantly better than these brute-force search. Behold, in this number rather small, only 20,000 digits we can store, we can file like 20 kilobytes assuming one byte per digit, in this number there is information about p and q, but we can never retrieve it. Isn't that amazing, I mean if you find two big bribes, and you calculate their product, and you publish this product, it will still be the only person in the universe who knows the original factors, and these factors can stay your secret as long as you want it. Now, this secret keeping business reminds me of encryption, and yes there are encryption algorithms based on these asymmetry of multiplication and factoring, and these algorithms are themselves asymmetric, which means they use different keys for encrypting and decrypting data. We shall also to do many things like allowing anyone to send you encrypted messages, only you would be able to read, or digitally signing some data et cetera. The most famous such algorithm let us say, makes possible hand shake, the initial stage of the https, secure connections on the Internet. Now, this algorithm there we say was invented in 1973 by English scientists Clifford Cocks, and this result was market as classified by the British government, which made it possible in 1977, three American computer scientists, Ron Rivest, Adi Shamir, and Adlemen to reinvent the algorithm. So, the algorithm was named by the first letters of their names, the RSA, and that is probably the most well known and widely used algorithm nowadays. It is believed to be secure as long as the factoring problem is believed to be hard. Now, you can understand the importance of Shor's result, because with Shor's algorithm, the factoring problem is not hard at all, and all the data which is encrypted by RSA right now, and all the protocols which use it are insecure for big enough quantum computer. Well, here is the plan of this week's lectures. First the introduction, you are finishing it right now, then we are going to recall the RSA algorithm with idea and some examples, then I'm going to explain how factoring and period finding are connected. So, how can we solve the factoring task, if you can solve the period finding task, then I'm going to introduce the new quantum operator, the Quantum Free Transform, QFT, and only then we can proceed to the algorithm itself, and this will occupy us for two lectures. So, let's start.