ConsoleApplication1.cpp

// ConsoleApplication1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>

int Shenks_Tonelli(int p, long long n) {
    n = n % p;
    int s = p - 1, r = 0;
    //получаем разложение p-1  
    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;
}

int main()
{
    std::cout << "Hello World!\n";
}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы 
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.