關于數論，想到的就是密碼系統和大素數。大素數的易求和因子分解的高難度是密碼系統安全性的數學基礎。輸入一個大的整數，用位操作次數來衡量數論算法的時間性能。

1）初等數論概念

關于整數集合Z={…,-2,-1,0,1,2,…}和自然數集合N={0,1,2,…}的初等數論概念。

第一：整數性和約數

一個整數能被另一個整數整除，記號為d|a（d整除a），意味著對某個整數k，有a=kd。如果d|a且d≥0，則說d是a的約數。

對每個整數a來說，1和a是其平凡約數，而a的非平凡約數稱為a的因子。

第二：素數和合數

對于某個整數a＞1，如果它僅有平凡約數1和a，則稱a為素數或質數，素數有無窮多個。

不是素數的整數a＞1稱為合數。當然整數0和所有負整數既不是素數也不是合數。

第三：余數和模

對任意整數a和任意正整數n，存在唯一的整數q和r，滿足0≤r＜n，并且a=qn+r；其中q就是除法的商，r就是除法的余數。r=a mod n。

第四：公約數和最大公約數

如果d是a的約數并且也是b的約數，則d是a和b的公約數。兩個不同時為0的整數a和b的最大公約數表示為gcd(a,b)。對任意整數x和y，有：

d|a并且d|b蘊含著d|(ax+by)

如果a和b是都不為0的任意整數，則gcd(a,b)是a與b的線性組合集合{ax+by:x,y∈Z}中的最小正元素。

對任意整數a和b，如果d|a并且d|b，則d|gcd(a,b)。

對所有整數a和b以及任意非負整數n，gcd(an,bn)=ngcd(a,b)。

對所有正整數n,a和b，如果n|ab并且gcd(a,n)=1，則n|b。

第五：互質數

如果兩個整數a和b僅有公因數1，即如果gcd(a,b)=1，則a和b稱為互質數。

對任意整數a,b和p，如果gcd(a,p)=1且gcd(b,p)=1，則gcd(ab,p)=1。

第六：唯一因子分解

這是素數整除性的一個重要基礎。

對所有素數p和所有整數a,b，如果p|ab，則p|a或p|b或者都成立。由此可得唯一質因子分解定理。

合數a僅能以一種方式，寫成如下的乘積形式：

其中p_i為素數，p₁<p₂<…<p_r，且e_i為正整數。

如數6000可以唯一分解為2⁴*3*5³

2）最大公約數

計算兩個整數的最大公約數是數論的基礎算法，運用歐幾里得算法可有效計算，其運行時間和斐波那契數存在聯系。

一般情況下，最大公約數的求解，可以通過素數因子分解來完成。假設正整數a和b的最大公約數gcd(a,b)：

如果r項不足則使用零指數，使素數結合p₁,p₂,…,p_r對于a和b是相同的，容易得出：

然而素數分解因子的算法是在多項式時間內無法完成的。因此需要通過歐幾里得算法來有效求解。

歐幾理得求解最大公約數的算法，基于GCD的一個遞歸原理：對任意非負整數a和任意正整數b，有

gcd(a,b)=gcd(b,amod b)

通過遞歸程序來實現歐幾理得的算法（約公元前300年的幾何原本中描述的）：

Func_Euclid(a,b){

??? if b=0

??????? then return a

??? else return Func_Euclid(b,a mod b)

}

歐幾里得算法的運行時間和斐波那契數有關聯。

如果a＞b≥1并且Func_Euclid(a,b)執行了k≥1次遞歸調用，則a≥F_k+2，b≥F_k+1。

對任意整數k≥1，如果a＞b≥1并且b＜F_k+1，則Func_Euclid(a,b)遞歸調用次數少于k次。

推廣歐幾理得算法，求解下列方程式的x和y：

d=gcd(a,b)=ax+by

先看函數：

Func_Extend_Euclid(a,b){

??? if b=0

??????? then return ( a,1,0)

??? (d’,x’,y’)= Func_Extend_Euclid(b,a mod b)

??? (d,x,y)=(d’,y’,x’-(a/b)y’)

??? return?(d,x,y)

}

其中y= x’-(a/b)y’是擴展算法的關鍵，遞歸到最底層時，x=1，y=0，是基礎解。

歐幾理得算法及其推廣形式中很重要的是a mod b的模運算。

總結

以上是生活随笔為你收集整理的算法导论之有关数论的算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。