Carmichael Function

Definition / 定义

Carmichael function（卡迈克尔函数）：在数论中记作 λ(n)，表示模 n 的乘法群的指数。等价地说，λ(n) 是使得对所有与 n 互素的整数 a 都满足
a^λ(n) ≡ 1 (mod n) 的最小正整数。
（它与欧拉函数 φ(n) 相关，但通常 **λ(n) ≤ φ(n)**，且更“精确”地刻画幂在模 n 下回到 1 的周期上界。）

Examples / 例句

The Carmichael function of 8 is 2.
8 的卡迈克尔函数是 2。

In RSA and other modular exponentiation settings, using the Carmichael function λ(n) can give a tighter exponent than Euler’s totient φ(n) for guaranteeing (a^{\lambda(n)} \equiv 1 \pmod n) when gcd(a, n) = 1.
在 RSA 等模幂运算场景中，使用卡迈克尔函数 λ(n) 往往能比欧拉函数 φ(n) 给出更“紧”的指数界，从而保证当 gcd(a, n)=1 时有 (a^{\lambda(n)} \equiv 1 \pmod n)。

Pronunciation / 发音

/ˈkɑːrmaɪkəl ˈfʌŋkʃən/

Etymology / 词源

该术语以美国数学家 Robert Daniel Carmichael（罗伯特·丹尼尔·卡迈克尔）命名。他在研究数论与同余性质时推动了相关概念的发展；函数记号 λ(n) 也常被称为“卡迈克尔的 λ 函数”，用于描述模 n 乘法结构中的“周期上界/指数”。

Related Words / 相关词

• Euler Totient Function
• Modular Arithmetic
• Congruence
• Multiplicative Order
• Exponent
• Carmichael Number
• Group
• Least Common Multiple
• RSA

Literary Works / 文学与著作例证

• G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers（《数论导引》）：在讲授同余、指数与相关函数时会涉及与 λ(n) 密切相关的思想与结果。
• Kenneth H. Rosen, Elementary Number Theory and Its Applications（《初等数论及其应用》）：常在讨论模 n 的乘法结构、阶与指数时引入/使用 λ(n)。
• D. R. Stinson, Cryptography: Theory and Practice（《密码学：理论与实践》）：在公开密钥密码与模幂运算背景下会提到与 λ(n) 相关的指数选择思想。
• Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography（《应用密码学手册》）：在 RSA 等章节中讨论与 φ(n)、λ(n) 相关的数论工具与安全实现细节。