(Solved): (d) Consider the following piece of pseudocode that claims to find the smallest square root of an ...

(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