In this problem, we will carry out some steps of the quantum factoring algorithm for N=91.
(a) What is the period k of the periodic superposition set up by the quantum factoring algorithm if it chooses x=8? I.e. what is the period of f(j)=8j(mod91)
(b) Using your answer to (a), find a nontrivial square root of 1(mod91). Write your answer as an integer between 0 and 91.
(c) Then, the algorithm proceeds by computing gcd(91,y) for some y. What is y? If there are multiple correct answers, provide any one of them.
6.(a)answer: 4
(a) To find the period k of the function f(j) = 8j (mod 91) when x = 8, we can use the Quantum Period Finding Algorithm. However, since this problem asks for a specific value of x = 8, we can find the period classically.
To determine the period classically, we need to find the smallest positive integer k such that 8^k ≡ 1 (mod 91). We can start by calculating the powers of 8:
8^1 ≡ 8 (mod 91)
8^2 ≡ 64 (mod 91)
8^3 ≡ 1 (mod 91)
Therefore, the period k of the function f(j) = 8j (mod 91) when x = 8 is 3.
(b) To find a nontrivial square root of 1 (mod 91) using the period k, we can calculate 8^(k/2) (mod 91), where k = 3 in this case.
8^(k/2) = 8^(3/2) = 8^(1.5)
Since the exponent is not an integer, we need to use a different approach. We know that 8^3 ≡ 1 (mod 91), so we can rewrite 8^(1.5) as (8^3)^(1/2).
Taking the square root:
(8^3)^(1/2) = (1)^(1/2) = 1
Therefore, a nontrivial square root of 1 (mod 91) is 1.
(c) The algorithm proceeds by computing gcd(91, y) for some y. To find y, we need to factorize N = 91. Since 91 is a composite number, its factors are prime numbers.
The prime factorization of 91 is: 7 * 13 = 91.
Therefore, any factor of 91 can be used as y. So, one possible value for y is 7 or 13.
To determine the greatest common divisor (gcd) of 91 and y, we can compute gcd(91, 7) or gcd(91, 13), both would yield the same result of 7 as the greatest common divisor.