整數和基礎
整數
Integer
符號
ℤ意思
一個可以是負數、零或正數的整數。
使用時機
使用整數來進行帶有方向、索引、差值和確切離散計算的計數。
計算範例
-4、0 和 27 都是整數。數學參考
數論術語和計算指南
搜索整數、素數、模算術、循環群生成元、二次剩餘數、丟番圖方程和 RSA，並使用公式和例題。
模 7 的生成元循環
3 的連續冪訪問每個非零剩餘數，然後返回 1。
模 7 的二次剩餘數
非零剩餘數的平方只產生 1、2 和 4。
55 個術語
整數和基礎
自然數
Natural number
符號
ℕ意思
一個計數數；是否包含零取決於所使用的約定。
使用時機
在使用自然數進行證明、規格或程序之前，先說明慣例。
注意
有些書籍將自然數定義為從 1 開始，因此請務必檢查慣例。
計算範例
This guide uses ℕ = {0, 1, 2, 3, ...}.整數和基礎
絕對值
Absolute value
符號
|a|意思
整數到零的非負距離，在數線上。
使用時機
將其用於表達幅度、距離、誤差和對稱界限。
計算範例
|-7| = 7 and |5 - 12| = 7.整數和基礎
奇偶性
Parity
符號
n mod 2意思
整數是偶數還是奇數的屬性。
使用時機
將奇偶性用於分支、交替模式、證明、校驗和位級邏輯。
計算範例
18 mod 2 = 0, so 18 is even.整數和基礎
除法算法
Division algorithm
符號
a = bq + r意思
對於整數 a 和正數 b，存在唯一的整數 q 和 r，其中 0 ≤ r < b。
使用時機
將其用作商數、餘數、歐幾里得演算法和模算術的基礎。
計算範例
29 = 6 × 4 + 5, so q = 4 and r = 5.可除性
除數
Divisor
符號
d | n意思
如果 n = dk，其中 k 是某個整數，則整數 d 是 n 的一個除數。
使用時機
使用除數來分析因子結構、公因子和確切可除性。
計算範例
6 | 42 because 42 = 6 × 7.可除性
倍數
Multiple
符號
n = dk意思
一個通過將整數乘以另一個整數而得到的數。
使用時機
將倍數用於排程、常見週期、循環系統和分母對齊。
計算範例
5 的倍數包括 0、5、10、15 和 20。可除性
可除性檢驗
Divisibility test
符號
n mod d = 0意思
一個規則，用於確定一個整數是否能整除另一個整數，而無需進行長除法。
使用時機
將其用於快速檢查、心算、輸入驗證以及教學位值結構。
計算範例
7,452 is divisible by 3 because 7 + 4 + 5 + 2 = 18.可除性
最大公約數
Greatest common divisor
符號
gcd(a, b)意思
兩個整數的最大公約數。
使用時機
將其用於簡化分數、測試互素性、求解同餘方程和計算比例。
計算範例
gcd(84, 30) = 6.可除性
最小公倍數
Least common multiple
符號
lcm(a, b)意思
兩個非零整數的最小公倍數。
使用時機
將其用於同步週期、組合分數和計算重複排程。
計算範例
lcm(12, 18) = 36.可除性
GCD-LCM 恆等式
GCD-LCM identity
符號
gcd(a,b)lcm(a,b)=|ab|意思
一個連接兩個非零整數的最大公約數和最小公倍數的關係。
使用時機
將其用於在已知另一數量的情況下，高效地計算一個數量。
計算範例
gcd(12,18)=6, so lcm(12,18)=|12×18|/6=36.可除性
歐幾里得算法
Euclidean algorithm
符號
gcd(a,b)=gcd(b,a mod b)意思
一個用於尋找最大公約數的重複餘數算法。
使用時機
將其用於快速 GCD 計算，即使輸入整數很大。
計算範例
gcd(252,105) = gcd(105,42) = gcd(42,21) = 21.可除性
擴展歐幾里得算法
Extended Euclidean algorithm
符號
ax + by = gcd(a,b)意思
一個歐幾里得算法的擴展，它還找到貝祖係數 x 和 y。
使用時機
將其用於計算模逆元和求解線性丟番圖方程。
計算範例
35×(-1) + 12×3 = 1，因此 -1 是 35 的係數。可除性
互質整數
Coprime integers
符號
gcd(a,b)=1意思
如果兩個整數的最大公約數為 1，則它們是互質的。
使用時機
使用互質性來確定模 n 的可逆性以及應用歐拉定理。
計算範例
8 和 15 是互質的，即使這兩個數字都不是質數。素數與分解
素數
Prime number
符號
p意思
一個大於 1 且其唯一的正除數是 1 和自身的整數。
使用時機
將素數作為整數分解和公鑰密碼學的基本構建塊。
計算範例
2、3、5、7 和 11 都是質數。素數與分解
合數
Composite number
符號
n = ab意思
一個大於 1 且具有除 1 和自身之外的正除數的整數。
使用時機
將其用於區分可分解整數和素數。
計算範例
21 is composite because 21 = 3 × 7.素數與分解
素數分解
Prime factorization
符號
n=∏pᵢ^aᵢ意思
將整數寫成素數冪的乘積。
使用時機
將其用於計算除數、GCD、LCM 和算術函數。
計算範例
360 = 2^3 × 3^2 × 5.素數與分解
算術基本定理
Fundamental theorem of arithmetic
符號
n=∏pᵢ^aᵢ意思
任何大於 1 的整數都有一個唯一的素因子分解，僅因子順序不同。
使用時機
將其用於證明基於素數指數的演算法和證明。
計算範例
72 = 2^3 × 3^2 是 72 的唯一質數分解。素數與分解
埃拉托斯特尼篩法
Sieve of Eratosthenes
意思
一個通過重複標記每個發現的質數的倍數來列出小於某個極限的質數的算法。
使用時機
將其用於許多素數查詢共享相同的適中上限的情況。
計算範例
要找到 30 以內的素數，請標記 2、3 和 5 的倍數。素數與分解
素性檢驗
Primality test
意思
一個判斷給定整數是否為質數的算法。
使用時機
將試除用於小輸入，以及使用 Miller-Rabin 等概率測試用於大輸入。
注意
一個可能質數測試，可能需要多輪或針對預期的整數範圍的確定性基數集。
計算範例
試除只需要到 √n 的候選除數。模算術
同餘
Congruence
符號
a ≡ b (mod n)意思
如果 n 除以它們的差，則兩個整數是同餘的。
使用時機
將其用於用等效餘數替換整數，以進行循環計算。
計算範例
29 ≡ 5 (mod 12)，因為 12 能整除 29 - 5。模算術
同餘類
Residue class
符號
[a]ₙ意思
所有與固定整數同餘的整數的集合，模 n。
使用時機
將其用於將模值視為等價類，而不是孤立的數字。
計算範例
[2]₅ = {..., -8, -3, 2, 7, 12, ...}.模算術
取模運算
Modulo operation
符號
a mod n意思
一個返回除以 n 之後的餘數的運算。
使用時機
將其用於包裝索引、時鐘、哈希桶和週期狀態。
計算範例
(23 + 5) mod 24 = 4.模算術
模算術
Modular arithmetic
符號
ℤ/nℤ意思
在具有餘數類的算術運算中，結果模 n 進行還原。
使用時機
將其用於密碼學、編碼理論、循環緩衝區和日曆計算。
計算範例
(17 × 19) mod 12 = 11.模算術
模反元素
Modular inverse
符號
a⁻¹ mod n意思
一個滿足 ax ≡ 1 (mod n) 的值 x；它存在當且僅當 gcd(a,n)=1 時。
使用時機
將其用於在模算術中進行除法、求解同餘方程和實現密碼學演算法。
注意
在進行模除法之前，請務必檢查除數是否與模數互質。
計算範例
3⁻¹ mod 7 = 5 because 3 × 5 ≡ 1 (mod 7).模算術
模指數
Modular exponentiation
符號
a^k mod n意思
在構建潛在的巨大完整冪之前，計算模 n 的冪。
使用時機
將重平方用於密碼學、素性測試和指數較大的問題。
計算範例
3^13 mod 7 = 3 using repeated squaring.模算術
線性同餘
Linear congruence
符號
ax ≡ b (mod n)意思
一個尋求滿足線性模方程的整數 x 的同餘關係。
使用時機
使用 GCD 条件和模逆元来确定和计算解。
計算範例
3x ≡ 4 (mod 7) 得到 x ≡ 6 (mod 7)。模算術
孫子定理
Chinese remainder theorem
符號
x ≡ aᵢ (mod nᵢ)意思
一個將相容同餘關係組合起來的定理，當模數兩兩互素時，給出模產品的唯一解。
使用時機
將其用於組合獨立的循環約束，並加速大整數計算。
計算範例
x ≡ 2 (mod 3), x ≡ 3 (mod 5) 得到 x ≡ 8 (mod 15)。模算術
歐拉的 totient 函數
Euler's totient function
符號
φ(n)意思
從 1 到 n 的整數中，與 n 互質的整數的數量。
使用時機
將其用於歐拉定理、RSA 密鑰計算和簡化餘數系統。
計算範例
φ(12) = 4，因為 1、5、7 和 11 與 12 互質。模算術
歐拉定理
Euler's theorem
符號
a^φ(n) ≡ 1 (mod n)意思
如果 a 和 n 互質，那麼 a 的 φ(n) 次方模 n 同餘於 1。
使用時機
將其用於減少指數、證明模恆等式以及解釋 RSA。
計算範例
gcd(3,10)=1 and φ(10)=4, so 3^4 ≡ 1 (mod 10).模算術
費馬小定理
Fermat's little theorem
符號
a^(p-1) ≡ 1 (mod p)意思
對於素數 p 和不能被 p 整除的 a，a 的 (p-1) 次方模 p 同餘於 1。
使用時機
將其用於模逆元（在素數模下）以及素性檢測。
注意
即使通過了費馬檢驗，也不能證明一個數是素數，因為存在偽素數。
計算範例
2^6 ≡ 1 (mod 7).循環群和生成元
群
Group
符號
(G, *)意思
一個集合，具有一個結合運算、一個單位元素，以及每個元素的逆元。
使用時機
使用群來描述算術結構，其中可以組合和反轉操作。
計算範例
整數在加法下形成一個群，其單位元為 0，對於任何整數 a，其逆元為 -a。循環群和生成元
阿貝爾群
Abelian group
符號
a*b=b*a意思
一個群，其運算滿足交換律。
使用時機
用於模加法、向量加法以及許多操作順序不重要的算術群。
計算範例
(ℤ/nℤ, +) 是一個阿貝爾群。循環群和生成元
模 n 同餘的加法群
Additive group modulo n
符號
(ℤ/nℤ, +)意思
模 n 的餘數類，使用模 n 進行加法。
使用時機
用於建模循環計數器、週期狀態和模加法的同餘類。
計算範例
In ℤ/5ℤ, 3+4=2.循環群和生成元
單位的乘法群
Multiplicative group of units
符號
(ℤ/nℤ)×意思
與 n 互質的餘數類，使用模 n 進行乘法。
使用時機
用於研究模反元素、原根、歐拉定理和公開密碼學。
計算範例
(ℤ/8ℤ)×={1,3,5,7}.循環群和生成元
循環群
Cyclic group
符號
G=⟨g⟩意思
一個群，其每個元素都是一個元素的冪或重複和。
使用時機
用於將群操作簡化為指數或整數倍上的算術。
計算範例
加法群 ℤ/6ℤ 由 1 和 5 生成。循環群和生成元
生成元
Generator
符號
⟨g⟩=G意思
一個通過重複群運算產生循環群中所有元素的元素。
使用時機
用於枚舉循環群並定義基於指數的密碼學操作。
注意
始終說明群和運算，因為一個元素可以生成一種結構，但不能生成另一種結構。
計算範例
3 的冪模 7 產生 3,2,6,4,5,1，因此 3 生成 (ℤ/7ℤ)×。循環群和生成元
元素的階
Order of an element
符號
ord(g)意思
最小的正整數 k，使得 g^k 是單位元。
使用時機
用於測試元素是否為生成元以及確定循環長度。
計算範例
模 7，ord(2)=3，因為 2^3≡1，且沒有更小的正指數有效。循環群和生成元
原根
Primitive root
符號
ordₙ(g)=φ(n)意思
模 n 同餘群的乘法群的生成元。
使用時機
使用原根來表示非零餘數，並將其表示為冪，以及來構建離散對數。
計算範例
3 模 7 同餘的本原根，因為它的階數是 φ(7)=6。循環群和生成元
原根的存在
Primitive root existence
意思
原根在 n=1, 2, 4, p^k 或 2p^k 時存在，其中 p 是奇素數。
使用時機
在搜尋模一個合數的原根之前，請使用該判據。
計算範例
因為 8 沒有任何所需的形式，所以模 8 沒有原根。循環群和生成元
離散對數
Discrete logarithm
符號
g^x=h意思
給定一個生成元 g 和群元素 h，離散對數問題尋找滿足 g^x=h 的指數 x。
使用時機
用於理解 Diffie-Hellman、ElGamal 和橢圓曲線的安全性假設。
注意
離散對數在小群或選擇不佳的群中可能很容易計算，但在適當的參數下才難以計算。
計算範例
模 7，生成元為 3，log₃(5)=5，因為 3^5≡5。循環群和生成元
卡邁爾函數
Carmichael function
符號
λ(n)意思
最小的正指數 m，使得 a^m ≡ 1 (mod n)，對於所有與 n 互質的 a 成立。
使用時機
用於獲得比 φ(n) 更嚴密的通用指數，用於模冪和 RSA 分析。
計算範例
λ(8)=2，因為每個奇數 a 都滿足 a²≡1 (mod 8)。二次剩餘數
二次剩餘數
Quadratic residue
符號
x²≡a (mod n)意思
一個剩餘數 a，使得同餘方程 x²≡a 模 n 有解。
使用時機
用於分析模平方根、質數測試和二次剩餘密碼學。
計算範例
2 模 7 同餘的二次剩餘數，因為 3²≡2。二次剩餘數
二次非剩餘數
Quadratic nonresidue
意思
一個非零的剩餘數，使得 x²≡a 模 n 沒有解。
使用時機
用於分類餘數並構建具有已知二次特徵的測試或密碼學參數。
計算範例
3 模 7 同餘的二次非剩餘數。二次剩餘數
模平方根
Modular square root
符號
x=√a mod n意思
x²≡a 模 n 的解 x。
使用時機
用於點解壓縮、數論算法和基於餘數的密碼學。
計算範例
2 模 7 的平方根是 3 和 4。二次剩餘數
勒讓德符號
Legendre symbol
符號
(a/p)意思
對於一個奇素數 p，一個值 0、1 或 -1，表示是否可以被 p 整除或模 p 的二次剩餘狀態。
使用時機
用於測試二次特徵並簡潔地陳述歐拉判別法和二次互反律。
計算範例
(2/7)=1，因為 2 模 7 同餘的二次剩餘數。二次剩餘數
Jacobi 符號
Jacobi symbol
符號
(a/n)意思
一個勒讓德符號的乘法延拓，適用於正的奇數複合數的分母。
使用時機
用於高效的字元計算和不需要首先進行分解 n 的算法。
注意
Jacobi 符號為 1 並不能保證 a 是模複合數 n 的二次剩餘數。
計算範例
(5/21)=(5/3)(5/7)=1.二次剩餘數
歐拉判別法
Euler's criterion
符號
a^((p-1)/2)≡(a/p) (mod p)意思
一個判別準則，用於判斷奇素數模下的二次剩餘狀態，使用模指數。
使用時機
用於計算勒讓德符號，而無需列出每個平方數。
計算範例
對於 p=7，3^3≡-1 (mod 7)，因此 3 是二次非剩餘數。二次剩餘數
二次互反律
Quadratic reciprocity
符號
(p/q)(q/p)=(-1)^((p-1)(q-1)/4)意思
一個定理，描述了一個奇素數是否是另一個奇素數模下的二次剩餘數。
使用時機
用於將大型勒讓德符號計算簡化為較小的計算。
計算範例
因為 3 和 11 都是模 4 同餘的 3，所以 (3/11)=-(11/3)。二次剩餘數
輔助定律
Supplementary laws
符號
(-1/p), (2/p)意思
確定 -1 和 2 在一個奇素數模下的二次特徵的公式。
使用時機
與二次互反律結合使用，以完成勒讓德符號計算。
計算範例
當 p≡1 或 7 (mod 8) 時，(2/p)=1；當 p≡3 或 5 (mod 8) 時，(2/p)=-1。二次剩餘數
Tonelli-Shanks 算法
Tonelli-Shanks algorithm
意思
一個用於尋找奇素數模下二次剩餘數的模平方根的演算法。
使用時機
當模數為質數且簡單的 p≡3 模 4 的捷徑不適用時，請使用它。
計算範例
對於 p=13，Tonelli-Shanks 算法找到 x=6 或 7，使得 x²≡10 (mod 13)。二次剩餘數
複合數的平方根
Square roots modulo a composite
意思
模素數冪因子的平方根，並與中國剩餘定理結合。
使用時機
用於分析 Rabin 類型系統和具有複合模數的同餘式。
注意
對於一個由不同的奇素數組成的乘積，一個剩餘數可以有多個平方根，因此選擇所需的平方根需要額外的信息。
計算範例
解 x²≡1 模 3 和 5，然後組合模 15 的符號選擇。整數方程
丟番圖方程
Diophantine equation
意思
一個只尋求整數解的方程。
使用時機
使用可除性、GCD、同餘性和界限來確定是否存在整數解。
計算範例
3x + 5y = 17 has the integer solution x = 4, y = 1.整數方程
線性丟番圖方程
Linear Diophantine equation
符號
ax + by = c意思
一個未知數必須是整數的線性方程；當且僅當 gcd(a,b) 能整除 c 時，才存在解。
使用時機
將其用於精確分配、硬幣問題、排程和晶格約束。
計算範例
6x + 9y = 30 可以求解，因為 gcd(6,9)=3 能整除 30。應用
RSA 算術
RSA arithmetic
符號
c ≡ m^e (mod n)意思
基於模指數運算和分解大素數乘積困難度的公鑰算術。
使用時機
將其用於理解數論如何支持加密和數字簽名。
注意
示例值僅用於學習；真正的 RSA 需要標準填充、安全的鍵大小和經過審計的庫。
計算範例
使用示例值 n=55, e=3, 和 m=7，則 c=7^3 mod 55=13。