一、什么是大数分解

给一个大数n,将它分解成质因子的乘积的形式。比如：

49716575159173590222=3*3*2*3*19*37199*73331*17763763

大数分解最简单的思想也是试除法，就是从2到sqrt(n)，一个一个的试验，直到除到1或者循环完，最后判断一下是否已经除到1了即可。但这样效率很低，需要使用其他算法来实现大数分解。

大数应该至少要在20位以上的整数，因为超过20位以上的整数，用普通的试除法就很难分解。

二、大数分解算法：

1、Miller-Rabin 素性检测算法

Miller-Rabin算法本质上是一种概率算法，存在误判的可能性，但是出错的概率非常小。出错的概率到底是多少，存在严格的理论推导。

MillerRabbin素性测试算法涉及到二个定理：

### 1.1、费马小定理

如果p为质数:a^(p-1)≡ 1 (mod p)

注意，p是质数，一定满足费马小定理，但是，满足费马小定理的数，并不能证明就是质数。

### 1.2、二次探测定理

对于任意一个小于p的正整数x，发现1（mod p）的非平凡平方根存在，则说明p是合数。

如果p是一个素数，0 < x< p, 则方程 x^2 ≡ 1(mod p) 的解为 x=1 ,x= p-1。

反之如果 x^ 2 ≡ 1(mod p) 的解不是 x=1 ,x= p-1 那 p 就不是素数

2、Pollard-rho算法

由于普通的试除法进行大数分解，复杂度是相当高的。一种很妙的思路是找到一个因子（不一定是质因子），然后再一路分解下去。

这就是基于Miller_rabin的大数分解法Pollard_rho大数分解。Pollard_rho算法的大致流程是 先判断当前数是否是素数（Miller_rabin）了，如果是则直接返回。

如果不是素数的话，试图找到当前数的一个因子（可以不是质因子）。然后递归对该因子和约去这个因子的另一个因子进行分解。

二、单线性——实现大数分解

实现代码

import sysfrom random import randintfrom math import gcdimport timesys.setrecursionlimit(100000)import threadingdef isPrime(n,t=50):           t = min(n-3,t)    if n <2:                return    if n==2: return True    s = n-1    r = 0        #分解成2^r*s形式     while s%2==0:        r=r+1        s=s//2    tested=set()    #出错概率1/2^t     for i in range(t):        a = randint(2,n-2)        while a in tested:#不取重复随机数a            a = randint(2,n-2)        tested.add(a)                x= pow(a,s,n)        if x==1 or x==n-1:            continue  #继续返回测试                #二次探测        for j in range(r):            x= x*x % n            if x==1 or x==n-1:break #继续返回测试        else:            return False #合数    return Truedef factor(n):        #递归出口    if n==1: return     if isPrime(n):        #print(n)        return [n]    #初始化：因子，环数，x1,x2由x1决定    p=1    loop=2    x1 = randint(1, n-1)    x2 = x1    #随机取一个常数c，用来构造x1,x1=x1*x1+c    c = randint(1,n)    #循环直到找到n的质因子p    while p==1:                    for i in range(loop):            #如果找到一个因子，则退出            if p>1:break                        x1=(x1*x1+c)%n             #如果x1=x2,则重新选择x1                       if x1==x2:                c = randint(1,n)                continue            p = gcd(x1-x2,n) #如果p>1刚找到n的一个质因子p        loop=loop *2 #环数加倍        x2 = x1    #如果找到n的一个质因子p，则递归继续            return factor(p)+factor(n//p)n=int(input("n:"))print(n,len(str(n)))start_time=time.time()print(factor(n))print('运行时间：', time.time()-start_time)

运行结果：

n:123456123456123456123456

123456123456123456123456 24

[3, 2, 2, 2, 2, 2, 2, 101, 137, 73, 643, 9901, 99990001]

运行时间： 0.003989696502685547

单线性——演示视频：

视频加载中...

三、多线程——实现大数分解

import sysfrom random import randintfrom math import gcdimport timeimport threadingdef isPrime(n,t=50):           t = min(n-3,t)    if n <2:                return    if n==2: return True    s = n-1    r = 0        #分解成2^r*s形式     while s%2==0:        r=r+1        s=s//2    tested=set()    #出错概率1/2^t     for i in range(t):        a = randint(2,n-2)        while a in tested:#不取重复随机数a            a = randint(2,n-2)        tested.add(a)                x= pow(a,s,n)        if x==1 or x==n-1:            continue  #继续返回测试                #二次探测        for j in range(r):            x= x*x % n            if x==1 or x==n-1:break #继续返回测试        else:            return False #合数    return Truelst=[] #全局变量使用t_list=[] #线程列表def factor(n):        #print('当前线程的名字是： ', threading.current_thread().name)          #递归出口    if n==1: return     if isPrime(n):        #print(n,",")        lst.append(n) #全局变量存放结果        return n    #初始化：因子，环数，x1,x2由x1决定    p=1    loop=2    x1 = randint(1, n-1)    x2 = x1    #随机取一个常数c，用来构造x1,x1=x1*x1+c    c = randint(1,n)    #循环直到找到n的质因子p    while p==1:                    for i in range(loop):            #如果找到一个因子，则退出            if p>1:break                        x1=(x1*x1+c)%n             #如果x1=x2,则重新选择x1                       if x1==x2:                c = randint(1,n)                continue            p = gcd(x1-x2,n) #如果p>1刚找到n的一个质因子p        loop=loop *2 #环数加倍        x2 = x1    #如果找到n的一个质因子p，则递归继续             t1=threading.Thread(target=factor,args=(p,))    t2=threading.Thread(target=factor,args=(n//p,))    t_list.append(t1)    t_list.append(t2)    t1.start()    t2.start()    #return t1,t2n=int(input("n:"))start_time=time.time()factor(n)for t in t_list:    t.join()print("运行结果：",lst)print('运行时间：', time.time()-start_time)###############验证分解后的值s=1for i in lst:    s=s*iprint("n:",s,s==n)

运行结果：

n:123456123456123456123456

运行结果： [2, 2, 3, 2, 2, 2, 101, 2, 73, 137, 643, 9901, 99990001]

运行时间： 0.0071179866790771484

多线程——演示视频：

视频加载中...

四、多进程——实现大数分解

import sysfrom random import randintfrom math import gcdimport timeimport multiprocessingdef isPrime(n,t=50):           t = min(n-3,t)    if n <2:                return    if n==2: return True    s = n-1    r = 0        #分解成2^r*s形式     while s%2==0:        r=r+1        s=s//2    tested=set()    #出错概率1/2^t     for i in range(t):        a = randint(2,n-2)        while a in tested:#不取重复随机数a            a = randint(2,n-2)        tested.add(a)                x= pow(a,s,n)        if x==1 or x==n-1:            continue  #继续返回测试                #二次探测        for j in range(r):            x= x*x % n            if x==1 or x==n-1:break #继续返回测试        else:            return False #合数    return Truep_list=[]def factor(n,lst):        #print(multiprocessing.current_process(),multiprocessing.current_process().pid)           #递归出口    if n==1: return     if isPrime(n):        #print(n,",")        lst.append(n) #全局变量存放结果        return n    #初始化：因子，环数，x1,x2由x1决定    p=1    loop=2    x1 = randint(1, n-1)    x2 = x1    #随机取一个常数c，用来构造x1,x1=x1*x1+c    c = randint(1,n)    #循环直到找到n的质因子p    while p==1:                    for i in range(loop):            #如果找到一个因子，则退出            if p>1:break                        x1=(x1*x1+c)%n             #如果x1=x2,则重新选择x1                       if x1==x2:                c = randint(1,n)                continue            p = gcd(x1-x2,n) #如果p>1刚找到n的一个质因子p        loop=loop *2 #环数加倍        x2 = x1    p1=multiprocessing.Process(target=factor,args=(p,lst))              p2=multiprocessing.Process(target=factor,args=(n//p,lst))       p_list.append(p1)    p_list.append(p2)    p1.start()    p2.start()    return p1,p2def pmain(__name__, p_list, factor):    if __name__ =='__main__':        n=int(input("n:"))        lst= multiprocessing.Manager().list()        #定义进程共享列表变量        start_time=time.time()        factor(n,lst)        for p in p_list:            p.join()        print("运行结果：",lst)        print('运行时间：', time.time()-start_time)        ##############验证分解后的值        s=1        for i in lst:            s=s*i        print("n:",s,s==n)pmain(__name__, p_list, factor)

运行结果：

n:123456123456123456123456

运行结果： [2, 2, 3, 2, 2, 2, 2, 137, 73, 101, 643, 9901, 99990001]

运行时间： 1.7835564613342285

多进程——演示视频：

视频加载中...

五、单线性、多线程、多进程性能比较

通过下面一组数据比较，发现多线程在CPU密集型操作上，并没有的优势，多进程性能表现更优。