数论ex

数学学得太差了补补知识点or复习

Miller-Rabin 和 Pollard Rho

• Miller-Rabin

  前置知识：

  1. 费马小定理
     [ a^{p-1}equiv 1pmod p,p is prime ]

  2. 二次探测（mod奇素数下1的二次剩余）
     [ x^2equiv 1pmod pRightarrow x=1 or p-1 ]
     如果不是 (bmod) 奇素数，二次剩余可能是更多的值

  如果把费马小定理反过来用来检测一个数是否是素数，虽然是错的，但是反例比较少，如果配合二次探测进行测试并取多个a，可以把1e18内的所有数是否是质数判断出来。

  具体的，取(a)为前(12)个质数((2,3,5,7,11,13,17,19,23,29,31,37))

  然后用费马小定理进行测试，如果(a^{p-1}equiv 1pmod p)，就根据二次探测检验是否有(a^{(p-1)/2}equiv 1pmod p)，如果值为(1)，就递归((p-1)/4)处理，如果值为(p-1)，无法向下递归直接返回true，否则返回false

  Code:

  const int pri[]={2,37};
  bool ck(ll a,ll k,ll p)
  {
      ll x=qp(a,k,p);//a^k mod p
      if(x!=1&&x!=p-1) return false;
      if(x==p-1) return true;
      if(k&1) return true;
      return ck(a,k>>1,p);
  }
  bool Miller_Rabin(ll p)
  {
      if(p==1) return false;
      for(int i=0;i<12;i++) if(p%pri[i]==0) return p==pri[i];
      for(int i=0;i<12;i++)
          if(!ck(pri[i],p-1,p))
              return false;
      return true;
  }

  这样做的复杂度是(12log^2 n)，其中因子2的个数是一个(log)，里面每次还做了一次快速幂，如果里面用了龟速乘就更完蛋了。

  考虑从底向上做，就是说，先求出(x-1)除2到不能除的最底层的(x)，这样每次向上一层直接就是(x^2)了

  考虑在某一层(x=1)，那么如果之前的一层的(x'not=p-1)的话，就不合法了，或者在最上面一层(x)仍然不为(1)，也是不合法的

  这样就优化掉了一个(log)

  Code:

  const int pri[]={2,37};
  bool Miller_Rabin(ll p)
  {
      if(p==1) return false;
      for(int i=0;i<12;i++) if(p%pri[i]==0) return p==pri[i];
      ll res=p-1;int k=0;
      while(!(res&1)) res>>=1,++k;
      for(int i=0;i<12;i++)
      {
          ll x=qp(pri[i],res,p);
          for(int j=0;j<k&&x>1;j++)
          {
              ll y=(ll)x*x%p;
              if(y==1&&x!=p-1) return false;
              x=y;
          }
          if(x!=1) return false;
      }
      return true;
  }

  洛谷 P3383 【模板】线性筛素数

  完整Code

• Pollard Rho

  朱老大说的非常好

  我再胡乱说一个自己瞎编的假装是给自己看的，说一下流程把

  首先是不加倍增优化的

  考虑在(n)范围内rand两个数(x,y)，如果(gcd(x+n-ybmod n,n)not=1,n)，那么(|x-y|)就是一个(n)的约数。

  现在搞一个近似随机函数(f)，保证(f)在(bmod n)近似均匀随机

  令(f_m(x)=f(f_{m-1}(x)))，因为(f)取值有限，所以一定会出现循环，考虑在出现循环的时候如果我们还没有找到约数，我们就退出。

  具体的，初始(x=y=rand())，然后(x)一步一步跳，(x'=f(x))，(y)两步两步跳(y'=f(f(y)))，如果(x)与(y)又跳到相等了，就说明找到了环，可以证明这个环最多被走一次就找到了。

  发现(f(x)=x^2+c)的时候效果好，(c)是随机正整数。

  于是我们每次(rand())一个(x,y)和(c)去找一个约数，然后分解(n)，递归子问题继续找，知道Miller Rabin检测(n)为素数。

  这样的复杂度是(O(n^{frac{1}{4}}log n))的

  考虑去优化掉(log)

  打雀去了，明天再写