pohlig-hellman算法C语言

Pohlig-Hellman算法是一种解离散对数问题的算法，它的思想是使用小质数的幂次来分解大质数的幂次，然后通过合并结果求解原问题的解。下面是Pohlig-Hellman算法的C语言实现：

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

// 计算a^b mod m的值
long long mod_pow(long long a, long long b, long long m) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

// 计算c ≡ a^x * b^y (mod p)中x的值
long long discrete_log(long long a, long long b, long long p) {
    long long m = sqrt(p) + 1;
    long long *mem = (long long *)malloc(sizeof(long long) * m);
    long long *table = (long long *)malloc(sizeof(long long) * m);
    for (long long i = 0; i < m; i++) {
        mem[i] = mod_pow(a, i * m, p);
    }
    for (long long i = 0; i < m; i++) {
        long long x = b * mod_pow(mem[i], p - 2, p) % p;
        table[i] = -1;
        for (long long j = 0; j < m; j++) {
            if (mem[j] == x) {
                table[i] = j;
                break;
            }
        }
    }
    long long res = 0;
    long long now = 1;
    for (long long i = 0; i < m; i++) {
        if (table[i] != -1) {
            res += i * now;
            now *= m;
            res %= now;
            now %= p - 1;
        }
    }
    for (long long i = 0; i < now; i++) {
        if (mod_pow(a, res + i * (p - 1) / now, p) == b) {
            free(mem);
            free(table);
            return res + i * (p - 1) / now;
        }
    }
    free(mem);
    free(table);
    return -1;
}

// 计算b ≡ a^x (mod p)中x的值
long long pohlig_hellman(long long a, long long b, long long p) {
    long long res = 1;
    for (long long i = 2; i <= p; i++) {
        if (p % i == 0) {
            long long mul = 1;
            long long cnt = 0;
            while (p % i == 0) {
                p /= i;
                cnt++;
                mul *= i;
            }
            long long x = discrete_log(mod_pow(a, (p - 1) / mul, p), b * mod_pow(res, p - 2, p) % p, p);
            if (x == -1) {
                return -1;
            }
            res += x * mul;
        }
    }
    return res;
}

int main() {
    long long a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    long long x = pohlig_hellman(a, b, p);
    if (x == -1) {
        printf("No solution\n");
    } else {
        printf("%lld\n", x);
    }
    return 0;
}

输入格式为三个整数a、b和p，分别表示方程b ≡ a^x (mod p)中的a、b和模数p。输出格式为方程的解x，如果没有解则输出"No solution"。

需要注意的是，该算法的时间复杂度为O(𝑝^(1/2)log^2𝑝)，对于非常大的质数p，可能需要使用更高效的算法。