 # Python Program to Find Square Root Under Modulo k (When k is in Form of 4*i + 3)

In the previous article, we have discussed Python Program for Array/List Elements that Appear More than Once

Given the number N, prime number k and the task is to find the square root of the given number under modulo k(When k is in form of 4*i + 3). Here i is an integer.

Examples:

Example1:

Input:

Given prime number k=5
Given Number = 4

Output:

The Square root of the given number{ 4 } under modulo k= 2

Example2:

Input:

Given prime number k=3
Given Number = 5

Output:

No, we cannot find the square root for a given number

## Program to Find Square Root Under Modulo k (When k is in Form of 4*i + 3) in Python

Below are the ways to find the square root of the given number under modulo k (When k is in form of 4*i + 3) in python:

### Method #1: Using For Loop (Static Input)

Approach:

• Give the prime number k as static input and store it in a variable.
• Give the number as static input and store it in another variable.
• Pass the given number and k as the arguments to the sqrt_undermodk function.
• Create a function to say sqrt_undermodk which takes the given number and k as the arguments and returns the square root of the given number under modulo k (When k is in form of 4*i + 3).
• Calculate the value of the given number modulus k and store it in the same variable given number.
• Loop from 2 to the given k value using the for loop.
• Multiply the iterator value with itself and store it in another variable.
• Check if the above result modulus k is equal to the given number using the if conditional statement.
• If it is true then print the iterator value.
• Return and exit the for loop.
• Print “No, we cannot find the square root for a given number”.
• The Exit of the Program.

Below is the implementation:

# Create a function to say sqrt_undermodk which takes the given number and k as
# the arguments and returns the square root of the given number under modulo k
# (When k is in form of 4*i + 3).

def sqrt_undermodk(gvn_numb, k):
# Calculate the value of the given number modulus k and store it in the same variable
# given number.
gvn_numb = gvn_numb % k
# Loop from 2 to the given k value using the for loop.
for itror in range(2, k):
# Multiply the iterator value with itself and store it in another variable.
mul = (itror * itror)
# Check if the above result modulus k is equal to the given number using the if
# conditional statement.
if (mul % k == gvn_numb):
# If it is true then print the iterator value.
print(
"The Square root of the given number{", gvn_numb, "} under modulo k=", itror)
# Return and exit the for loop.
return
# Print "No, we cannot find the square root for a given number".
print("No, we cannot find the square root for a given number")

# Give the prime number k as static input and store it in a variable.
k = 5
# Give the number as static input and store it in another variable.
gvn_numb = 4
# Pass the given number and k as the arguments to the sqrt_undermodk function.
sqrt_undermodk(gvn_numb, k)


Output:

The Square root of the given number{ 4 } under modulo k= 2

### Method #2: Using For loop (User Input)

Approach:

• Give the prime number k as user input using the int(input()) function and store it in a variable.
• Give the number as user input using the int(input()) function and store it in another variable.
• Pass the given number and k as the arguments to the sqrt_undermodk function.
• Create a function to say sqrt_undermodk which takes the given number and k as the arguments and returns the square root of the given number under modulo k (When k is in form of 4*i + 3).
• Calculate the value of the given number modulus k and store it in the same variable given number.
• Loop from 2 to the given k value using the for loop.
• Multiply the iterator value with itself and store it in another variable.
• Check if the above result modulus k is equal to the given number using the if conditional statement.
• If it is true then print the iterator value.
• Return and exit the for loop.
• Print “No, we cannot find the square root for a given number”.
• The Exit of the Program.

Below is the implementation:

# Create a function to say sqrt_undermodk which takes the given number and k as
# the arguments and returns the square root of the given number under modulo k
# (When k is in form of 4*i + 3).

def sqrt_undermodk(gvn_numb, k):
# Calculate the value of the given number modulus k and store it in the same variable
# given number.
gvn_numb = gvn_numb % k
# Loop from 2 to the given k value using the for loop.
for itror in range(2, k):
# Multiply the iterator value with itself and store it in another variable.
mul = (itror * itror)
# Check if the above result modulus k is equal to the given number using the if
# conditional statement.
if (mul % k == gvn_numb):
# If it is true then print the iterator value.
print(
"The Square root of the given number{", gvn_numb, "} under modulo k=", itror)
# Return and exit the for loop.
return
# Print "No, we cannot find the square root for a given number".
print("No, we cannot find the square root for a given number")

# Give the prime number k as user input using the int(input()) function and
# store it in a variable.
k = int(input("Enter some random number = "))
# Give the number as user input using the int(input()) function and
# store it in another variable.
gvn_numb = int(input("Enter some random number = "))
# Pass the given number and k as the arguments to the sqrt_undermodk function.
sqrt_undermodk(gvn_numb, k)


Output:

Enter some random number = 7
Enter some random number = 2
The Square root of the given number{ 2 } under modulo k= 3

Find a comprehensive collection of Examples of Python Programs ranging from simple ones to complex ones to guide you throughout your coding journey.