Постановка задачи, основные идеи (52).
2. 5. Дискретное преобразование Люка–Мерсенна . . . . . . . . . . . . . . . 54
2. 5. 1. Коды Люка–Мерсенна (54). 2. 5. 2. Дискретное преобразова-
ние Люка–Мерсенна (56). 2. 5. 3. Вычисление дискретной круговой
свертки с помощью LMT (58).
2. 6. Некоторые обобщения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2. 6. 1. Обобщение на квазимерсенновы модули (59). 2. 6. 2. Обоб-
щение на случай рекуррентных систем счисления третьего поряд-
ка (61). Комментарии к главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Литература к главе 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Г л а в а 3. Неоднозначность разложения на множители и парал-
лельные алгоритмы вычисления свертки . . . . . . . . . . . . . . . . . 65
3. 1. Введение, основные идеи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3. 2. Параллельные алгоритмы вычисления свертки по модулю составно-
го числа Мерсенна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3. 2. 1. Альтернативное представление разложения (составных) чи-
сел Мерсенна (68). 3. 2. 2.
Вычисление свертки по модулю состав-
ного числа Мерсенна (72).
3. 3. Параллельные алгоритмы вычисления свертки по модулю составно-
го числа Ферма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3. 3. 1. Альтернативное разложение (составных) чисел Ферма (75).
3. 3. 2. Вычисление свертки по модулю составного числа Фер-
ма (80). Комментарии к главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Литература к главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Г л а в а 4. Канонические системы счисления в полях алгебраиче-
ских чисел и параллельные алгоритмы вычисления свертки . . . 84
4. 1. Введение, основные идеи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4. 1. 1. Требования, предъявляемые к системам счисления (84). Оглавление 5
4. 2. Предварительные сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4. 2. 1. Целые элементы в квадратичных полях (86). 4. 2. 2. «Канони-
ческие» системы счисления в квадратичных полях (86). 4. 2. 3. При-
меры канонических систем счисления (89).
4. 3. Параллельные алгоритмы вычисления свертки в «канонических»
системах счисления для квадратичных полей . . . . . . . . . . . . . . . 91
4. 3. 1. Параллельные алгоритмы вычисления свертки в РКСС с ос-
нованием (i − 1) (91). 4. 3. 2. Параллельные алгоритмы вычисления
1 √
свертки в РКСС с основанием (−1 ± i 7 ) (95). 4. 3. 3. Парал-
2
лельные алгоритмы вычисления свертки в РКСС с основанием
√
(±i 2 ) (98).
4. 4.