[WP] cryptohack mathematics modules-math

这部分相对做起来还是比较轻松的

目录传送门：cryptohack 练习学习汇总(writeup index)

Quadratic Residues

关键函数：libnum.sqrtmod
相关库：import libnum

该函数传入两个参数：第一个是被开方的数，第二个是所模的数（以质因数分解 dict 的形式给出，如 63 应表示为 {3:2, 7:1}

代码: cryptohack/mathematics modules-math Quadratic-Residues.py

Legendre Symbol

显然用 libnum.sqrtmod 可以轻松解决，但是根据这题的本意我们选择自己写

代码: cryptohack/mathematics modules-math Legendre-Symbol.py

Modular Square Root

这题偷个小懒，就不自己实现了。以前学 OI 的时候看的是 Cipolla 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
namespace QuadraticResidue {
    typedef long long qr_int64;
    struct qr_complex {
        qr_int64 real, imag;
        qr_complex(qr_int64 R = 0, qr_int64 I = 0) : real(R), imag(I) {}
    };
    qr_complex qrc_mul(qr_complex a, qr_complex b, qr_int64 sqrI, qr_int64 p) {
        return qr_complex((a.real * b.real + a.imag * b.imag % p * sqrI) % p, 
                          (a.real * b.imag + a.imag * b.real) % p);
    }
    /// @brief Quick Power a^n in Mod-Meaning(mod p)
    qr_int64 qpow(qr_int64 a, qr_int64 n, qr_int64 p) {
        qr_int64 ret(1);
        while (n) {
            if (n & 1) ret = ret * a % p;
            a = a * a % p;
            n >>= 1;
        }
        return ret;
    }
    /// @brief Quick Power a^n in Mod-Meaning-Complex
    qr_complex qpow(qr_complex a, qr_int64 n, qr_int64 sqrI, qr_int64 p) {
        qr_complex ret(1);
        while (n) {
            if (n & 1) ret = qrc_mul(ret, a, sqrI, p);
            a = qrc_mul(a, a, sqrI, p);
            n >>= 1;
        }
        return ret;
    }
    /**
     * @brief Quadratic Residue, or Square Root in Mod-Meaning
     * @param a for equation x^2=a (mod p)
     * @param p mod num(need to be odd-prime)
     * @return -1 if no solution, 0 if one solution, and x if x^2 = a && (p-x)^2 = a (mod p) && x < p-x
     */
    qr_int64 sqrt(qr_int64 n, qr_int64 p) {
        if (n == 0) return 0;
        if (qpow(n, (p - 1) >> 1, p) == p - 1) return -1;
        qr_int64 a = rand();
        while (qpow((a * a + p - n) % p, (p - 1) >> 1, p) == 1) a = rand();
        qr_int64 res = qpow(qr_complex(a, 1), (p + 1) >> 1, (a * a + p - n) % p, p).real;
        return std::min(res, p - res);
    }
}

这题题目建议的是 Tonelli-Shanks 算法。这两种做法的适应条件都是一样的，即奇素数，时间复杂度也是相似的（合数：可以通过分开求解，然后 CRT 组合得到结果，注意素因子越多，其二次剩余数量就越多）

python 代码使用 libnum.sqrtmod 来直接求解

代码: cryptohack/mathematics modules-math Modular-Square-Root.py

Chinese Remainder Theorem

libnum 真香啊（惊叹）

关键函数：libnum.solve_crt
相关库：import libnum

该函数传入两个参数，均为 list。第一个参数记录了余数，第二个参数记录了模数。返回为一个 int，即对应求出来的满足题意的余数

代码: cryptohack/mathematics modules-math Chinese-Remainder-Theorem.py