前些日子在和队友训练杭电多校的时候，遇到了这样一道题HDU 6632，要求一个质数群上的离散对数问题。这个质数有一个特性，。

一般来讲，离散对数问题的求解主要有算法，算法等，前者效率为，空间复杂度也是，后者节省了空间，时间复杂度期望略慢于前者。但是这道题，难于承受。那么关键就落在了的因子很小这一信息上。

其实在去年，做一个全国密码竞赛的时候，尝试求解过椭圆曲线离散对数问题，当时也接触过针对群阶因子不大的攻击，但是因为当时的赛题，群阶被人为取定成都是素数，那么就不存在所谓小因子，所以虽然当时资料查到过 方法，但是没有加以学习。

这次ACM中碰到这样的题，只能怪自己当时没有仔细了解了。

是针对群阶的分解中质数不大的情况的，它的目标是将一个大的离散对数问题，分解成多个离散对数问题，这些子问题中，指数的范围是被质数的大小所限制住的。

这里仅仅叙述针对质数群的算法，参考文章：https://blog.csdn.net/oampamp1/article/details/104061969。

另外针对椭圆曲线群的，步骤和方法其实基本一致，参考：https://blog.csdn.net/oampamp1/article/details/104061969。

1. 将质因子分解，（m为质因子个数）

2. 对于每个质因子，将我们要求的答案，模上的结果，拆分成进制的形式：
   

3. 令，展开，得到
   
   注意到左边后面的项都是1，所以得到
   

4. 这也是一个离散对数问题，但是由于的所有系数（进制的缘故），所以求解是比较方便的。可以用或者解决。当然很小的情况下，暴力穷举就足够了，比如本题。

5. 得到之后，我们在的等是两边除，那么得到了新的，在进制下不再有个位，我们取，展开来求十位。

6. 进一步重复操作，一直到所有都被求出。于是得到
   

7. 在算出个关于的模方程之后，来一次中国剩余定理即可（不需要扩展CRT,因为模数互质）。

几个需要注意的地方：

1. 每一步的模数是啥，需要注意。
2. 由于不是原根时，在中可能有多个解，第三步求解，可能满足条件的有多个，这时候你只能任取一个。所以有多个解的时候，不能保证求出来是最小的那个。
3. 普遍上的Pohlig-Hellman算法的效率，在知道因子分解之后，取决于和暴力求解的部分，两个部分上界都受限于最大的质数因子大小。因此在我们设计离散对数密码算法时，群阶的最大质因子大小至少应该是才安全。如果是椭圆曲线离散对数，群阶甚至可以直接设置成质数。
4. 在求解本题时，有两种方法：一种是直接求离散对数，如果所有求出来后，剩下的不等于1，那么就是无解。但是有解的话不一定求得最小，还需要求出的阶数。另一种是先求原根，再对各自求一次离散对数，再用扩展GCD来求出答案，扩展GCD可以比较快保证求出来最小正值。两种效率和码量应该差不多。这里用第二种。
5. 普适的模板之后再补充，这里只给出本题的代码，只考虑了两种模数。

#include<cstdio>

using namespace std;
using LL=long long;

int T, c2, c3;
LL a, b, p, g, xx, yy, rr, tt, xa, xb, tmp, ans;

LL quick_power(LL a, LL b, LL mo) {
    LL ans = 1, base = a;
    while (b) {
        if (b & 1)
            ans = (__int128) ans * base % mo;
        base = (__int128) base * base % mo;
        b >>= 1;
    }
    return ans;
}

LL Root(LL p) {
    bool f = false;
    LL i;
    for (i = 1; !f; i++) {
        f = true;
        if (quick_power(i, (p - 1) >> 1, p) == 1)
            f = false;
        if (f && quick_power(i, (p - 1) / 3, p) == 1)
            f = false;
    }
    return i - 1;
}

void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if (!b)
        d = a, x = 1, y = 0;
    else
        gcd(b, a % b, d, y, x), y -= x * (a / b);
}

LL Pohlig_Hellman(LL g, LL b, LL p) {
    LL fp = 1, sum = 1, mo2, mo3, val2 = 0, val3 = 0, coef, temp, tb = b, invg = quick_power(g, p - 2, p);
    for (int j = 1; j <= c2; j++) {
        fp <<= 1;
        LL _b = quick_power(tb, (p - 1) / fp, p);
        coef = _b == 1 ? 0 : 1;
        temp = coef * (fp >> 1);
        tb = (__int128) tb * quick_power(invg, temp, p) % p;
        val2 += temp;
    }
    mo2 = fp;
    LL _g = quick_power(g, (p - 1) / 3, p);
    tb = b;
    fp = 1;
    for (int j = 1; j <= c3; j++) {
        fp *= 3;
        LL _b = quick_power(tb, (p - 1) / fp, p);
        if (_b == 1)
            coef = 0;
        else if (_b == _g)
            coef = 1;
        else
            coef = 2;
        temp = coef * (fp / 3);
        tb = (__int128) tb * quick_power(invg, temp, p) % p;
        val3 += temp;
    }
    mo3 = fp;
    if (mo2 == 1)
        return val3;
    if (mo3 == 1)
        return val2;
    LL inv3 = quick_power(mo3, (mo2 >> 1) - 1, mo2), inv2 = quick_power(mo2, (mo3 / 3 * 2) - 1, mo3);
    return (LL) (((__int128) inv3 * val2 % mo2 * mo3 + (__int128) inv2 * val3 % mo3 * mo2) % (p - 1));
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld", &p, &a, &b);
        tmp = p - 1;
        c2 = c3 = 0;
        while (!(tmp & 1))
            tmp >>= 1, c2++;
        while (!(tmp % 3))
            tmp /= 3, c3++;
        g = Root(p);
        xa = Pohlig_Hellman(g, a, p);
        xb = Pohlig_Hellman(g, b, p);
        gcd(xa, p - 1, rr, xx, yy);
        if (xb % rr) {
            puts("-1");
            continue;
        }
        tt = (p - 1) / rr;
        ans = (__int128) (xx < 0 ? xx + tt : xx) * (xb / rr) % tt;
        printf("%lld\n", ans ? ans : tt);
    }
    return 0;
}