4. Factoring 21. (a) Suppose that, when running Shor's algorithm to factor the number 21, you...

Transcribed Image Text:

4. Factoring 21. (a) Suppose that, when running Shor's algorithm to factor the number 21, you choose the value a = 2. What is the order r of a mod 21? (b) Give an expression for the probabilities of the possible measurement outcomes when per- forming phase estimation with n bits of precision in Shor's algorithm. (c) In the execution of Shor's algorithm considered in part (a), suppose you perform phase estimation with n = - 7 bits of precision. Plot the probabilities of the possible measurement outcomes obtained by the algorithm. You are encouraged to use software to produce your plot. (d) Compute ged(21, ar/² – 1) and gcd(21, ar/² + 1). How do they relate to the prime factors of 21? (e) How would your above answers change if instead of taking a = 2, you had taken a = = 5? 4. Factoring 21. (a) Suppose that, when running Shor's algorithm to factor the number 21, you choose the value a = 2. What is the order r of a mod 21? (b) Give an expression for the probabilities of the possible measurement outcomes when per- forming phase estimation with n bits of precision in Shor's algorithm. (c) In the execution of Shor's algorithm considered in part (a), suppose you perform phase estimation with n = - 7 bits of precision. Plot the probabilities of the possible measurement outcomes obtained by the algorithm. You are encouraged to use software to produce your plot. (d) Compute ged(21, ar/² – 1) and gcd(21, ar/² + 1). How do they relate to the prime factors of 21? (e) How would your above answers change if instead of taking a = 2, you had taken a = = 5?

Answer rating: 100% (QA)

This question relates to Shors algorithm and its application to prime factoring Lets address each part separately a Find the order r of 2 mod 21 The o... View the full answer