In this problem, we will carry out some steps of the quantum factoring algorithm for N = 15
(a) What is the period k of the periodic superposition set up by the quantum factoring algorithm if it chooses x = 2 ?
(b) Assume that we found this k using period finding algorithm. Use k to find a non-trivial square root of 1(mod 15) . Write your answer as an integer between 0 and 15.
(c) Then, the algorithm proceeds by computing gcd (x,y) for some integers x and y . List these two numbers separated by a comma.
If there are more than one correct solution, provide any one of them.
a)4;b)4;c)(3,15) or (5,15)
thank you
Answer to Q 2,3,5?
q10
To solve this problem, let's go through the steps of the quantum factoring algorithm for N = 15.
(a) To find the period k, we choose x = 2 as mentioned in the problem. The period finding algorithm in the quantum factoring algorithm can be done by using a quantum computer. However, since we are not given access to a quantum computer, we'll use a classical approach instead.
To find the period k, we can use a classical algorithm called the "Pollard's rho algorithm" or "Pollard's kangaroo algorithm". This algorithm uses a random function and a collision detection method to find the period. Applying this algorithm, we find that the period k is 4.
(b) Now that we have the period k, let's find a non-trivial square root of 1 (mod 15). We know that the non-trivial square roots of 1 (mod 15) are the solutions to x^2 = 1 (mod 15), where x is between 0 and 15.
Using the period k = 4, we can find a non-trivial square root by calculating 2^(k/2) (mod 15). In this case, it would be 2^(4/2) (mod 15), which simplifies to 2^2 (mod 15), resulting in 4. Therefore, a non-trivial square root of 1 (mod 15) is 4.
(c) Finally, the algorithm proceeds by computing gcd(x, y) for some integers x and y. In this case, let's take x = 2 and y = 15.
Computing the gcd(2, 15) using the Euclidean algorithm, we have:
gcd(2, 15) = gcd(15, 2) = gcd(2, 1)
The greatest common divisor of 2 and 1 is 1.
So, the two numbers for gcd(x, y) are 2 and 15.
In summary:
(a) The period k of the periodic superposition set up by the quantum factoring algorithm when x = 2 is 4.
(b) A non-trivial square root of 1 (mod 15) is 4.
(c) The two numbers for gcd(x, y) when x = 2 and y = 15 are 2 and 15.