(Solved): This question is about searching and solving a problem in modular arithmetic. (a) Consider the fol ...

This question is about searching and solving a problem in modular arithmetic. (a) Consider the following vector of integers: By hand, directly run through the Binary Search algorithm on this vector searching for the value 5 . Show your working and how you choose elements to inspect. [7] (b) It can be argued that the Binary Search algorithm is optimal. Very briefly explain what this means. You do not have to provide an argument, just explain what the statement means. [3] (c) A modular square root of a non-negative integer \( y \) modulo \( N \) is a non-negative integer \( x \) such that \( x^{2} \equiv y(\bmod N) \), i.e. \( x^{2} \) and \( y \) are congruent modulo \( N \). For instance, if \( y \) is 2 and \( N \) is 7 , then \( x \) could be 3 since \( 9 \bmod 7 \) is 2 , or \( x \) could be 4 since \( 16 \bmod 7 \) is also 2 . That is, there can be multiple square roots. (There is a short revision on modular arithmetic at the end of this question.) The modular square roots \( x \) and \( y \) are also assumed to be integers less than \( N \). Note that \( N \) is always assumed to be greater than 0 . Consider the following piece of pseudocode that finds the smallest square root of an integer \( y \) modulo \( N \) : i. Briefly explain why the worst-case time complexity of \( \operatorname{RECMOD}(a, N) \) is \( O(a / N) \) for inputs a and \( N \). [5] ii. What is the worst-case time complexity of \( \operatorname{MODSQUAREROOT}(y, N) \) in \( \operatorname{Big} O \) notation and in terms of the inputs \( N \) and/or \( y \) ? [2] iii. Briefly explain your solution to part 2 of (c), i.e. the worst-case time complexity of MODSQUAREROOT \( (y, N) \). [5] (d) Consider the following piece of pseudocode that claims to find the smallest square root of an integer \( y \) modulo \( N \) : If this algorithm worked, in general, it would give an algorithm that could find the smallest modular square root of an integer \( y \) in time that is \( O(\log N) \) for integer input \( N \). Explain why this algorithm cannot work. You can use the internet to perform research for your answer, as long as you appropriately reference the materials used. [8] Short Modular Arithmetic Revision A non-negative integer is an integer greater than or equal to 0 . Every non-negative integer a can be written as \( a=p N+q \) where \( p, q \) and \( N \) are all non-negative integers and \( N>0, q