Number Theory Algorithms

對非常大的數字執行數論算法和算術運算

計算機:

兩個大整數相加

兩個大整數相減

兩個大整數相乘

兩個大整數相除

一個大整數的冪

一個大整數的根

兩個大整數的最大公約數 (GCD)

兩個大整數的最小公倍數 (LCM)

兩個大整數的模

兩個大整數的模逆

模冪

判斷一個大整數是否為質數

歐拉函數

階乘

一個大整數的下一個質數

一個大整數的下一個孿生素數對

演算法:

簡單二次型。求解 x, y，使得 bxy+dx+ey=f，其中 b,d,e,f,x,y 位於 Z 中。

歐幾裡得演算法。計算兩個數 a 和 b 的最大公約數 (GCD)。

擴展歐幾裡得演算法。解 x, y，使得 ax + by = gcd(a, b)。

二元一次丟番圖方程式。求解 x,y，使得 ax+by=c。

一元一次全等式。求解 x，形式為 ax ≡ b (mod m) 的全等式。

二元一次全等式。解 x，y，形式為 ax+by ≡ c (mod m) 的全等式。

Tonelli-Shanks 演算法。計算模二次剩餘。求解 x，形式為 x² ≡ a (mod p) 的全等式，其中 p 為質數。

模因子。計算給定數字和模數的模因數。求 n ≡ bc (mod a)，其中 (ax + c)(ay + b) = a(axy + bx + cy) + bc = n。

素數列表。按列排序的素數列表。

注意：性能取決於設備。