Millar_rabin和Pollard_Rho

发表于 更新于 分类于 阅读次数：

1.Millar_rabin 素数判定

​ 基于以下两个基础：

　　1.如果p是素数，且(a,p)=1,那么(a^(p-1))%p=1(费马小定理)

​ 2.对于0<x<p，(x^2)%p=1 => x=1 或者 x=p-1

​ 处理：

​ 把p-1写成u*(2^t)，则a^(p-1)=(a^u)^2^2^2…..t次平方操作

​ 过程：

​ 随机产生一个数a，cur=a^u %p,对cur做t次平方操作，即cur=cur*cur %p，每次操作结束后，如果cur=1那么上一次的cur必须为1或者p-1否则为合数（上面的基础2），最终的cur必须为1（基础1）。

　注意：

​ long long 在计算乘法的时候要防止溢出，用2进制模拟乘法。

2.Pollard_rho，因数分解

​ 用某种方法生成a,b.计算p=gcd(a-b,n)，则p是n的一个因数，如果p=n或者p=1，则迭代的生成a,b，知道p不是n或者1，或者a,b出现循环。（通常b=(a*a+c)%p，在执行之前用Millar_rabin进行素数判定保证n不为素数).

​ 过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func get_facts(n)

      if (n是素数){fac[tot++]=n; return;}

　　　　  		p=n

     while (p>=n) p=Pollard_rho(n,rand()%(p-1)+1)

      get_facts(p)

      get_facts(n/p)

   end func