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:

Using For Loop (Static Input)
Using For loop (User Input)

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.