Finding Square Root Under Modulo P Using Shanks Tonelli Algorithm In C++

Introduction:

In the field of number theory and modular arithmetic, determining square roots modulo a prime number is crucial, particularly in cryptography and number theory scenarios. The Shanks Tonelli Algorithm offers a streamlined approach for calculating square roots within the confines of a prime number modulo.

Syntax:

It has the following syntax:

// Function to compute Legendre symbol
int legendreSymbol(int a, int p);
 
// Function to compute modular exponentiation
int modularExponentiation(int base, int exponent, int mod);
 
// Function to find square root modulo p using Shanks Tonelli Algorithm
int shanksTonelli(int a, int p);
 
int main() {
    int a, p;
    cout << "Enter the value of a (base): ";
    cin >> a;
    cout << "Enter the value of p (prime modulo): ";
    cin >> p;
    
    if (legendreSymbol(a, p) != 1) {
        cout << "Square root does not exist modulo " << p << endl;
    } else {
        int sqrt_mod_p = shanksTonelli(a, p);
        cout << "Square root of " << a << " modulo " << p << " is: " << sqrt_mod_p << endl;

Parameters:

• ✅ a: It is a base value for which square root modulo p needs to be found.
• ✅ p: Prime modulo.

Example 1:

Let's consider an illustration to demonstrate the process of calculating a square root modulo p in the C++ programming language.

#include <iostream> 
#include <cmath> 
 
using namespace std;
 
// Forward declarations
int modularExponentiation(int base, int exponent, int mod);
int legendreSymbol(int a, int p);
 
int legendreSymbol(int a, int p) { 
    int ls = modularExponentiation(a, (p - 1) / 2, p); 
    return (ls == p - 1) ? -1 : ls; 
} 
 
int modularExponentiation(int base, int exponent, int mod) { 
    if (exponent == 0) return 1; 
    long long result = 1; 
    long long x = base % mod; 
    while (exponent > 0) { 
        if (exponent % 2 == 1) { 
            result = (result * x) % mod; 
        } 
        x = (x * x) % mod; 
        exponent = exponent / 2; 
    } 
    return result % mod; 
} 
 
int shanksTonelli(int a, int p) { 
    int q = p - 1; 
    int s = 0; 
    while (q % 2 == 0) { 
        q /= 2; 
        s += 1; 
    } 
    if (s == 1) { 
        return modularExponentiation(a, (p + 1) / 4, p); 
    } 
    int z = 2; 
    while (legendreSymbol(z, p) != -1) { 
        z++; 
    } 
    int c = modularExponentiation(z, q, p); 
    int r = modularExponentiation(a, (q + 1) / 2, p); 
    int t = modularExponentiation(a, q, p); 
    int m = s; 
    while (true) { 
        if (t == 1) { 
            return r; 
        } 
        int i = 0; 
        int temp = t; 
        while (temp != 1) { 
            temp = (temp * temp) % p; 
            i++; 
        } 
        int b = modularExponentiation(c, pow(2, m - i - 1), p); 
        r = (r * b) % p; 
        t = (t * (b * b)) % p; 
        c = (b * b) % p; 
        m = i; 
    } 
} 
 
int main() { 
    int a, p; 
 
    cout << "Enter the value of a (base): "; 
    cin >> a; 
    cout << "Enter the value of p (prime modulo): "; 
    cin >> p; 
 
    if (legendreSymbol(a, p) != 1) { 
        cout << "Square root does not exist modulo " << p << endl; 
    } else { 
        int sqrt_mod_p = shanksTonelli(a, p); 
        cout << "Square root of " << a << " modulo " << p << " is: " << sqrt_mod_p << endl; 
    } 
 
    return 0; 
}

Output:

Enter the value of a (base): 3
Enter the value of p (prime modulo): 17
Square root of 3 modulo 17 is: 6

Explanation:

• ✅ In this example, the Legendre symbol of a modulo p is calculated using the legendreSymbol function. Modular exponentiation is used to increase a modulo p to the power of (p - 1) / 2. It returns a -1 value if the result is -1; it provides the calculated Legendre symbol otherwise.
• ✅ The modular exponentiation of the base raised to the power of the exponent modulo mod is computed by the modular exponentiation function. It computes the result quickly by iterating through the exponent's binary form and applying modular arithmetic.
• ✅ shanksTonelli Function: It is the implementation of the Shanks Tonelli Algorithm. First, it determines the value of q and s such that p - 1 = q * (2^s) . After that, it checks if s is equal to 1. If it is, it directly computes the square root modulo p using modular exponentiation. Otherwise, it finds a non-quadratic residue z modulo p, and then proceeds with the main steps of the algorithm to compute the square root modulo p.
• ✅ main Function: This function reads the input values a (base) and p (prime modulo) from the user. After that, it checks if the Legendre symbol of a modulo p is equal to 1. If it is not, it prints a message indicating that the square root does not exist modulo p. Otherwise, it computes the square root modulo p using the shanksTonelli function and prints the result.

Example 2:

Let's consider a different scenario to demonstrate the concept of modulo arithmetic in the C++ programming language.

#include <iostream>
#include <cmath>
 
using namespace std;
 
// Function to compute Legendre symbol
int legendreSymbol(int a, int p) {
    int ls = (int)pow(a, (p - 1) / 2) % p;
    return (ls == p - 1) ? -1 : ls;
}
 
// Function to compute modular exponentiation
int modularExponentiation(int base, int exponent, int mod) {
    if (exponent == 0) return 1;
    int result = 1;
    base = base % mod;
    while (exponent > 0) {
        if (exponent % 2 == 1)
            result = (result * base) % mod;
        exponent = exponent >> 1;
        base = (base * base) % mod;
    }
    return result;
}
 
// Function to find square root modulo p using Shanks Tonelli Algorithm
int shanksTonelli(int a, int p) {
    if (legendreSymbol(a, p) != 1) {
        return -1; // Square root does not exist
    }
 
    int q = p - 1;
    int s = 0;
    while (q % 2 == 0) {
        q /= 2;
        s += 1;
    }
 
    int z = 2;
    while (legendreSymbol(z, p) != -1) {
        z++;
    }
 
    int c = modularExponentiation(z, q, p);
    int r = modularExponentiation(a, (q + 1) / 2, p);
    int t = modularExponentiation(a, q, p);
    int m = s;
 
    while (t != 1) {
        int i = 0;
        int temp = t;
        while (temp != 1) {
            temp = (temp * temp) % p;
            i++;
        }
        int b = modularExponentiation(c, pow(2, m - i - 1), p);
        r = (r * b) % p;
        t = (t * b * b) % p;
        c = (b * b) % p;
        m = i;
    }
 
    return r;
}
 
int main() {
    int a = 5; // Base
    int p = 11; // Prime modulo
    
    int sqrt_mod_p = shanksTonelli(a, p);
    cout << "Square root of " << a << " modulo " << p << " is: " << sqrt_mod_p << endl;
    
    return 0;
}

Output:

Square root of 5 modulo 11 is: 4

Explanation:

• ✅ Legendre Symbol Calculation: In this example, evaluate the Legendre symbol to check if a square root exists modulo the prime number p.
• ✅ Modular Exponentiation: Implement modular exponentiation efficiently to handle large numbers during exponentiation.
• ✅ Algorithm Initialization: Determine the value of s and find a suitable quadratic non-residue z.
• ✅ Initial Computation: Compute c, r, and t based on the given input values and previously determined parameters.
• ✅ Iteration: Iterate through a loop to adjust values and find the square root modulo p.
• ✅ Result Retrieval: Obtain the square root modulo p after completing the iteration process. If a square root exists, return the result; otherwise, indicate its non-existence.

Real-World Applications:

Several Real-world applications of the Modulo Arithmetic are as follows:

• ✅ Cryptography: Cryptography uses modular arithmetic as a primary operation for a large variety of encryption and decryption methods. Modular operations are one of the main numerical variables in RSA encoding and signature scheme. The implementation of Shanks Tonelli Algorithm in the cryptographic protocols helps enhance their high level of efficiency and secure communication keeping the data free from any other deviations.
• ✅ Error Detection and Correction: Error detection and correction codes frequently use characteristics of finite fields, which are digital number representations created with modulo arithmetic. If square roots are taken modulo the prime number, the algorithms can verify that the received data has no error and ensure its correct transmission, which is particularly true in communication systems and storage devices.
• ✅ Digital Signal Processing: Algorithms for modulus operation (DSP) necessitate re-coding which uses integer numbers. Compute square roots to be used as moduli of prime numbers in DSP algorithms in such a way that it would decrease the processing time and hence can be applied to improve various audio and image processing technologies.
• ✅ Finite Element Analysis: Finite element analysis (FEA) is commonly employed in engineering and scientific simulations to analyze diverse systems successfully by incorporating complex apatite. FEA tends to be an operation that entails solving large systems of linear equations; therefore, it is at this stage that modular arithmetic may be performed. An efficient operation of square roots in modules of a prime number brings about more precisely and faster FEA, improving engineering decisions and optimizations.
• ✅ Number Theory Research: Shank-Tonelli Algorithm is given credit to the development of the most recent number-theory techniques for the effective resolution of modular arithmetic issues. Participants of investigations on quadratic residues, Diophantine equations, and elliptic curves use algorithms like Shanks Tonelli to explore mathematically deeper inquiries and reveal innovative cryptographic methods.

Conclusion:

Shanks Tonelli Algorithm provides a streamlined method for calculating square roots within the constraints of a prime number. This technique proves invaluable in scenarios where modular arithmetic holds significant importance, especially in cryptographic contexts. Through the utilization of Legendre symbols and modular exponentiation, we can determine the square root modulo p with a manageable level of computational intricacy. The C++ code snippet furnished here can be enhanced and seamlessly incorporated into diverse applications that necessitate modular arithmetic computations.