In this morning, I had a wonderful experience discussing the new paper by Oded Regev with my class mate Jai and Ayan in PAB-4-708. Thanks for comming guys!
In this blog, I will briefly introduce what we have discussed and what problems we have met.
Before we learn the shor's algorithm, we have to understand the RSA public-key cryptosystem. The main reason for people to come up with RSA in 1977, is that private key exchange protocals could consume too much time and storage to generate and store the private keys for each other on the internet! Let's say, Alice and Bob want to send a piece of secret message "m" between each other. In private key-exchange system, they will generate a secrete key "sk" in advance and both keep it in their own computer. When they are trying to communicate, the protocal goes as
Encryption: m'=Enc(m,sk)
Decryption: m=Dec(m',sk)
This protocal is not feasible on the internet because otherwise we have to generate different secret key for other 7 billion people each! To solve this problem, we just need to change the protocal a little bit as:
Encryption: m'=Enc(m,pk)
Decryption: m=Dec(m',sk)
Where we introduce a new key called public key "pk" to the protocal. On the internet, everybody just need to generate a public key and private key pair (pk,sk) once. After that, he can just broadcast pk to the whole internet, and whoever want to send him a secret message can use that key to do the encryption. Except one that hold the secret key, nobody can understand what the messeage really mean!
The real implementation of such public cryptosystem that have been used widely is called "RSA", first introduced by three computer scientist in MIT. (Ron Rivest, Adi Shamir and Leonard Adleman, they won the Turing award together in 2002 for this contributation.)
The math behind the RSA is quite clear and simple. We want to fix a large integer n, with bit length N, and find a pair of inverse modulus number (e,d) with regard to this n. Which means:
For all message m, (m^e)^d = m (mod n)
Now, we can let pk=(e,n), and sk=d, and the encryption, decryption process becomes
Encryption: m'= m^e mod n
Decryption: m=m'^d mod n
More specifically, RSA generate (n,e,d) by the following process:
1. Generate two random large prime p,q, set n=pq
2. Calculate the Euler function of n, phi(n)=(p-1)(q-1)
3. Choose e such that e is co-prime with phi(n)
4. Calculate d from e,phi(n)
The hardness of decrypting RSA, relies on the fact that factoring is hard. Becasue once you can factor n=pq, you can easily get phi(n) and get the secrete key d.
When I introduce the RSA cryptosystem, Jai raised a very important question:
Jai:
"How do we measure the comlexity of doing exponentiation in the protocal? Should we treat multiplication, addition of two bit string the same way when we analyze the algorithm's time complexity? "
Shor's algorithm:
The most important idea of shor's algorithm is based on a simple observation: On can do factoring of n when we find a non-trivial oder a of n. By order of n, we mean:
a*a= 1 (mod n)
When we find such a, which is not a trivial case such as a=1 or a=-1, we can us gcd algorithm to do the factoring because
(a-1)(a+1)=0 mod n, n=pq, p,q
p,q have to be facors of either (a-1) or (a+1). With high probability:
gcd(a-1,n), gcd(a+1,n) could be a factor of n!
Such process, is called order finding! And basically, shor's circuit creates a superposition of all possible order a and a bunch of control-a gates first and then use QFFT to get the feasible period a!
Oded regev's improved version of shor's algorithm:
The result of Oded's improvement, is astonishing, at first sight. Becasue he claims in his paper that the circuit size has been reduced to O(n^{1.5}), which is a 0.5 improvement in factor to the previous best result! However, we should be critical about the claim, at this stage, as also mentioned by the author himself in the paper, because in real application, this improvement might not be pratical, when we are considering the real gate implementation. (In which case Ua should not be treated as an oracal)
The algorithm by Oded is completed in the following steps:
1. Create a quantum superposition over the high dimension lattice vector with bounded radius
2. Compute the order and store that in another register. And create the same type of high-dimensional periodic state in analogy to what was done in shor's algorithm
3.Apply QFFT and measure, and we get a vector from the dual lattice, not the original lattice.
4.Repeat process in 3, generate many vectors from the dual lattice, and then use a classical algorithm to get a non-trivial vector in the original lattice.
5. Calculate the order by the lattice vector and do factoring just the same way as in Shor's algorithm.
I make some comments and raised some questions.
John:
1. How to implement the algorithm on a quantum circuit simulator? Could there be any difficulty that we don't know yet?
2. Since there are two trade-off in optimization shor's algorithm, circuit depth and qubit number, how do we set the best criterion to compare different optimization methods in real physical implementation? For example, although Oded successfully reduced the circuit depth, it takes more loops the run the circuit.
In short, Regev's algorithm is just an extention of oder finding from integer space to high-dimensional space. As long as we could find one none trivial lattice vector in the defined lattice space, we can get the order of the integer by multiplying them together.
The question is: How to prove the existence of such vector that is non-trivial? The author still don't know how to prove it! He just use this as an assumption.
We understand the high lever of the algorithm together. However, it still takes time to undertand the proof.
Comments