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

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

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

Примитивный корень существует тогда и только тогда, когда n равно 1, 2, 4, p ^к или 2 п. ^к, где p — нечетное простое число и k > 0 . Для всех других значений n мультипликативная группа целых чисел по модулю n не является циклической . ^[1]^[2]^[3] Впервые это было доказано Гауссом . ^[4]

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

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

{\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\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$ - положительное целое число, целые числа от 1 до $n$ - 1 , взаимно простые с $n$ (или, что то же самое, классы сравнения , взаимно простые с $n$ ), образуют группу с умножением по модулю $n$ в качестве операции; это обозначается $\mathbb {Z}$ ^×
_$n$ и называется группой единиц по модулю $n$ или группой примитивных классов по модулю $n$ . Как объяснено в статье мультипликативная группа целых чисел по модулю $n$ , эта мультипликативная группа ( $\mathbb {Z}$ ^×
_$n$ ) является циклическим тогда и только тогда, когда $n$ равно 2, 4, $p к$ , или 2 $п. к$ где $р к$ является степенью нечетного простого числа . ^[6]^[7]^[8] Когда (и только когда) эта группа $\mathbb {Z}$ ^×
_$n$ циклическая, образующая этой циклической группы называется примитивным корнем по модулю $n.$ ^[9] (или, говоря более полным языком, примитивный корень из единицы по модулю $n$ , подчеркивая его роль как фундаментального решения корней единичных полиномиальных уравнений X ^$м$
− 1 на ринге $\mathbb {Z}$ _$n$ ), или просто примитивный элемент $\mathbb {Z}$ ^×
_$н$ .

Когда $\mathbb {Z}$ ^×
_$n$ нецикличен, таких примитивных элементов по модулю $n$ не существует. Вместо этого каждый простой компонент $n$ имеет свои собственные субпримитивные корни (см. $15$ в примерах ниже).

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

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

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

 x     x, 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. Элементы $\mathbb {Z}$ ^×
₁₅ — классы конгруэнтности {1, 2, 4, 7, 8, 11, 13, 14}; их $φ$ (15) = 8 .

 x     x, 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 )

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

Числа $n$ имеющие примитивный корень, имеют форму

n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ prime}};\;k\in \mathbb {N} \},

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. ^[10]

Это цифры $n$ с $\varphi (n)=\lambda (n),$ хранится также в последовательности A033948 в OEIS .

В следующей таблице перечислены примитивные корни по модулю $n$ до $n=31$ :

$n$	примитивные корни по модулю $n$	заказ $\varphi (n),$ ( ОЭИС : A000010 )	показатель степени $\lambda (n),$ ( ОЭИС : A002322 )
1	0	1	1
2	1	1	1
3	2	2	2
4	3	2	2
5	2, 3	4	4
6	5	2	2
7	3, 5	6	6
8		4	2
9	2, 5	6	6
10	3, 7	4	4
11	2, 6, 7, 8	10	10
12		4	2
13	2, 6, 7, 11	12	12
14	3, 5	6	6
15		8	4
16		8	4
17	3, 5, 6, 7, 10, 11, 12, 14	16	16
18	5, 11	6	6
19	2, 3, 10, 13, 14, 15	18	18
20		8	4
21		12	6
22	7, 13, 17, 19	10	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	22
24		8	2
25	2, 3, 8, 12, 13, 17, 22, 23	20	20
26	7, 11, 15, 19	12	12
27	2, 5, 11, 14, 20, 23	18	18
28		12	6
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	28
30		8	4
31	3, 11, 12, 13, 17, 21, 22, 24	30	30

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

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

Он также доказал ^[12] что для любого простого числа $p$ сумма его примитивных корней конгруэнтна $µ$ ( $p$ − 1) по модулю $p$ , где $µ$ — функция Мёбиуса .

Например,

$р$ = 3,	$ц$ (2) = −1.	Первоначальный корень равен 2.
$р$ = 5,	$ц$ (4) = 0.	Первоначальные корни — 2 и 3.
$р$ = 7,	$м$ (6) = 1.	Первоначальные корни — 3 и 5.
$р$ = 31,	$ц$ (30) = −1.	Первоначальные корни — 3, 11, 12, 13, 17, 21, 22 и 24.

Например, произведение последних примитивных корней равно $2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}$ , а их сумма равна $123\equiv -1\equiv \mu (31-1){\pmod {31}}$ .

Если $a$ является примитивным корнем по модулю простого числа $p$ , затем $a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$ .

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

Нахождение примитивных корней [ править ]

Простая общая формула для вычисления примитивных корней по модулю $n$ неизвестна. ^[а]^[б] Однако существуют методы обнаружения примитивного корня, которые работают быстрее, чем простая проверка всех кандидатов. Если мультипликативный порядок (его показатель ) числа $m$ по модулю $n$ равен $\varphi (n)$ (порядок $\mathbb {Z}$ ^×
_$n$ ), то это примитивный корень. На самом деле верно обратное: если $m$ является примитивным корнем по модулю $n$ , то мультипликативный порядок $m$ равен $\varphi (n)=\lambda (n)~.$ Мы можем использовать это, чтобы проверить кандидата $m$ на предмет его примитивности.

Для $n>1$ сначала вычисли $\varphi (n)~.$ Затем определите различные простые множители $\varphi (n)$ , скажем, $p$ ₁ , ..., $p k$ . Наконец, вычислите

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

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

Число первообразных корней по модулю $n$ , если таковые имеются, равно ^[13]

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

поскольку, вообще говоря, циклическая группа с $r$ элементами имеет $\varphi (r)$ генераторы.

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

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

Если $g$ — примитивный корень по модулю $p к$ , то $g$ также является примитивным корнем по модулю всех меньших степеней $p$ .

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

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

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

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

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

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

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

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

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

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

Это можно доказать ^[16] элементарным образом, что для любого натурального числа $M$ существует бесконечно много простых чисел таких, что $M$ < $g p$ < $p$ − $M$ .

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

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

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

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

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

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

^ Вайсштейн, Эрик В. «Группа умножения по модулю» . Математический мир .
^ Первобытный корень , Энциклопедия математики.
^ ( Vinogradov 2003 , pp. 105–121, § VI PRIMITIVE ROOTS AND INDICES)
^ ( Гаусс 1986 , ст. 52–56, 82–891)
^ Стромквист, Уолтер. «Что такое примитивные корни?» . Математика. Колледж Брин-Мор. Архивировано из оригинала 3 июля 2017 г. Проверено 3 июля 2017 г.
^ Вайсштейн, Эрик В. «Группа умножения по модулю» . Математический мир .
^ Первобытный корень , Энциклопедия математики .
^ Vinogradov 2003 , pp. 105–121, § VI Primitive roots and indices.
^ Vinogradov 2003 , p. 106.
^ Гаусс 1986 , ст. 92.
^ Гаусс 1986 , искусство. 80.
^ Гаусс 1986 , арт 81.
^ (последовательность A010554 в OEIS )
^ Кнут, Дональд Э. (1998). Получисловые алгоритмы . Искусство компьютерного программирования. Том. 2 (3-е изд.). Аддисон-Уэсли. раздел 4.5.4, стр. 391.
^ Jump up to: Перейти обратно: ^а ^б Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Берлин: Шпрингер . п. 26. ISBN 978-3-540-55640-4 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Рибенбойм, Пол (1996). Новая книга рекордов простых чисел Нью-Йорк, штат Нью-Йорк: Спрингер . п. 24. ISBN 978-0-387-94457-9 .
^ Берджесс, Д.А. (1962). «О суммах символов и примитивных корнях †» . Труды Лондонского математического общества . с3-12 (1): 179–192. дои : 10.1112/plms/s3-12.1.179 .
^ Гроссвальд, Э. (1981). «О границе Бёрджесса для примитивных корней по модулю простых чисел и приложении к Γ (p)» . Американский журнал математики . 103 (6): 1171–1183. дои : 10.2307/2374229 . ISSN 0002-9327 . JSTOR 2374229 .
^ Бах и Шалит 1996 , с. 254.
^ Нежный, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло (2-е изд.). Нью-Йорк: Спрингер. ISBN 0-387-00178-6 . OCLC 51534945 .
^ Уокер, Р. (1990). Проектирование и применение модульных акусторассеивающих элементов (PDF) . Исследовательский отдел BBC (Отчет). Британская радиовещательная корпорация . Проверено 25 марта 2019 г.
^ Фельдман, Элиот (июль 1995 г.). «Решетка отражения, сводящая на нет зеркальное отражение: конус тишины». Дж. Акуст. Соц. Являюсь . 98 (1): 623–634. Бибкод : 1995ASAJ...98..623F . дои : 10.1121/1.413656 .

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

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

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

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

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

Гаусс, Карл Фридрих (1965) [1801]. Исследования высшей арифметики на ( немецком языке). Перевод Мазера Х. (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 . дои : 10.1007/s002000050093 . МР 1624824 . S2CID 19232025 .

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

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

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

Вайсштейн, Эрик В. «Примитивный корень» . Математический мир .
Холт. «Квадратичные вычеты и примитивные корни» . Математика. Мичиганский технологический институт.
«Калькулятор примитивных корней» . СинийТюльпан .

[13] «Одной из наиболее важных нерешенных проблем теории конечных полей является разработка быстрого алгоритма построения примитивных корней. фон Цур Гатен и Шпарлински 1998 , стр. 15–24

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

[1] Вайсштейн, Эрик В. «Группа умножения по модулю» . Математический мир .

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

[Vinogradov2003.pp=105-121-3] ( Vinogradov 2003 , pp. 105–121, § VI PRIMITIVE ROOTS AND INDICES)

[4] ( Гаусс 1986 , ст. 52–56, 82–891)

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

[6] Вайсштейн, Эрик В. «Группа умножения по модулю» . Математический мир .

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

[Vinogradov2003.pp=105–121-8] Vinogradov 2003 , pp. 105–121, § VI Primitive roots and indices.

[9] Vinogradov 2003 , p. 106.

[10] Гаусс 1986 , ст. 92.

[11] Гаусс 1986 , искусство. 80.

[12] Гаусс 1986 , арт 81.

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

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

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

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

[19] Берджесс, Д.А. (1962). «О суммах символов и примитивных корнях †» . Труды Лондонского математического общества . с3-12 (1): 179–192. дои : 10.1112/plms/s3-12.1.179 .

[20] Гроссвальд, Э. (1981). «О границе Бёрджесса для примитивных корней по модулю простых чисел и приложении к Γ (p)» . Американский журнал математики . 103 (6): 1171–1183. дои : 10.2307/2374229 . ISSN 0002-9327 . JSTOR 2374229 .

[21] Бах и Шалит 1996 , с. 254.

[22] Нежный, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло (2-е изд.). Нью-Йорк: Спрингер. ISBN 0-387-00178-6 . OCLC 51534945 .

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

[Feldman-24] Фельдман, Элиот (июль 1995 г.). «Решетка отражения, сводящая на нет зеркальное отражение: конус тишины». Дж. Акуст. Соц. Являюсь . 98 (1): 623–634. Бибкод : 1995ASAJ...98..623F . дои : 10.1121/1.413656 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[а]

[б]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]