Modulo-Square-Root

Square Root Modulo P

In log(n) time provided 4*i+3(OR p%4=3)

Task: Given a number ‘n’ and a prime ‘p’, find square root of n under modulo p if it exists.

Input Format: We need to give the value of n and p as input.

Output Format: The output will give the modulo square root if it exist and p is valid.

Sample Input 1:-

Enter the value of p: 7 Enter the value of n: 2

Sample Output 1:-

Square root is: 4

Sample Input 2:-

Enter the value of p: 15 Enter the value of n: 2

Sample Output 2:-

Square root doesn't exist!

Sample Input 3:-

Enter the value of p: 8 Enter the value of n: 2

Sample Output 3:-

Invalid value of p.

Implemented in:-

• C++