数论

        模运算：两个数求除法后所得到的余数，符号 %

                注意：

                        正数取模的答案是唯一的， 负数取模的答案不唯一

                        比如 -7 % 3 = -1（此时商为  2） 

                                -7 % 3 = 2（此时商为 3）

                快速幂：其实就是幂运算，只不过在计算机中直接幂运算会比较耗时，所以就研究出了一种叫做 快速幂 的算法

                        快速幂就是在 O(logn) 的时间复杂度内进行幂运算的

                常用的实现方法是 分治或二进制：

                        分治：比如计算 ，如果 n 是偶数，；如果 n 是奇数， 

                        二进制：比如计算 ，可以拆成  来计算，观察指数841，分别是，于是我们就可以对二进制各个位进行标记，在对每一个简单幂数（等）的值进行计算，最后在累乘即可

                        EG：

#include <iostream>


using namespace std;

typedef long long ll;

//分治
ll qr(ll a,ll n)
{
    if(n == 0)
        return 1;

    ll res = qr(a, n / 2);

    if(n % 2 == 0)
        return res * res;
    else    
        return res * res * a;
}


//二进制
ll qi(ll a,ll n)
{
    ll res = 1;

    while(n > 0)
    {

        if(n & 1)
            res *= a;

        a *= a;

        n >>= 1;
    }

    return res;
}


int main()
{
    long long a, n;
    cout << "输入底数a和指数n: ";
    cin >> a >> n;

    cout << "递归法结果: " << qr(a, n) << endl;
    cout << "迭代法结果: " << qi(a, n) << endl;

    return 0;
}

                模逆元（扩展欧几里得 / 费马小定理）：

                        扩展欧几里得：

#include <iostream>


typedef long long ll;

long long exgcd(ll a,ll m,ll &x,ll &y)
{
    if(m == 0)
    {
        x = 1;
        y = 0;
        return a;
    }

    ll d = exgcd(m,a % m,y,x);
    y -= (a / m) * x;

    return d;
}


ll modInverse(ll a,ll m)
{
    ll x,y;
    ll d = exgcd(a,m,x,y);

    if(d != 1)
        return -1;


    return (x % m + m) % m;

}


int main()
{   
    ll a,m;

    std::cout << "请输入 a 和 模数 m：";

    if(!(std::cin >> a >> m))
        return 0;

    ll inv = modInverse(a,m);

    if(inv == -1)
        std::cout << "gcd(" << a << ", " << m << ") != 1,逆元不存在" << std::endl;
    else
        std::cout << a << "模" << m << "的逆元是：" << inv << std::endl;

    return 0;
}

        费马小定理：扩展欧几里得的简化版

                        p 是一个质数，且整数 a 不是 p 的倍数，那么;

                        对于任意整数a，都有(不要求a，p互质)

#include <iostream>


typedef long long ll;


ll quick_pow(ll base,ll exp,ll mod)
{
    ll res = 1;

    base %= mod;

    while(exp > 0)
    {
        if(exp % 2 == 1)
            res = (res * base) % mod;

        base = (base * base) % mod;

        exp /= 2;
    }

    return res;
}

ll fermatInverse(ll a,ll p)
{
    if(a % p == 0)
        return 0;

    return quick_pow(a,p - 2, p);
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    
    ll a,p;
    
    if(!(std::cin >> a >> p))
        return 0;
    std::cout << "输入: a = " << a << ", p = " << p;

    ll inv = fermatInverse(a,p);

    if(inv == -1)
        std::cout << " -> 结果: 逆元不存在 (a 是 p 的倍数)" << std::endl;
    else
    {
        std::cout << " -> 逆元: " << inv;

        if((a * inv) % p == 1)
            std::cout << " (验证成功: " << a << "*" << inv << " % " << p << " = 1)" << std::endl;
        else
            std::cout << " (验证失败!)" << std::endl;
    }

    return 0;
}


//     // 样例 1: 基础质数测试
//     test(3, 11);    // 预期: 4

//     // 样例 2: 较大的质数
//     test(10, 17);   // 预期: 12

//     // 样例 3: a > p 的情况
//     test(20, 7);    // 20 % 7 = 6, 6在模7下的逆元是6 (6*6=36=35+1)

//     // 样例 4: 算法竞赛常用大质数模
//     test(3, 1000000007); // 预期: 333333336

//     // 样例 5: 异常情况 (a 是 p 的倍数)
//     test(14, 7);    // 预期: 逆元不存在

                        

                模运算性质

        素数与因数分解

                欧几里得算法

                扩展欧几里得

        欧拉函数 & 欧拉定理

                线性筛求 φ

                分解质因数求 φ

        中国剩余定理

                手写 CRT 模板

                理解分解大模数问题

抽象代数

        群

        有限域

椭圆曲线

        点加法

        群结构

        优点：更短密钥，更强安全

        

概率论与随机性

        随机数生成

        安全性证明

        零知识证明

计算复杂性理论

        P vs NP
        单向函数（One-way function）

常见的难题

        大整数分级，离散对数问题

线性代数

        编码理论

        格雷码（后量子密码）

信息论

        熵

        信息量；

哈希函数

        单向性、抗碰撞、雪崩效应

、