用c编成实现模重复平方根的算法

下面是用C语言编写的实现模重复平方根的算法：

#include <stdio.h>
#include <math.h>

int modSqrt(int n, int p) {
    if (n == 0 || p == 2) {
        return n % p;
    }
    if (pow(n, (p - 1) / 2) == -1) {
        return -1;
    }
    if (n % p == 0) {
        return 0;
    }
    if (p % 4 == 3) {
        return (int) pow(n, (p + 1) / 4) % p;
    }
    int s = p - 1;
    int e = 0;
    while (s % 2 == 0) {
        s /= 2;
        e++;
    }
    int a = 2;
    while (pow(a, (p - 1) / 2) != -1) {
        a++;
    }
    int x = pow(n, (s + 1) / 2) % p;
    int b = pow(n, s) % p;
    int g = pow(a, s) % p;
    int r = e;
    while (1) {
        if (b == 0) {
            return 0;
        }
        if (b == 1) {
            return x;
        }
        int m = 0;
        for (int i = 1; i < r; i++) {
            if (pow(b, pow(2, i)) % p == 1) {
                m = i;
                break;
            }
        }
        int gs = pow(g, pow(2, r - m - 1)) % p;
        x = (x * gs) % p;
        b = (b * pow(gs, 2)) % p;
        g = pow(gs, 2) % p;
        r = m;
    }
}

int main() {
    int n = 123456789;
    int p = 1000000007;
    int result = modSqrt(n, p);
    printf("%d", result);
    return 0;
}

其中，`modSqrt`函数实现了模重复平方根的算法，输入两个整数`n`和`p`，返回`n`模`p`下的平方根。在`main`函数中，我们对`n`取模`p`下的平方根进行了计算，并输出了结果。你可以根据需要修改`n`和`p`的值。