Implement a function that finds the first nontrivial square root modulo . We are working classically, so feel free to do it using a sequential search over all possible elements. This search is linear in and may seem efficient, but the numbers used in algorithms such as RSA are extremely large, on the order of thousands of digits! For this reason, through quantum computation we will devise new strategies to find the nontrivial square roots that are of so much interest for prime factorization.

Hint.

The nontrivial square root is a number belonging to the set .

def nontrivial_square_root(m):
"""Return the first nontrivial square root modulo m.

Args:
m (int): modulus for which want to find the nontrivial square root

Returns:
int: the first nontrivial square root of m
"""

##################
# YOUR CODE HERE #
##################


print(nontrivial_square_root(391))

or to submit your code

To interact with codercises, please switch to a larger screen size.

Learning Objectives:

  • Describe the concept of nontrivial square roots in modular arithmetic.
  • Classically factor a number using modular arithmetic techniques.