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

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

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

Элементарный пример [ править ]

Число 3 является примитивным корнем по модулю 7 ^[1], потому что

{\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}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\\end{array}}

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

Определение [ править ]

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

Для любого $n$ (независимо от того, $ℤ$ ^×
_$п$является циклическим), порядок (т.е. количество элементов в) $ℤ$ ^×
_$п$дается функцией Эйлера $φ$ ( $n$ ) (последовательность A000010 в OEIS ). И затем теорема Эйлера утверждает, что $a$ ^{$φ$ ( $n$ )} ≡ 1 (mod $n$ ) для любого $a,$ взаимно простого с $n$ ; самая низкая мощность , что сравнимо с 1 по модулю $п$ называется мультипликативный порядок из $более$ по модулю $п$ . В частности, чтобы $a$ было первообразным корнем по модулю $n$ , $φ$ ( $n$ ) должно быть наименьшей степенью числа $a$ , сравнимой с 1 по модулю $n$ .

Примеры [ править ]

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

хх, х ² , х ³ , ... (мод 14) 1: 1  3: 3, 9, 13, 11, 5, 1  5: 5, 11, 13, 9, 3, 1 9: 9, 11, 111: 11, 9, 113: 13, 1

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

Во втором примере пусть $n$ = 15. Элементы $ℤ$ ^×
₁₅- классы конгруэнции {1, 2, 4, 7, 8, 11, 13, 14}; их $φ$ (15) = 8 .

хх, х ² , х ³ , ... (мод.15) 1: 1  2: 2, 4, 8, 1  4: 4, 1 7: 7, 4, 13, 1 8: 8, 4, 2, 111: 11, 113: 13, 4, 7, 114: 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 1 + 8 = 512 \equiv 6 (mod 11)$ . Индекс 25 вдвое больше индекса 5: $28 = 256 25 (mod 11)$ . (Конечно, поскольку $25 \equiv 3 (mod 11)$ , запись для 3 равна 8).

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

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

Примитивные корни и индексы
(другие столбцы - это индексы целых чисел под соответствующими заголовками столбцов)
$п$	корень	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
$п$	корень	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$	первобытные корни по модулю $n$	заказ ( OEIS : A000010 )	$n$	первобытные корни по модулю $n$	заказ ( 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

Гипотеза Артина о первообразных корнях утверждает, что данное целое число $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 )

Арифметические факты [ править ]

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

Он также доказал ^[7], что для любого простого числа $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).

Поиск первобытных корней [ править ]

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

Во-первых, вычислим . Затем определяют различные простые множители из , скажем $р$ ₁ , ..., $р$ $к$ . Наконец, вычислим $\varphi (n)$ $\varphi (n)$

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

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

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

\varphi \left(\varphi (n)\right)

поскольку, вообще говоря, циклическая группа из $r$ элементов имеет образующие. Для простого $n$ это равно , и поскольку генераторы очень распространены среди {2, ..., $n$ −1}, и, следовательно, их относительно легко найти. ^[9] $\varphi (r)$ $\varphi (n-1)$ $n/\varphi (n-1)\in O(\log \log n)$

Если $g$ является примитивным корнем по модулю $p$ , то $g$ также является первообразным корнем по модулю всех степеней $p k,$ если только $g$ ^{$p$ −1} ≡ 1 (mod $p$ ² ); в этом случае $g$ + $p$ равно. ^[10]

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

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

Порядок величины первобытных корней [ править ]

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

Верхняя граница [ править ]

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

Гроссвальд (1981) доказал ^[11], что если , то $p>e^{e^{24}}$ $g_{p}<p^{0.499}~.$

Карелла (2015) доказал ^[12], что существует такое, что для всех достаточно больших простых чисел $C>0$ $g_{p}\leq C\,p^{5/\log \log p}$ $p>2~.$

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

Нижние границы [ править ]

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

Это может быть доказано ^[11] элементарным образом , что для любого положительного целого числа $М$ существует бесконечное множество простых чисел , таких , что $М$ < $г р$ < $р$ - $М$ .

Приложения [ править ]

Примитивный корень по модулю $n$ часто используется в криптографии , включая схему обмена ключами Диффи – Хеллмана . Звуковые диффузоры были основаны на теоретико-числовых концепциях, таких как первообразные корни и квадратичные вычеты . ^[14]^[15]

См. Также [ править ]

Гипотеза Артина о первобытных корнях
Dirichlet персонаж
Полный репенд прайм
Обобщение Гаусса теоремы Вильсона
Мультипликативный порядок
Квадратичный остаток
Корень из единицы по модулю n

Сноски [ править ]

^ "Одной из наиболее важных нерешенных проблем в теории конечных полей является разработка быстрого алгоритма для построения первообразных корней. Von zur Gathen & Shparlinski 1998 , стр. 15–24
^ «Не существует удобной формулы для вычисления [наименьшего примитивного корня]». Роббинс 2006 , стр. 159

Ссылки [ править ]

^ Стромквист, Уолтер. "Что такое первобытные корни?" . Математика. Колледж Брин-Мор. Архивировано из оригинала на 2017-07-03 . Проверено 3 июля 2017 .
^ Вайсштейн, Эрик В. "Группа умножения по модулю" . MathWorld .
^ Первобытный корень , Энциклопедия математики .
^ Виноградов 2003 , стр. 105–121, § VI Первобытные корни и индексы.
^ Виноградов 2003 , с. 106.
^ Гаусс и Кларк 1986 , искусства. 80.
↑ Gauss & Clarke 1986 , статья 81.
^ (последовательность A010554 в OEIS )
^ Кнут, Дональд Э. (1998). Получисловые алгоритмы . Искусство программирования. 2 (3-е изд.). Аддисон-Уэсли. раздел 4.5.4, с. 391.
^ a b Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Берлин: Springer . п. 26. ISBN 978-3-540-55640-4.
^ a b c d Рибенбойм, Пауло (1996). Новая книга рекордов простых чисел . Нью-Йорк, штат Нью-Йорк: Спрингер . п. 24. ISBN 978-0-387-94457-9.
^ Карелла, Н. (2015). «Наименьшие первичные примитивные корни». Международный журнал математики и информатики . 10 (2): 185–194. arXiv : 1709.01172 .
^ Bach & Shallit 1996 , стр. 254.
^ Уокер, Р. (1990). Проектирование и применение модульных акустических рассеивающих элементов (PDF) . Исследовательский отдел BBC (Отчет). Британская радиовещательная корпорация . Проверено 25 марта 2019 .
↑ Фельдман, Элиот (июль 1995 г.). «Отражательная решетка, которая устраняет зеркальное отражение: конус тишины». J. Acoust. Soc. Am . 98 (1): 623–634. Bibcode : 1995ASAJ ... 98..623F . DOI : 10.1121 / 1.413656 .

Источники [ править ]

Бах, Эрик; Шаллит, Джеффри (1996). Эффективные алгоритмы . Алгоритмическая теория чисел. Я . Кембридж, Массачусетс: MIT Press . ISBN 978-0-262-02405-1.

Карелла, Северная Каролина (2015). «Наименьшие первичные примитивные корни». Международный журнал математики и информатики . 10 (2): 185–194. arXiv : 1709.01172 .

Disquisitiones Arithmeticae был переведен из Гаусса Цицерона латинского на английский и немецкий языки. Немецкое издание включает все его работы по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

Гаусс, Карл Фридрих (1986) [1801]. Disquisitiones Arithmeticae . Перевод Кларка, Артур А. (2-е, исправленное изд.). Нью-Йорк, штат Нью-Йорк: Спрингер . ISBN 978-0-387-96254-2.

Гаусс, Карл Фридрих (1965) [1801]. Untersuchungen über höhere Arithmetik [ Исследования высшей арифметики ] (на немецком языке). Перевод Мазера, Х. (2-е изд.). Нью-Йорк, Нью-Йорк: Челси. ISBN 978-0-8284-0191-3.

Роббинс, Невилл (2006). Начало теории чисел . Джонс и Бартлетт Обучение. ISBN 978-0-7637-3768-9.

Виноградов И.М. (2003). «§ VI Первобытные корни и индексы» . Элементы теории чисел . Минеола, Нью-Йорк: Dover Publications. С. 105–121. ISBN 978-0-486-49530-9.

фон цур Гатен, Иоахим ; Шпарлинский, Игорь (1998). «Порядки периодов Гаусса в конечных полях». Применимая алгебра в инженерии, коммуникации и вычислениях . 9 (1): 15–24. CiteSeerX 10.1.1.46.5504 . DOI : 10.1007 / s002000050093 . Руководство по ремонту 1624824 . S2CID 19232025 .

Дальнейшее чтение [ править ]

Оре, Ойштейн (1988). Теория чисел и ее история . Дувр. С. 284–302 . ISBN 978-0-486-65620-5..

Внешние ссылки [ править ]

Вайсштейн, Эрик В. «Первобытный корень» . MathWorld .
Холт. «Квадратичные вычеты и первообразные корни» . Математика. Michigan Tech.
"Калькулятор первобытных корней" . BlueTulip .

[8] "Одной из наиболее важных нерешенных проблем в теории конечных полей является разработка быстрого алгоритма для построения первообразных корней. Von zur Gathen & Shparlinski 1998 , стр. 15–24

[9] «Не существует удобной формулы для вычисления [наименьшего примитивного корня]». Роббинс 2006 , стр. 159

[1] Стромквист, Уолтер. "Что такое первобытные корни?" . Математика. Колледж Брин-Мор. Архивировано из оригинала на 2017-07-03 . Проверено 3 июля 2017 .

[2] Вайсштейн, Эрик В. "Группа умножения по модулю" . MathWorld .

[3] Первобытный корень , Энциклопедия математики .

[Vinogradov2003.pp=105–121-4] Виноградов 2003 , стр. 105–121, § VI Первобытные корни и индексы.

[5] Виноградов 2003 , с. 106.

[6] Гаусс и Кларк 1986 , искусства. 80.

[7] Gauss & Clarke 1986 , статья 81.

[10] (последовательность A010554 в OEIS )

[Knuth-1998-11] Кнут, Дональд Э. (1998). Получисловые алгоритмы . Искусство программирования. 2 (3-е изд.). Аддисон-Уэсли. раздел 4.5.4, с. 391.

[Cohen1993-12] Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Берлин: Springer . п. 26. ISBN 978-3-540-55640-4.

[Ribenboim,_p.24-13] Рибенбойм, Пауло (1996). Новая книга рекордов простых чисел . Нью-Йорк, штат Нью-Йорк: Спрингер . п. 24. ISBN 978-0-387-94457-9.

[Carella-2015-14] Карелла, Н. (2015). «Наименьшие первичные примитивные корни». Международный журнал математики и информатики . 10 (2): 185–194. arXiv : 1709.01172 .

[15] Bach & Shallit 1996 , стр. 254.

[Walker-1990-16] Уокер, Р. (1990). Проектирование и применение модульных акустических рассеивающих элементов (PDF) . Исследовательский отдел BBC (Отчет). Британская радиовещательная корпорация . Проверено 25 марта 2019 .

[Feldman-17] Фельдман, Элиот (июль 1995 г.). «Отражательная решетка, которая устраняет зеркальное отражение: конус тишины». J. Acoust. Soc. Am . 98 (1): 623–634. Bibcode : 1995ASAJ ... 98..623F . DOI : 10.1121 / 1.413656 .

[1],