Shanks Tonelli algorithm

#cpp #algorithms #programming #learning

Mathematical and modular algorithms play an important role in working with data. Instead of 1000 iterations, we can do 10, relying on knowledge of special functions and factorization.
Modular arithmetic is complex due to different dimensions and non-trivial comments on operations (+/-/*). But the abstract thinking that we use helps us solve honestly applied problems.

#include <iostream>

int Shenks_Tonelli(int p, long long n) {
    n = n % p;
    int s = p - 1, r = 0;
    while (s % 2 == 0) {
        s /= 2;
        r++;
    }
    //λ и ω  
    int l = PowMod(n, s, p);
    int w = PowMod(n, (s + 1) / 2, p);
    int mod = l, m = 0;
    while (mod != 1) {
        mod = MulMod(mod, mod, p);
        m++;
    }
    int z = quadratic nonresidue(p);
    int yd_l = PowMod(PowMod(z, s, p), pow(2, r - m), p);
    int yd_w = PowMod(PowMod(z, s, p), pow(2, r - m - 1), p);
    while (l != 1) {
        l = MulMod(l, yd_l, p);
        w = MulMod(w, yd_w, p);
    }
    return w;
}

Let's look at this algorithm (сan you create a mathematical structure using code?):

The input is an odd prime number (p) and an integer - a quadratic residue modulo p (n, Legendre symbol)
First, we obtain the expansion of p-1 using the formula above. This gives us solution invariance
Let us choose an arbitrary quadratic nonresidue z, that is, the Legendre symbol
Based on the results of working out the last cycle, we find the comparison solution w, the second comparison solution is found as p−w

In general, the complexity of the algorithm is O(ln^2(p)). If you know the complexities of algorithms, it's easy to see that the algorithm is efficient. The average complexity of sorting data on С++ is O(p*ln(p)).

Complexity affects the running time of the code and the complexity of data circulation. Can save a lot of time in companies and when working with big data.