Примитивный корень

Cтраница 3

Следует отметить еще одну особенность книги: у каждой важной теоремы и у всякого важного алгоритма есть свое имя. В большинстве своем это классические имена, которые используются в этом качестве уже десяти - или столетиями. По некоторым из них, как, скажем, теорема о примитивном корне, формулировка результата немедленно восстанавливается всяким, знакомым с предметом изложения; для других сделать это труднее. [31]

Разумеется, со времен Эв-клида теория чисел была пронизана алгоритмами, однако до самого последнего времени этот подход казался несколько старомодным. Мы относимся к нему очень серьезно. Так, доказательству Эвклида бесконечности множества простых чисел предшествует обсуждение формулы праймориала, а существование примитивных корней по модулю простого числа доказывается с помощью алгоритма Гаусса, который тот изобрел для вычисления корней. [32]

Изображение составных чисел, используемых при вычислении w по модулю Ъ. В каждом блоке, состоящем из нулей, содержатся 2 log b нулей. [33]

Вычислив все wt по модулю Ь, вычисляем wt по модулю 22 1 с помощью обернутой свертки. Для этого надо взять преобразование Фурье, выполнить попарные умножения и найти обратное преобразование. По теореме 7.5 элементы со и Ь имеют обратные по модулю т, а со - примитивный корень & - й степени из единицы. [34]

Следовательно, aa w0a, где о0 - некоторый корень ге-й степени из единицы, не обязательно примитивный. Отображение ai - wa является, очевидно, гомоморфизмом G в группу корней w - Й степени из единицы, причем инъективным. Если о - образующая G, то ша - примитивный корень d - й степени из единицы. [35]

Следовательно, аа со0а, где ( 00 - некоторый корень / г-й степени из единицы, не обязательно примитивный. Отображение oi - ю0 является, очевидно, гомоморфизмом G в группу корней л-й степени из единицы, причем инъективным. Если о - образующая G, то № 0 - примитивный корень d - R степени из единицы. [36]

О ( п1о % 3) шагов, разбивая каждое двоичное число на два ( п / 2) - разрядных числа. Этот метод можно обобщить, разбивая числа на Ъ блоков по / разрядов в каждом. Чтобы определить коэффициенты произведения полиномов, вычисляем полиномы на некотором подходящем множестве точек, перемножаем найденные значения и интерполируем. Выбрав в качестве точек, в которых вычисляются полиномы, примитивные корни из единицы, можно воспользоваться преобразованием Фурье и теоремой о свертке. Сделав Ъ функцией от п и применив рекурсию, можно умножить два / г-разрядных двоичных числа за ОБ ( п log п log log n) шагов. [37]

Страницы: 1 2 3