Примитивный корень по модулю n

редактировать

В модульной арифметике, ветви теории чисел, число g является примитивным корнем по модулю n, если каждое число a , взаимно простое с n конгруэнтно степени g по модулю n. То есть g является примитивным корнем по модулю n, если для каждого целого числа, взаимно простого с n, существует целое число k такое, что g ≡ a (mod n). Такое значение k называется индексом или дискретным логарифмом числа a по основанию g по модулю n. Обратите внимание, что g является примитивным корнем по модулю n тогда и только тогда, когда g является генератором мультипликативной группы целых чисел по модулю n.

Гаусс, определенный в статье 57 Disquisitiones Arithmeticae (1801 г.), где он приписал Эйлеру создание этого термина. В статье 56 он заявил, что Ламберт и Эйлер знали о них, но он был первым, кто строго продемонстрировал, что примитивные корни существуют для простого n. Фактически, Disquisitiones содержит два доказательства: одно в статье 54 является неконструктивным доказательством существования, а другое в статье 55 является конструктивным.

Содержание

1 Элементарный пример
2 Определение
3 Примеры
- 3.1 Таблица первообразных корней
- 3.2 Арифметические факты
4 Поиск первообразных корней
5 Порядок величины первообразных корней
- 5.1 Верхние границы
- 5.2 Нижние границы
6 Приложения
7 См. Также
8 Примечания
9 Ссылки
10 Дополнительная литература
11 Внешние ссылки

Элементарный пример

Число 3 является примитивом корень по модулю 7, поскольку

3 1 = 3 = 3 0 × 3 ≡ 1 × 3 = 3 ≡ 3 (mod 7) 3 2 = 9 = 3 1 × 3 ≡ 3 × 3 = 9 ≡ 2 (mod 7) 3 3 = 27 = 3 2 × 3 ≡ 2 × 3 = 6 ≡ 6 (mod 7) 3 4 = 81 = 3 3 × 3 ≡ 6 × 3 = 18 ≡ 4 (mod 7) 3 5 = 243 = 3 4 × 3 ≡ 4 × 3 = 12 ≡ 5 (модуль 7) 3 6 = 729 = 3 5 × 3 ≡ 5 × 3 = 15 ≡ 1 (модуль 7) 3 7 = 2187 = 3 6 × 3 ≡ 1 × 3 = 3 ≡ 3 (мод 7) {\ displaystyle {\ begin {array} {rcrcrcrcrcr} 3 ^ {1} = 3 = 3 ^ {0} \ times 3 \ eq uiv 1 \ times 3 = 3 \ Equiv 3 {\ pmod {7}} \\ 3 ^ {2} = 9 = 3 ^ {1} \ times 3 \ Equiv 3 \ times 3 = 9 \ Equiv 2 {\ pmod {7}} \\ 3 ^ {3} = 27 = 3 ^ {2} \ times 3 \ Equiv 2 \ times 3 = 6 \ Equiv 6 {\ pmod {7}} \\ 3 ^ {4} = 81 = 3 ^ {3} \ times 3 \ Equiv 6 \ times 3 = 18 \ Equiv 4 {\ pmod {7}} \\ 3 ^ {5} = 243 = 3 ^ {4} \ times 3 \ Equiv 4 \ times 3 = 12 \ Equiv 5 {\ pmod {7}} \\ 3 ^ {6} = 729 = 3 ^ {5} \ times 3 \ Equiv 5 \ times 3 = 15 \ Equiv 1 {\ pmod {7 }} \\ 3 ^ {7} = 2187 = 3 ^ {6} \ times 3 \ Equiv 1 \ times 3 = 3 \ Equiv 3 {\ pmod {7}} \\\ end {array}}}

{\ displaystyle {\ begin {array} {rcrcrcrcrcr} 3 ^ {1} = 3 = 3 ^ {0} \ times 3 \ Equiv 1 \ times 3 = 3 \ Equiv 3 {\ pmod {7}} \\ 3 ^ {2} = 9 = 3 ^ {1} \ times 3 \ Equiv 3 \ times 3 = 9 \ Equiv 2 {\ pmod {7}} \ \ 3 ^ {3} = 27 = 3 ^ {2} \ times 3 \ Equiv 2 \ times 3 = 6 \ Equiv 6 {\ pmod {7}} \\ 3 ^ {4} = 81 = 3 ^ { 3} \ times 3 \ Equiv 6 \ times 3 = 18 \ Equiv 4 {\ pmod {7}} \\ 3 ^ {5} = 243 = 3 ^ {4} \ times 3 \ Equiv 4 \ times 3 = 12 \ Equiv 5 {\ pmod {7}} \\ 3 ^ {6} = 729 = 3 ^ {5} \ times 3 \ Equiv 5 \ times 3 = 15 \ Equiv 1 {\ pmod {7}} \\ 3 ^ {7} = 2187 = 3 ^ {6} \ ti mes 3 \ Equiv 1 \ times 3 = 3 \ Equiv 3 {\ pmod {7}} \\\ end {array}}}

Здесь мы видим, что период числа 3 по модулю 7 равен 6. Остатки в периоде, равные 3, 2, 6, 4, 5, 1, образуют перестановку всех ненулевых остатков по модулю 7, подразумевая, что 3 действительно является примитивным корнем по модулю 7. Это происходит из того факта, что последовательность (g по модулю n) всегда повторяется после некоторого значения k, поскольку по модулю n получается конечное число значений. Если g - примитивный корень по модулю n, а n - простое число, то период повторения равен n − 1. Любопытно, что созданные таким образом перестановки (и их круговые сдвиги) оказались массивами Костаса.

Определение

Если n - положительное целое число, целые числа от 0 до n - 1, которые взаимно простые с n (или эквивалентно, классы конгруэнтности взаимно простые с n) образуют группу с умножением по модулю n в качестве операции; она обозначается Z. n и называется группой единиц по модулю n или группой примитивных классов по модулю n. Как объясняется в статье мультипликативная группа целых чисел по модулю n, эта мультипликативная группа (Z. n) является циклической тогда и только тогда, когда n равно 2, 4, p или 2p, где p - степень нечетного простого числа. Когда (и только когда) эта группа Z. nявляется циклической, генератор этой циклической группы называется примитивным корнем по модулю n (или на более полном языке примитивным корнем единицы по модулю n, подчеркивая ее роль как фундаментального решения корней из единицы полиномиальных уравнений X. - 1 в кольце Z. n), или просто примитивный элемент Z. n. Когда Z. nнециклический, таких примитивных элементов по модулю n не существует.

Для любого n (независимо от того, является ли Z. nциклическим или нет), порядок (т. Е. Количество элементов в) Z. nзадается функцией Эйлера φ ( n) (последовательность A000010 в OEIS ). И затем, теорема Эйлера говорит, что a 1 (mod n) для каждого взаимно простого с n; наименьшая степень числа a, которая сравнима с 1 по модулю n, называется мультипликативным порядком по модулю n. В частности, чтобы a было первообразным корнем по модулю n, φ (n) должна быть наименьшей степенью a, которая сравнима с 1 по модулю n.

Примеры

Например, если n = 14, то элементы Z. nявляются классами конгруэнтности {1, 3, 5, 9, 11, 13}; их φ (14) = 6. Вот таблица их мощностей по модулю 14:

xx, x, x,... (mod 14) 1: 1 3: 3, 9, 13, 11, 5, 1 5: 5, 11, 13, 9, 3, 1 9: 9, 11, 1 11: 11, 9, 1 13: 13, 1

Порядок 1 равен 1, порядок 3 и 5 равен 6, порядки 9 и 11 равны 3, а порядок 13 равен 2. Таким образом, 3 и 5 являются первообразными корнями по модулю 14.

Для второго примера пусть n = 15. Элементы Z. 15равны классы конгруэнции {1, 2, 4, 7, 8, 11, 13, 14}; их φ (15) = 8.

xx, x, x,... (mod 15) 1: 1 2: 2, 4, 8, 1 4: 4, 1 7: 7, 4, 13, 1 8: 8, 4, 2, 1 11: 11, 1 13: 13, 4, 7, 1 14: 14, 1

Поскольку нет числа, порядок которого равен 8, нет примитивных корней по модулю 15. В самом деле, λ (15) = 4, где λ - функция Кармайкла. (последовательность A002322 в OEIS )

Таблице примитивных корней

Числа, которые имеют примитивный корень:

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 98, 101, 103, 106, 107, 109, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 142, 146, 149,... (последовательность A033948 в OEIS )

Это таблица Гаусса примитивные корни из Disquisitiones. В отличие от большинства современных авторов, он не всегда выбирал наименьший примитивный корень. Вместо этого он выбрал 10, если это примитивный корень; если это не так, он выбрал тот корень, который дает 10 наименьший индекс, и, если их несколько, выберите наименьший из них. Это не только для облегчения ручных вычислений, но и используется в § VI, где исследуются периодические десятичные разложения рациональных чисел.

Строки таблицы помечены простые степени (кроме 2, 4 и 8) меньше 100; второй столбец - это примитивный корень по модулю этого числа. Столбцы помечены простыми числами меньше 100. Запись в строке p, столбец q - это индекс q по модулю p для данного корня.

Например, в строке 11, 2 задается как первообразный корень, а в столбце 5 запись равна 4. Это означает, что 2 = 16 ≡ 5 (mod 11).

Для индекса составного числа сложите индексы его простых множителей.

Например, в строке 11 индекс 6 представляет собой сумму индексов для 2 и 3: 2 = 512 ≡ 6 ( мод 11). Индекс 25 вдвое больше индекса 5: 2 = 256 ≡ 25 (мод 11). (Конечно, поскольку 25 ≡ 3 (mod 11), запись для 3 равна 8).

Таблица проста для нечетных простых степеней. Но степени числа 2 (16, 32 и 64) не имеют примитивных корней; вместо этого, степени 5 составляют половину нечетных чисел, меньших степени 2, а их отрицательные значения по модулю степени 2 составляют вторую половину. Все степени 5 равны 5 или 1 (mod 8); столбцы, озаглавленные числами 3 или 7 (mod 8), содержат индекс его отрицательного значения. (Последовательность A185189 и A185268 в OEIS )

Например, по модулю 32 индекс для 7 равен 2, а 5 = 25 ≡ −7 (mod 32), но запись для 17 - 4, и 5 = 625 ≡ 17 (mod 32).

Примитивные корни и индексы. (другие столбцы - это индексы целых чисел под соответствующими заголовками столбцов)
n	корень	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
n	root	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
3	2	1
5	2	1	3
7	3	2	1	5
9	2	1	*	5	4
11	2	1	8	4	7
13	6	5	8	9	7	11
16	5	*	3	1	2	1	3
17	10	10	11	7	9	13	12
19	10	17	5	2	12	6	13	8
23	10	8	20	15	21	3	12	17	5
25	2	1	7	*	5	16	19	13	18	11
27	2	1	*	5	16	13	8	15	12	11
29	10	11	27	18	20	23	2	7	15	24
31	17	12	13	20	4	29	23	1	22	21	27
32	5	*	3	1	2	5	7	4	7	6	3	0
37	5	11	34	1	28	6	13	5	25	21	15	27
41	6	26	15	22	39	3	31	33	9	36	7	28	32
43	28	39	17	5	7	6	40	16	29	20	25	32	35	18
47	10	30	18	17	38	27	3	42	29	39	43	5	24	25	37
49	10	2	13	41	*	16	9	31	35	32	24	7	38	27	36	23
53	26	25	9	31	38	46	28	42	41	39	6	45	22	33	30	8
59	10	25	32	34	44	45	28	14	22	27	4	7	41	2	13	53	28
61	10	47	42	14	23	45	20	49	22	39	25	13	33	18	41	40	51	17
64	5	*	3	1	10	5	15	12	7	14	11	8	9	14	13	12	5	1	3
67	12	29	9	39	7	61	23	8	26	20	22	43	44	19	63	64	3	54	5
71	62	58	18	14	33	43	27	7	38	5	4	13	30	55	44	17	59	29	37	11
73	5	8	6	1	33	55	59	21	62	46	35	11	64	4	51	31	53	5	58	50	44
79	29	50	71	34	19	70	74	9	10	52	1	76	23	21	47	55	7	17	75	54	33	4
81	11	25	*	35	22	1	38	15	12	5	7	14	24	29	10	13	45	53	4	20	33	48	52
83	50	3	52	81	24	72	67	4	59	16	36	32	60	38	49	69	13	20	34	53	17	43	47
89	30	72	87	18	7	4	65	82	53	31	29	57	77	67	59	34	10	45	19	32	26	68	46	27
97	10	86	2	11	53	82	83	19	27	79	47	26	41	71	44	60	14	65	32	51	25	20	42	91	18

В следующей таблице перечислены первообразные корни по модулю n для n ≤ 72:

$n {\ displaystyle n}$ $n$	примитивные корни по модулю $n {\ displaystyle n}$ $n$	порядок (OEIS : A000010 )	$n {\ displaystyle n}$ $n$	примитивные корни по модулю $n {\ displaystyle n}$ $n$	order (OEIS : A000010 )
1	0	1	37	2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35	36
2	1	1	38	3, 13, 15, 21, 29, 33	18
3	2	2	39		24
4	3	2	40		16
5	2, 3	4	41	6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35	40
6	5	2	42		12
7	3, 5	6	43	3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34	42
8		4	44		20
9	2, 5	6	45		24
10	3, 7	4	46	5, 7, 11, 15, 17, 19, 21, 33, 37, 43	22
11	2, 6, 7, 8	10	47	5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45	46
12		4	48		16
13	2, 6, 7, 11	12	49	3, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45, 47	42
14	3, 5	6	50	3, 13, 17, 23, 27, 33, 37, 47	20
15		8	51		32
16		8	52		24
17	3, 5, 6, 7, 10, 11, 12, 14	16	53	2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51	52
18	5, 11	6	54	5, 11, 23, 29, 41, 47	18
19	2, 3, 10, 13, 14, 15	18	55		40
20		8	56		24
21		12	57		36
22	7, 13, 17, 19	10	58	3, 11, 15, 19, 21, 27, 31, 37, 39, 43, 47, 55	28
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	59	2, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 56	58
24		8	60		16
25	2, 3, 8, 12, 13, 17, 22, 23	20	61	2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59	60
26	7, 11, 15, 19	12	62	3, 11, 13, 17, 21, 43, 53, 55	30
27	2, 5, 11, 14, 20, 23	18	63		36
28		12	64		32
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	65		48
30		8	66		20
31	3, 11, 12, 13, 17, 21, 22, 24	30	67	2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63	66
32		16	68		32
33		20	69		44
34	3, 5, 7, 11, 23, 27, 29, 31	16	70		24
35		24	71	7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69	70
36		12	72		24

Гипотеза Артина о первообразном корне s утверждает, что данное целое число a, которое не является ни полным квадратом, ни −1, является первообразным корнем по модулю бесконечного числа простых чисел.

Последовательность наименьших примитивных корней по модулю n ( не то же самое, что последовательность примитивных корней в таблице Гаусса)

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0,... (последовательность A046145 в OEIS )

Для простого n они равны

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2, 3, 7, 6, 2, 2,... (последовательность A001918 в OEIS )

Наибольшие примитивные корни по модулю n равны

0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0,... (последовательность A046146 в OEIS )

Для простого n они равны

1, 2, 3, 5, 8, 11, 14, 15, 21, 27, 24, 35, 35, 34, 45, 51, 56, 59, 63, 69, 68, 77, 80, 86, 92, 99, 101, 104, 103, 110, 118, 128, 134, 135, 147, 146, 152, 159, 165, 171, 176, 179, 189, 188, 195, 197, 207, 214, 224, 223,... (последовательность A071894 в OEIS )

Количество примитивных корней по модулю n равны

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0,... (последовательность A046144 в OEIS )

Для простого n это

1, 1, 2, 2, 4, 4, 8, 6, 10, 12, 8, 12, 16, 12, 22, 24, 28, 16, 20, 24, 24, 24, 40, 40, 32, 40, 32, 52, 36, 48, 36, 48, 64, 44, 72, 40, 48, 54, 82, 84, 88, 48, 72, 64, 84, 60, 48, 72, 112, 72, 112, 96, 64, 100, 128, 130, 132, 72, 88, 96,... (последовательность A008330 в OEIS )

Наименьшее простое число>n с примитивным корнем n равны

2, 3, 5, 0, 7, 11, 11, 11, 0, 17, 13, 17, 19, 17, 19, 0, 23, 29, 23, 23, 23, 31, 47, 31, 0, 29, 29, 41, 41, 41, 47, 37, 43, 41, 37, 0, 59, 47, 47, 47, 47, 59, 47, 47, 47, 67, 59, 53, 0, 53,... (последовательность A023049 в OEIS )

Наименьшее простое число (не обязательно превышающее n) с примитивным корнем n:

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2,... (последовательность A056619 в OEIS )

Арифметические факты

Гаусс доказал, что для любого простого числа p (за исключением p = 3) произведение его первообразных корней сравнимо с 1 по модулю p.

Он также доказал, что для любого простого числа p сумма его примитивных корней сравнима с μ (p - 1) по модулю p, где μ - это функция Мёбиуса.

Например,

p = 3, μ (2) = −1. Первообразный корень равен 2.

p = 5, μ (4) = 0. Первоначальные корни равны 2 и 3.

p = 7, μ (6) = 1. Примитивный корни равны 3 и 5.

p = 31, μ (30) = -1. Первоначальные корни - это 3, 11, 12, 13, 17, 21, 22 и 24.

Их произведение 970377408 1 (mod 31) и их сумма 123 ≡ −1 (mod 31).

3 × 11 = 33 ≡ 2

12 × 13 = 156 ≡ 1

(−14) × (−10) = 140 ≡ 16

(−9) × (−7) = 63 1 и 2 × 1 × 16 × 1 = 32 ≡ 1 (mod 31).

А как насчет сложения элементов этой мультипликативной группы? Как это бывает, суммы (или разности) двух примитивных корней складываются во все элементы подгруппы индекса 2 из Z / n Z для четного n и для всей группы Z / n Z, если n нечетное:

Z/ n Z+ Z/ n Z= Z/ n Z или 2 Z / n Z.

Поиск первообразных корней

Неизвестно простой общей формулы для вычисления первообразных корней по модулю n. Однако есть методы для поиска примитивного корня, которые быстрее, чем просто пробовать всех кандидатов. Если мультипликативный порядок числа m по модулю n равен $φ (n) {\ displaystyle \ varphi (n)}$ $\ varphi (n)$ (порядок Z. n), тогда это первобытный корень. На самом деле верно и обратное: если m - примитивный корень по модулю n, то порядок мультипликативности m равен $φ (n) {\ displaystyle \ varphi (n)}$ $\ varphi (n)$ . Мы можем использовать это, чтобы проверить кандидата m на примитивность.

Сначала вычислите $φ (n) {\ displaystyle \ varphi (n)}$ $\ varphi (n)$ . Затем определите различные простые множители из $φ (n) {\ displaystyle \ varphi (n)}$ $\ varphi (n)$ , скажем, p 1,..., р к. Наконец, вычислите

m φ (n) / pi mod n для i = 1,…, k {\ displaystyle m ^ {\ varphi (n) / p_ {i}} {\ bmod {n}} \ qquad { \ t_dv {for}} i = 1, \ ldots, k}

{\ displaystyle m ^ {\ varphi (n) / p_ {i }} {\ bmod {n}} \ qquad {\ t_dv {for}} i = 1, \ ldots, k}

с использованием быстрого алгоритма модульного возведения в степень, такого как возведения в степень возведением в квадрат. Число m, для которого все k результатов отличны от 1, является примитивным корнем.

Количество первообразных корней по модулю n, если они есть, равно

φ (φ (n)) {\ displaystyle \ varphi \ left (\ varphi (n) \ right)}

{\ displaystyle \ varphi \ left ( \ varphi (n) \ right)}

, поскольку, как правило, циклическая группа с r элементами имеет $φ (r) {\ displaystyle \ varphi (r)}$ $\ varphi (r)$ генераторы. Для простого n это равно $φ (n - 1) {\ displaystyle \ varphi (n-1)}$ ${\ displaystyle \ varphi (n -1)}$ , а поскольку $n / φ (n - 1) ∈ O (log ⁡ log ⁡ n) {\ displaystyle n / \ varphi (n-1) \ in O (\ log \ log n)}$ ${\ displaystyle n / \ varphi (n-1) \ in O (\ log \ log n)}$ генераторы очень распространены среди {2,…, n − 1} и таким образом, его относительно легко найти.

Если g - примитивный корень по модулю p, то g также является примитивным корнем по модулю всех степеней p, если g ≡ 1 (mod p); в этом случае g + p равно.

Если g является примитивным корнем по модулю p, то либо g, либо g + p (в зависимости от того, какой из них нечетный) является примитивным корнем по модулю 2p.

Нахождение первообразных корней по модулю p также эквивалентно поиску корней (p − 1) циклотомического многочлена по модулю p.

Порядок величины примитивных корней

Наименьший примитивный корень g p по модулю p (в диапазоне 1, 2,..., p - 1) обычно маленький.

Верхние границы

Берджесс (1962) доказал, что для любого ε>0 существует C такое, что $g p ≤ C p 1 4 + ϵ. {\ displaystyle g_ {p} \ leq Cp ^ {{\ frac {1} {4}} + \ epsilon}.}$ $g_p \ leq Cp ^ {\ frac {1} {4} + \ epsilon}.$

Гроссвальд (1981) доказал, что если $p>ee 24 {\ displaystyle p>e ^ {e ^ {24}}}$ $p>e ^ {e ^ {24}}$ , затем $gp < p 0.499 {\displaystyle g_{p}$ $g_p <p ^ {0.499}$ .

Carella (2015) доказал, что существует $C>0 {\ displaystyle C>0}$ $C>0$ такие что $gp ≤ C p 5 / log ⁡ log ⁡ p {\ displaystyle g_ {p} \ leq Cp ^ {5 / \ log \ log p}}$ ${\ displaystyle g_ {p} \ leq Cp ^ {5 / \ log \ log p}}$ для всех достаточно больших простых чисел $p>2 {\ displaystyle p>2}$ $p>2$ .

Шоуп (1990, 1992) доказал, допуская обобщенную гипотезу Римана, что g p = O (log p).

Lo Наши границы

Фридландер (1949) и Сали (1950) доказали, что существует положительная постоянная C такая, что для бесконечного числа простых чисел g p>C log p.

Элементарно можно доказать, что для любого положительного целого числа M существует бесконечно много простых чисел, таких что M < gp< p − M.

Приложения

В часто используется примитивный корень по модулю n криптография, включая схему обмена ключами Диффи – Хеллмана. Рассеиватели звука были основаны на теоретико-числовых концепциях, таких как примитивные корни и квадратичные вычеты.