Функция Кармайкла

Функция Кармайкла (также известная как функция Кармайкла или функция λ) — это теоретико-числовая функция, определённая для натурального числа n, равная наименьшему положительному целому m такому, что для всех целых a, взаимно простых с n, выполняется сравнение a^m ≡ 1 (mod n). Функция названа в честь американского математика Роберта Кармайкла, который впервые ввёл её в 1910 году. Она является обобщением функции Эйлера φ(n) и играет важную роль в теории чисел, криптографии и алгоритмической теории групп.

Определение

Для натурального числа n функция Кармайкла λ(n) определяется как наименьшее положительное целое число m, удовлетворяющее условию:

a^m ≡ 1 (mod n) для всех a, таких, что gcd(a, n) = 1.

Иными словами, λ(n) — это экспонента мультипликативной группы обратимых элементов кольца вычетов по модулю n, обозначаемой (ℤ/nℤ)^×. Группа (ℤ/nℤ)^× состоит из всех классов вычетов a mod n, для которых a и n взаимно просты. λ(n) — это наименьшее общее кратное порядков всех элементов этой группы.

Свойства

Связь с функцией Эйлера

Функция Эйлера φ(n) равна порядку группы (ℤ/nℤ)^×, то есть количеству чисел от 1 до n, взаимно простых с n. Функция Кармайкла λ(n) всегда делит φ(n). Для некоторых n (например, для степеней двойки, кроме 2, и для простых чисел) λ(n) = φ(n), но в общем случае λ(n) может быть строго меньше φ(n). Например, для n = 8: φ(8) = 4, но λ(8) = 2, так как 1^2 ≡ 1, 3^2 ≡ 9 ≡ 1, 5^2 ≡ 25 ≡ 1, 7^2 ≡ 49 ≡ 1 (mod 8).

Мультипликативность

Функция Кармайкла мультипликативна в следующем смысле: для взаимно простых чисел m и n выполняется λ(mn) = НОК(λ(m), λ(n)). Это свойство позволяет вычислять λ(n) на основе разложения n на простые множители.

Значения для простых степеней

Для простого числа p и натурального k ≥ 1:

• λ(p^k) = φ(p^k) = p^(k-1)(p-1) для нечётных p.
• Для p = 2: λ(2) = 1, λ(4) = 2, а для k ≥ 3: λ(2^k) = 2^(k-2).

Сравнение с теоремой Эйлера

Теорема Эйлера утверждает, что для любого a, взаимно простого с n, выполняется a^φ(n) ≡ 1 (mod n). Функция Кармайкла даёт наименьший показатель, для которого это верно для всех a одновременно. Таким образом, λ(n) ≤ φ(n), и равенство достигается тогда и только тогда, когда группа (ℤ/nℤ)^× является циклической.

Вычисление

Для вычисления λ(n) необходимо разложить n на простые множители: n = ∏ p_i^k_i. Тогда:

λ(n) = НОК(λ(p_1^k_1), λ(p_2^k_2), …, λ(p_r^k_r)),

где для каждого сомножителя:

• Если p_i нечётное, то λ(p_i^k_i) = p_i^(k_i-1)(p_i-1).
• Если p_i = 2, то:
• λ(2) = 1,
• λ(4) = 2,
• λ(2^k) = 2^(k-2) для k ≥ 3.

Примеры

1. n = 15 = 3·5. λ(3) = φ(3) = 2, λ(5) = φ(5) = 4. НОК(2, 4) = 4. Таким образом, λ(15) = 4. Проверка: для a=2 (gcd(2,15)=1): 2^4=16≡1 (mod 15); для a=7: 7^4=2401≡1 (mod 15).

1. n = 24 = 2^3·3. λ(8) = 2^(3-2) = 2, λ(3) = 2. НОК(2, 2) = 2. λ(24) = 2. Действительно, для любого нечётного числа a, не кратного 3, a^2 ≡ 1 (mod 24).

1. n = 100 = 2^2·5^2. λ(4) = 2, λ(25) = φ(25) = 20. НОК(2, 20) = 20. λ(100) = 20.

История

Функция была впервые определена Робертом Кармайклом в 1910 году в статье «Note on a new number theory function» (American Mathematical Monthly, том 17, № 2, стр. 30–34). Кармайкл изучал свойства чисел, для которых выполняется сравнение a^m ≡ 1 (mod n) для всех a, взаимно простых с n. Он показал, что минимальное такое m является делителем функции Эйлера, и предложил метод его вычисления через наименьшее общее кратное. В 1912 году он опубликовал более полное исследование, где ввёл термин «функция λ» и доказал её мультипликативность.

Применение

Криптография

Функция Кармайкла используется в криптосистеме RSA. В RSA модуль n = pq, где p и q — большие простые числа. Порядок группы (ℤ/nℤ)^× равен φ(n) = (p-1)(q-1). Однако для шифрования и дешифрования можно использовать λ(n) = НОК(p-1, q-1), так как для любого сообщения m, взаимно простого с n, выполняется m^λ(n) ≡ 1 (mod n). Это позволяет выбирать экспоненты e и d, удовлетворяющие условию ed ≡ 1 (mod λ(n)), что часто даёт меньшие значения d, ускоряя дешифрование. В современных реализациях RSA часто используют λ(n) вместо φ(n) для вычисления секретного ключа.

Теория чисел

Функция Кармайкла применяется при изучении циклических групп, первообразных корней и мультипликативных порядков. Она также используется в тестах на простоту, таких как тест Миллера — Рабина, где λ(n) помогает оценить количество свидетелей простоты.

Алгоритмические задачи

В задачах, связанных с вычислением дискретных логарифмов и решением сравнений, знание λ(n) позволяет определить максимальный порядок элемента группы, что важно для оптимизации алгоритмов.

Интересные факты

• Числа, для которых λ(n) = φ(n), называются «числами Кармайкла» в узком смысле, но обычно термин «число Кармайкла» относится к составным числам, удовлетворяющим условию a^n ≡ a (mod n) для всех a (псевдопростые числа по Ферма). Это разные понятия.
• Для n = 1 функция Кармайкла не определена в классическом смысле, но иногда полагают λ(1) = 1, так как группа (ℤ/1ℤ)^× тривиальна.
• Значение λ(n) для n, являющегося произведением двух различных простых чисел, равно НОК(p-1, q-1), что может быть значительно меньше φ(n) = (p-1)(q-1).

Критика и ограничения

Функция Кармайкла не является мультипликативной в полном смысле (для непростых степеней она не равна произведению значений), что усложняет её вычисление для больших n. Кроме того, в отличие от функции Эйлера, для λ(n) не существует простой формулы, выражающей её через сумму или произведение делителей. В криптографии использование λ(n) вместо φ(n) требует осторожности, так как при неправильном выборе параметров может снизиться стойкость системы.

Источники

• Carmichael, R. D. (1910). «Note on a new number theory function». American Mathematical Monthly, 17(2), 30–34.
• Carmichael, R. D. (1912). «On the theory of numbers». Bulletin of the American Mathematical Society, 18(5), 232–240.
• Hardy, G. H., & Wright, E. M. (2008). «An Introduction to the Theory of Numbers» (6th ed.). Oxford University Press.
• Koblitz, N. (1994). «A Course in Number Theory and Cryptography» (2nd ed.). Springer-Verlag.
• Rivest, R. L., Shamir, A., & Adleman, L. (1978). «A method for obtaining digital signatures and public-key cryptosystems». Communications of the ACM, 21(2), 120–126.