Читать онлайн «Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований»

Автор Чернов В.М.

Постановка задачи, основные идеи (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.