画布 1
现代密码学数论
  素数
    素因子
      整数分解的唯一性定理
    生成大素数
      产生一个 n 比特的随机数
        将最高位和最低位置1
          检测P 能不能被小于 2000 的素数整除
          随机选择a<p,用 a 对 p 做米勒罗宾测试
            循环多次
    米勒罗宾测试
  GCD
    gcd(a1,a2,....,an)=1,则称其为互素
      在不少于 3 个的互素正整数中,不一定两两互素
    EXGCD
      在RSA 中有重要的应用
    最小公倍数
  MOD
    同余运算
        师姐说要考大题,会给你个数的 2019 次方
        时间复杂度 O(logm)
    Euler定理
      计算小于等于 n 且与 n 互素的正整数的个数
        φ(8)=4
        依赖素数分解的唯一性定理,所以欧拉函数的分解也是唯一的
        只能有两个数 pq
      这个听说也要考,我觉得可能性更大
        费马小定理
    二次剩余
      QNRn非剩余集合
      QRn二次剩余集合
    中国剩余定理
      解同余方程组
    计算复杂性理论
      现代密码学将安全性建立在构建计算复杂性理论之上
        时间复杂度
          多项式
        空间复杂度
      P类问题
        容易问题
          确定性图灵机
      NP 问题
        困难问题
          非确定性图灵机
        NPC问题