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

Концепция модульной арифметики

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

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

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

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

Число 3 является примитивным корнем по модулю 7 ^[5], поскольку $${\displaystyle {\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 ^k по модулю 7 равен 6. Остатки в периоде, которые равны 3, 2, 6, 4, 5, 1, образуют перестановку всех ненулевых остатков по модулю 7, подразумевая, что 3 действительно является примитивный корень по модулю 7. Это происходит из-за того, что последовательность ( g ^k по модулю  n ) всегда повторяется после некоторого значения k , поскольку по модулю  n дает конечное число значений. Если g — примитивный корень по модулю  n , а n — простое число, то период повторения равен n — 1. Было показано, что созданные таким образом перестановки (и их круговые сдвиги) представляют собой массивы Костаса .

Определение

Если n - положительное целое число, целые числа от 1 до n - 1 , взаимно простые с n ( или, что то же самое, классы сравнения, взаимно простые с n ), образуют группу с умножением по модулю n в качестве операции; это обозначается ${\displaystyle \mathbb {Z} }$^×
_ни называется группой единиц по модулю n или группой примитивных классов по модулю n . Как объяснено в статье мультипликативная группа целых чисел по модулю n , эта мультипликативная группа ( ${\displaystyle \mathbb {Z} }$^×
_н) является циклическим тогда и только тогда, когда ⁿ равно 2, 4, pk или 2pk, где ^pk — степень ^{нечетного} простого числа . ^{[6] [7] [8]} Когда (и только тогда) эта группа ${\displaystyle \mathbb {Z} }$^×
_нявляется циклическим, генератор этой циклической группы называется примитивным корнем по модулю n ^[9] (или, на более полном языке, примитивным корнем из единицы по модулю n , подчеркивая его роль как фундаментального решения корней единичных полиномиальных уравнений X^м
− 1 в кольце _n ), или просто примитивный элемент ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {Z} }$^×
_н.

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

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

Примеры

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

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

хх, х 2 , х 3 , ... (мод. 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 )

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

Числа , имеющие примитивный корень, имеют вид ${\displaystyle n}$

${\displaystyle 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]

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

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

Характеристики

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

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

Например,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Сноски

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

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

1. Вайсштейн, Эрик В. «Группа умножения по модулю». Математический мир .
2. Первобытный корень, Энциклопедия математики
3. (Виноградов 2003, стр. 105–121, § VI ПРИМИТИВНЫЕ КОРНИ И ИНДЕКСЫ)
4. (Гаусс 1986, ст. 52–56, 82–891)
5. Стромквист, Уолтер. «Что такое примитивные корни?». Математика. Колледж Брин-Мор. Архивировано из оригинала 3 июля 2017 г. Проверено 3 июля 2017 г.
6. Вайсштейн, Эрик В. «Группа умножения по модулю». Математический мир .
7. Первобытный корень, Математическая энциклопедия .
8. Виноградов 2003, стр. 105–121, § VI Примитивные корни и индексы.
9. Виноградов 2003, с. 106.
10. Гаусс 1986, ст. 92.
11. Гаусс 1986, искусство. 80.
12. Гаусс 1986, ст. 81.
13. (последовательность A010554 в OEIS )
14. Кнут, Дональд Э. (1998). Получисловые алгоритмы . Искусство компьютерного программирования. Том. 2 (3-е изд.). Аддисон-Уэсли. раздел 4.5.4, стр. 391.
15. Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Берлин: Шпрингер . п. 26. ISBN 978-3-540-55640-4.
16. Рибенбойм, Пауло (1996). Новая книга рекордов простых чисел . Нью-Йорк, штат Нью-Йорк: Спрингер . п. 24. ISBN 978-0-387-94457-9.
17. Берджесс, Д.А. (1962). «О суммах символов и примитивных корнях †». Труды Лондонского математического общества . с3-12 (1): 179–192. дои : 10.1112/plms/s3-12.1.179.
18. Гроссвальд, Э. (1981). «О границе Бёрджесса для примитивных корней по модулю простых чисел и приложении к Γ (p)». Американский журнал математики . 103 (6): 1171–1183. дои : 10.2307/2374229. ISSN  0002-9327. JSTOR  2374229.
19. Бах и Шалит 1996, с. 254.
20. Нежный, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло (2-е изд.). Нью-Йорк: Спрингер. ISBN 0-387-00178-6. ОСЛК  51534945.
21. Уокер, Р. (1990). Проектирование и применение модульных акустических рассеивающих элементов (PDF) . Исследовательский отдел BBC (Отчет). Британская радиовещательная корпорация . Проверено 25 марта 2019 г.
22. Фельдман, Элиот (июль 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) [1801]. Арифметические исследования . Перевод Кларка, Артура А. (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 . дои : 10.1007/s002000050093. MR  1624824. S2CID  19232025.

дальнейшее чтение

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

Внешние ссылки

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