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

Кармайкл λ функция: λ(п) за 1 ≤ п ≤ 1000 (по сравнению с Эйлером φ функция)

В теория чисел, филиал математика, то Функция Кармайкла соратники для каждого положительное число п положительное целое число λ(п), определяемый как наименьшее положительное целое число м такой, что

а^м ≡ 1   (мод п)

для каждого целого числа а от 1 до п то есть совмещать к п. В алгебраических терминах λ(п) это показатель степени из мультипликативная группа целых чисел по модулю п.

Функция Кармайкла названа в честь американского математика. Роберт Кармайкл и также известен как пониженная тотальная функция или функция наименьшего универсального показателя.

В следующей таблице сравниваются первые 36 значений λ(п) (последовательность A002322 в OEIS) с Функция Эйлера φ (в смелый если они разные; в птакие, что они разные, перечислены в OEIS: A033949).

Числовой пример

Функция Кармайкла в 8 равна 2, λ(8) = 2, потому что для любого числа а взаимно просто с 8, то а² ≡ 1 (мод. 8). А именно, 1² = 1 (мод. 8), 3² = 9 ≡ 1 (мод. 8), 5² = 25 ≡ 1 (мод. 8) и 7² = 49 ≡ 1 (мод. 8). Эйлера общая функция в 8 - 4, φ(8) = 4, потому что на 4 числа меньше и взаимно просто с 8 (1, 3, 5 и 7). Теорема Эйлера уверяет, что а⁴ ≡ 1 (мод. 8) для всех а взаимно просто с 8, но 4 не наименьший такой показатель.

Вычисление λ(п) с теоремой Кармайкла

Посредством уникальная теорема факторизации, любой п > 1 уникальным образом можно записать как

${ displaystyle n = p_ {1} ^ {r_ {1}} p_ {2} ^ {r_ {2}} cdots p_ {k} ^ {r_ {k}}}$

куда п₁ < п₂ < ... < п_k находятся простые числа и р₁, р₂, ..., р_k положительные целые числа. потом λ(п) это наименьший общий множитель из λ каждого из основных факторов мощности:

${ displaystyle lambda (n) = operatorname {lcm} left ( lambda left (p_ {1} ^ {r_ {1}} right), lambda left (p_ {2} ^ {r_ { 2}} right), ldots, lambda left (p_ {k} ^ {r_ {k}} right) right).}$

Это можно доказать с помощью Китайская теорема об остатках.

Теорема Кармайкла объясняет, как вычислить λ главной власти п^р: для степени нечетного простого числа и для 2 и 4, λ(п^р) равно Эйлер тотиент φ(п^р); для степеней 2 больше 4 он равен половине суммы Эйлера:

${ displaystyle lambda (p ^ {r}) = { begin {case} varphi left (p ^ {r} right) & { mbox {if}} p ^ {r} = 2,3 ^ {r}, 4,5 ^ {r}, 7 ^ {r}, 11 ^ {r}, 13 ^ {r}, 17 ^ {r}, 19 ^ {r}, 23 ^ {r}, 29 ^ {r}, 31 ^ {r}, dots { tfrac {1} {2}} varphi left (p ^ {r} right) & { text {if}} p ^ {r} = 8,16,32,64,128,256, dots end {case}}}$

Функция Эйлера для простых степеней п^р дан кем-то

${ displaystyle varphi (p ^ {r}) = p ^ {r-1} (p-1).}$

Свойства функции Кармайкла

Порядок элементов по модулю п

Позволять а и п быть совмещать и разреши м быть наименьшим показателем с а^м ≡ 1 (мод п), то выполняется

${ Displaystyle м , | , лямбда (п)}$.

Это порядок m: = ord_п(а) из единица измерения а в кольце целых чисел по модулю п разделяет λ(п) и

${ Displaystyle лямбда (п) = макс { OperatorName {ord} _ {п} (а) , двоеточие , НОД (а, п) = 1 }}$

Минимальность

Предполагать а^м ≡ 1 (мод п) для всех номеров а совмещать с п. потом λ(п) | м.

Доказательство: Если м = kλ(п) + р с 0 ≤ р < λ(п), тогда

${ displaystyle a ^ {r} = 1 ^ {k} cdot a ^ {r} Equiv left (a ^ { lambda (n)} right) ^ {k} cdot a ^ {r} = а ^ {к лямбда (п) + г} = а ^ {м} эквив 1 { pmod {п}}}$

для всех номеров а совмещать с п. Следует р = 0, поскольку р < λ(п) и λ(п) минимальное положительное такое число.

Расширение степеней двойки

За а взаимно просто с (степенями) 2 имеем а = 1 + 2час для некоторых час. Потом,

${ displaystyle a ^ {2} = 1 + 4h (h + 1) = 1 + 8C}$

где мы используем тот факт, что C := (час + 1)час/2 целое число.

Таким образом, для k = 3, час целое число:

${ displaystyle { begin {align} a ^ {2 ^ {k-2}} & = 1 + 2 ^ {k} h a ^ {2 ^ {k-1}} & = left (1+ 2 ^ {k} h right) ^ {2} = 1 + 2 ^ {k + 1} left (h + 2 ^ {k-1} h ^ {2} right) end {align}}}$

По индукции, когда k ≥ 3, у нас есть

${ Displaystyle a ^ {2 ^ {k-2}} Equiv 1 { pmod {2 ^ {k}}}.}$

Он предусматривает, что λ(2^k) самое большее 2^{k − 2}.^[1]

λ(п) разделяет φ(п)

Это следует из элементарного теория групп, потому что показатель любой конечная группа должен разделить порядок группы. λ(п) - показатель мультипликативной группы целых чисел по модулю п пока φ(п) порядок этой группы.

Таким образом, мы можем рассматривать теорему Кармайкла как уточнение Теорема Эйлера.

Делимость

${ Displaystyle а , | , b Rightarrow lambda (a) , | , lambda (b)}$

Доказательство. Результат следует из формулы

${ displaystyle lambda (n) = operatorname {lcm} left ( lambda left (p_ {1} ^ {r_ {1}} right), lambda left (p_ {2} ^ {r_ { 2}} right), ldots, lambda left (p_ {k} ^ {r_ {k}} right) right)}$

упомянутый выше.

Сочинение

Для всех положительных целых чисел а и б он считает, что

${ displaystyle lambda ( mathrm {lcm} (a, b)) = mathrm {lcm} ( lambda (a), lambda (b))}$.

Это непосредственное следствие рекурсивного определения функции Кармайкла.

Экспоненциальная длина цикла

Если п имеет максимальный простой показатель р_{Максимум} при простой факторизации, то для всех а (в том числе непростые п) и все р ≥ р_{Максимум},

${ displaystyle a ^ {r} Equiv a ^ {r + lambda (n)} { pmod {n}}.}$

В частности, для без квадратов п (р_{Максимум} = 1), для всех а у нас есть

${ Displaystyle a Equiv a ^ { lambda (n) +1} { pmod {n}}.}$

Средняя стоимость

Для любого п ≥ 16:^[2][3]

${ displaystyle { frac {1} {n}} sum _ {i leq n} lambda (i) = { frac {n} { ln n}} e ^ {B (1 + o (1 )) ln ln n / ( ln ln ln n)}}$

(далее называемое приближением Эрдеша) с постоянной

${ displaystyle B: = e ^ {- gamma} prod _ {p in mathbb {P}} left ({1 - { frac {1} {(p-1) ^ {2} (p +1)}}} right) приблизительно 0,34537}$

и γ ≈ 0.57721, то Константа Эйлера – Маскерони.

В следующей таблице дается краткий обзор первого 2²⁶ – 1 = 67108863 ценности λ как для точного среднего, так и для его аппроксимации Эрдеша.

Кроме того, дается краткий обзор более легкодоступных Значения «логарифм над логарифмом» Ржунимагу(п) := пер λ(п)/пер п с

• Ржунимагу(п) > 4/5 ⇔ λ(п) > п^4/5.

Там запись таблицы в строке номер 26 в столбце

• % LoL> 4/5   → 60.49

указывает, что 60,49% (≈ 40000000) целых чисел 1 ≤ п ≤ 67108863 имеют λ(п) > п^4/5 это означает, что большинство λ значения экспоненциально по длине л : = журнал₂(п) ввода п, а именно

${ displaystyle left (2 ^ { frac {4} {5}} right) ^ {l} = 2 ^ { frac {4l} {5}} = left (2 ^ {l} right) ^ { frac {4} {5}} = n ^ { frac {4} {5}}.}$

ν	п = 2ν – 1	сумма ${ Displaystyle сумма _ {я Leq п} лямбда (я)}$	средний ${ Displaystyle { tfrac {1} {п}} сумма _ {я leq п} лямбда (я)}$	В среднем по Эрдешу	Эрдёш / точное среднее	Ржунимагу средний	% Ржунимагу > 4/5	% Ржунимагу > 7/8
5	31	270	8.709677	68.643	7.8813	0.678244	41.94	35.48
6	63	964	15.301587	61.414	4.0136	0.699891	38.10	30.16
7	127	3574	28.141732	86.605	3.0774	0.717291	38.58	27.56
8	255	12994	50.956863	138.190	2.7119	0.730331	38.82	23.53
9	511	48032	93.996086	233.149	2.4804	0.740498	40.90	25.05
10	1023	178816	174.795699	406.145	2.3235	0.748482	41.45	26.98
11	2047	662952	323.865169	722.526	2.2309	0.754886	42.84	27.70
12	4095	2490948	608.290110	1304.810	2.1450	0.761027	43.74	28.11
13	8191	9382764	1145.496765	2383.263	2.0806	0.766571	44.33	28.60
14	16383	35504586	2167.160227	4392.129	2.0267	0.771695	46.10	29.52
15	32767	134736824	4111.967040	8153.054	1.9828	0.776437	47.21	29.15
16	65535	513758796	7839.456718	15225.430	1.9422	0.781064	49.13	28.17
17	131071	1964413592	14987.400660	28576.970	1.9067	0.785401	50.43	29.55
18	262143	7529218208	28721.797680	53869.760	1.8756	0.789561	51.17	30.67
19	524287	28935644342	55190.466940	101930.900	1.8469	0.793536	52.62	31.45
20	1048575	111393101150	106232.840900	193507.100	1.8215	0.797351	53.74	31.83
21	2097151	429685077652	204889.909000	368427.600	1.7982	0.801018	54.97	32.18
22	4194303	1660388309120	395867.515800	703289.400	1.7766	0.804543	56.24	33.65
23	8388607	6425917227352	766029.118700	1345633.000	1.7566	0.807936	57.19	34.32
24	16777215	24906872655990	1484565.386000	2580070.000	1.7379	0.811204	58.49	34.43
25	33554431	96666595865430	2880889.140000	4956372.000	1.7204	0.814351	59.52	35.76
26	67108863	375619048086576	5597160.066000	9537863.000	1.7041	0.817384	60.49	36.73

Преобладающий интервал

Для всех номеров N и все кроме о(N)^[4] положительные целые числа п ≤ N («преобладающее» большинство):

${ displaystyle lambda (n) = { frac {n} {( ln n) ^ { ln ln ln n + A + o (1)}}}}$

с постоянной^[3]

${ displaystyle A: = - 1+ sum _ {p in mathbb {P}} { frac { ln p} {(p-1) ^ {2}}} приблизительно 0,2269688}$

Нижние границы

Для любого достаточно большого числа N и для любого Δ ≥ (ln ln N)³, есть не более

${ Displaystyle N ехр влево (-0,69 ( Delta ln Delta) ^ { frac {1} {3}} right)}$

положительные целые числа п ≤ N такой, что λ(п) ≤ ne^−Δ.^[5]

Минимальный заказ

Для любой последовательности п₁ < п₂ < п₃ < ⋯ положительных целых чисел, любая константа 0 < c < 1/пер. 2, и любые достаточно большие я:^[6][7]

${ displaystyle lambda (n_ {i})> left ( ln n_ {i} right) ^ {c ln ln ln n_ {i}}.}$

Маленькие значения

Для постоянного c и любой достаточно большой положительный А, существует целое число п > А такой, что^[7]

${ displaystyle lambda (n) < left ( ln A right) ^ {c ln ln ln A}.}$

Более того, п имеет форму

${ Displaystyle п = mathop { prod _ {q in mathbb {P}}} _ {(q-1) | m} q}$

для некоторого целого числа без квадратов м <(ln А)^{c ln ln ln А}.^[6]

Изображение функции

Набор значений функции Кармайкла имеет счетную функцию^[8]

${ displaystyle { frac {x} {( ln x) ^ { eta + o (1)}}},}$

куда

${ displaystyle eta = 1 - { frac {1+ ln ln 2} { ln 2}} приблизительно 0,08607}$

Использование в криптографии

Функция Кармайкла важна в криптография из-за его использования в Алгоритм шифрования RSA.

Смотрите также

• Число Кармайкла

Примечания

Рекомендации

• Эрдеш, Пол; Померанс, Карл; Шмутц, Эрик (1991). "Лямбда-функция Кармайкла". Acta Arithmetica. 58 (4): 363–385. Дои:10.4064 / aa-58-4-363-385. ISSN 0065-1036. МИСТЕР 1121092. Zbl 0734.11047.
• Фридлендер, Джон Б.; Померанс, Карл; Шпарлинский, Игорь Э. (2001). «Период генератора энергии и малые значения функции Кармайкла». Математика вычислений. 70 (236): 1591–1605, 1803–1806. Дои:10.1090 / s0025-5718-00-01282-5. ISSN 0025-5718. МИСТЕР 1836921. Zbl 1029.11043.
• Шандор, Йожеф; Crstici, Борислав (2004). Справочник по теории чисел II. Дордрехт: Kluwer Academic. С. 32–36, 193–195. ISBN 978-1-4020-2546-4. Zbl 1079.11001.
• Кармайкл, Р. Д. (2004-10-10). Теория чисел. Набу Пресс. ISBN 978-1144400345.