整数和基础
整数
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)。模算术
欧拉函数
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 和 a 不能被 p 整除，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，离散对数问题要求找到一个指数 x，使得 g^x=h。
使用场景
将其用于理解 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。