Первообразный корень по модулю n

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

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

Гаусс определил примитивные корни в статье 57 Disquisitiones Arithmeticae (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 modulo  n ) всегда повторяется после некоторого значения k , поскольку modulo  n производит конечное число значений. Если g является примитивным корнем по модулю  n, а n является простым числом, то период повторения равен n − 1. Было показано, что перестановки, созданные таким образом (и их циклические сдвиги), являются массивами Костаса .

Определение

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

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

Для любого n (независимо от того, ${\displaystyle \mathbb {Z} }$^×
_нциклический), порядок ${\displaystyle \mathbb {Z} }$^×
_нзадается функцией Эйлера φ ( n ) (последовательность A000010 в OEIS ). И затем, теорема Эйлера гласит, что a ^{φ ( n )} ≡ 1 (mod n ) для любого a, взаимно простого с n ; наименьшая степень a , которая сравнима с 1 по модулю n , называется мультипликативным порядком a по модулю 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 также является примитивным корнем по модулю всех степеней p ^k, если только g ^{p −1} ≡ 1 (mod p ² ); в этом случае 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 такая, что для бесконечного числа простых чисел g _p > C log p .

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

Приложения

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

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

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

Сноски

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

Ссылки

1. Вайсштейн, Эрик В. «Группа умножения по модулю». Математический мир .
2. Первообразный корень, Энциклопедия математики
3. (Виноградов 2003, стр. 105–121, § VI ПЕРВООБРАЗНЫЕ КОРНИ И ИНДЕКСЫ)
4. (Гаусс 1986, статьи 52–56, 82–891)
5. Стромквист, Уолтер. «Что такое примитивные корни?». Математика. Колледж Брин-Мор. Архивировано из оригинала 2017-07-03 . Получено 2017-07-03 .
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. Cohen, Henri (1993). Курс вычислительной алгебраической теории чисел . Берлин: Springer . стр. 26. ISBN 978-3-540-55640-4.
16. Рибенбойм, Пауло (1996). Новая книга записей простых чисел . Нью-Йорк, Нью-Йорк: Springer . стр. 24. ISBN 978-0-387-94457-9.
17. Берджесс, ДА (1962). «О суммах характеров и первообразных корнях †». Труды Лондонского математического общества . s3-12 (1): 179–192. doi :10.1112/plms/s3-12.1.179.
18. Гроссвальд, Э. (1981). «О границе Берджесса для примитивных корней по модулю простых чисел и ее применении к Γ(p)». American Journal of Mathematics . 103 (6): 1171–1183. doi :10.2307/2374229. ISSN  0002-9327. JSTOR  2374229.
19. Бах и Шалит 1996, с. 254.
20. Джентл, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло (2-е изд.). Нью-Йорк: Springer. ISBN 0-387-00178-6. OCLC  51534945.
21. Уокер, Р. (1990). Проектирование и применение модульных акустических рассеивающих элементов (PDF) . Исследовательский отдел BBC (Отчет). Британская вещательная корпорация . Получено 25 марта 2019 г. .
22. Фельдман, Элиот (июль 1995 г.). «Отражательная решетка, которая сводит на нет зеркальное отражение: конус тишины». J. Acoust. Soc. Am . 98 (1): 623–634. Bibcode : 1995ASAJ...98..623F. doi : 10.1121/1.413656.

Источники

• Бах, Эрик; Шаллит, Джеффри (1996). Эффективные алгоритмы . Алгоритмическая теория чисел. Том I. Кембридж, Массачусетс: Издательство MIT . 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). Начало теории чисел. Jones & Bartlett Learning. ISBN 978-0-7637-3768-9.

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

• von zur Gathen, Joachim ; Shparlinski, Igor (1998). "Порядки периодов Гаусса в конечных полях". Applicable Algebra in Engineering, Communication and Computing . 9 (1): 15–24. CiteSeerX  10.1.1.46.5504 . doi :10.1007/s002000050093. MR  1624824. S2CID  19232025.

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

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

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

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