【概述】

整數(shù)分解目前仍是世界級難題，是非常重要的研究方向，其有很多種算法，性能上各有差異，本文僅介紹試除法、Fermat 算法、Pollard Rho 算法。

【試除法】

試除法也叫窮舉法，是整數(shù)分解算法中最簡單和最容易理解的算法，但也是效率最低的算法。

試除法是用小于等于 n 的每個素數(shù)去試除待分解的整數(shù)，如果找到一個數(shù)能夠整除除盡，這個數(shù)就是待分解整數(shù)的因子。

試除法一定能夠找到 n 的因子，因為它檢查 n 的所有可能的因子，所以如果這個算法失敗，也就證明了 n 是個素數(shù)，因此，試除法也常用來判斷一個數(shù)是不是質(zhì)數(shù)。

bool judge(int n) {if(n==1)//1不是一個有效因數(shù)return false;for(int i=2;i<sqrt(n);i++)//如果能被整除，說明是因數(shù)if(n%i==0)retrun true;return false; }

【Fermat 算法】

Fermat 算法分解大數(shù)的效率并不高，但比起試除法要好了很多，且每次計算都是計算出 N 的一個因子，更降低了其效率。

1.費(fèi)馬整數(shù)分解

對于一個任意的偶數(shù)，我們都可以通過不斷提出為 2 的質(zhì)因子使其最終簡化為一個 2 的 n 次冪與一個奇數(shù)，因此，任意一個奇數(shù)都可以表示為：N=2*n+1

若這個奇數(shù) N 是一個合數(shù)，根據(jù)唯一分解定理，其一定可以寫成 N=c*d 的形式，不難發(fā)現(xiàn)，式中 c、d 均為奇數(shù)

設(shè)：c>d，令 a=(c+d)/2，b=(c-d)/2

可得：N=c*d=a*a-b*b

例如：

2.費(fèi)馬因式分解算法

由于?

因此?

即：

因此，我們可以從??開始枚舉，計算??為完全平方數(shù)即可求出 a、b，從而可以求得：c=a+b，d=a-b(a>b)

int res[N]; void Fermat(int n) {int a,b,temp;a=sqrt(n);if(a*a<n)a++;while(1)//y^2=x^2-n{temp=a*a-n;b=sqrt(a*a-n);if(b*b==temp)break;a++;}res[0]=a;//存儲a的值res[1]=b;//存儲b的值 }

【Pollard Rho 算法】

為進(jìn)一步提高效率，解決因數(shù)太多無法存儲的問題，我們有了 Pollard Rho 算法。

1.算法原理

其原理已知待分解的大整數(shù) n，再通過某種方法得到兩個整數(shù) a、b，計算?，直到 p不為1，或 a、b 出現(xiàn)循環(huán)為止，然后再判斷 p 的值，若 p=n 或 p=1，那么返回的 n 是一個質(zhì)數(shù)，否則返回的 p 是 n 的一個因子，因此我們可以遞歸的計算 Pollard(p) 與 Pollard(n/p) ，從而求出 n 所有的因子。

實(shí)際操作中，我們通常使用函數(shù)：?來不斷生成偽隨機(jī)數(shù)，用于逐步迭代計算 a、b 的值。

實(shí)踐中，常取 c=1，再任意取兩初值 a、b，即：，在下一次計算中，將 b 的值賦給 a，再次使用上式來計算新的 b 的值，直至 a、b 出現(xiàn)循環(huán)。

但是這樣判斷 a、b 的循環(huán)十分麻煩，例如生成偽隨機(jī)數(shù)為：2，10，16，23，29，13，16，23，29，13...時，很難判斷循環(huán)，因此我們可以采用 Floyd?判環(huán)算法來判斷循環(huán)。

2.Floyd 判環(huán)算法實(shí)現(xiàn)Pollard Rho 算法

利用多項式 f(x) 迭代出 的值，然后設(shè)定 x、y?的初值，選用多項式進(jìn)行迭代

每次令：，即：

當(dāng) x=y 時即出現(xiàn)循環(huán)

int GCD(int a,int b) {return b?GCD(b,a%b):a; }int Pow_Mod(int a, int b, int m) {int res=1;while(b){if(b&1)res=(res*a)%m;a=(a*a)%m;b>>=1;} }long long pollard_rho(long long x, long long c)//尋找一個因子 {long long i=1,k=2;srand(time(NULL));long long x0=rand()%(x-1)+1;//產(chǎn)生隨機(jī)數(shù)x0(并控制其范圍在1 ~ x-1之間)long long y=x0;while(1){i++;x0=(Pow_Mod(x0,x0,x)+c)%x;long long gcd=GCD(y-x0,x);if(gcd!=1&&gcd!= x)return gcd;if(y==x0) return x;if(i==k){y=x0;k+=k;}} }

3.存儲大整數(shù)的所有因子

組合使用 Pollard Rho 算法與 Miller Rabin 算法，可求出大整數(shù)的所有因子。

LL Mult_Mod(LL a,LL b,LL m)//res=(a*b)%m {a%=m;b%=m;LL res=0;while(b){if(b&1)res=(res+a)%m;a=(a<<=1)%m;b>>=1;}return res%m; } LL Pow_Mod(LL a, LL b, LL m)//res=(a^b)%m {LL res=1;LL k=a;while(b){if((b&1))res=Mult_Mod(res,k,m)%m;k=Mult_Mod(k,k,m)%m;b>>=1;}return res%m; }bool Witness(LL a,LL n,LL x,LL sum) {LL judge=Pow_Mod(a,x,n);if(judge==n-1||judge==1)return 1;while(sum--){judge=Mult_Mod(judge,judge,n);if(judge==n-1)return 1;}return 0; }bool Miller_Rabin(LL n) {if(n<2)return 0;if(n==2)return 1;if((n&1)==0)return 0;LL x=n-1;LL sum=0;while(x%2==0){x>>=1;sum++;}int times=20;for(LL i=1;i<=times;i++){LL a=rand()%(n-1)+1;//取與p互質(zhì)的整數(shù)aif(!Witness(a,n,x,sum))//費(fèi)馬小定理的隨機(jī)數(shù)檢驗return 0;}return 1; } LL GCD(LL a,LL b) {return b==0?a:GCD(b,a%b); } LL Pollard_Rho(LL n,LL c)//尋找一個因子 {LL i=1,k=2;LL x=rand()%n;//產(chǎn)生隨機(jī)數(shù)x0(并控制其范圍在1 ~ x-1之間)LL y=x;while(1){i++;x=(Mult_Mod(x,x,n)+c)%n;LL gcd=GCD(y-x,n);if(gcd<0)gcd=-gcd;if(gcd>1&&gcd<n)return gcd;if(y==x)return n;if(i==k){y=x;k<<=1;}} }int total;//因子的個數(shù) LL factor[N];//存儲所有因子的數(shù)組，無序的 void Find_fac(LL n)//對n進(jìn)行素因子分解，存入factor {if(Miller_Rabin(n))//是素數(shù)就把這個素因子存起來{factor[++total]=n;return;}long long p=n;while(p>=n)//值變化，防止陷入死循環(huán)kp=Pollard_Rho(p,rand()%(n-1)+1);Find_fac(n/p);Find_fac(p); }

【例題】?

• Prime Test（POJ-1811）(Pollard Rho 與 Miller Rabin 求大整數(shù)分解)：點(diǎn)擊這里

總結(jié)

以上是生活随笔為你收集整理的数论 —— 整数分解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。