Cтраница 1
Китайский алгоритм с предварительной обработкой данных, примененный к k модулям по b битов в каждом, работает не более ОБ ( bk log k log bk log log bk) времени. [1]
Китайский алгоритм остатков так назван потому, что впервые был найден в Учебнике математики мастера Сана, написанном между 287 и 473 годами нашей эры. В своей книге мастер Сан решал численные примеры, а потом выводил из них общие правила решения аналогичных задач. [2]
Китайский алгоритм остатков - это простое обобщение метода, использованного при решении системы из § 8.2. Подробному изучению алгоритма и посвящен настоящий параграф. [3]
В завершение, пользуясь китайским алгоритмом, получаем окончательный результат res. Если дана положительная оценка на res, то ищется наименьшее неотрицательное решение системы уравнений по китайскому алгоритму, если же оценивается res, то ищется наименьшее по абсолютной величине решение. На рис. 3.4 представлена диаграмма, иллюстрирующая приведенный алгоритм. [4]
Теорема 8.21. В случае целых чисел китайский алгоритм имеет сложность Оъ ( М ( bk) log k) 0B ( kM ( b) log b), где k - число используемых модулей, содержащих Ь двоичных разрядов каждый. [5]
В этой главе мы изучаем метод решения систем линейных сравнений, называемый китайским алгоритмом остатков. В последнем параграфе мы увидим, как этот алгоритм применяется для передачи ключа к шифру нескольким людям. [6]
Эта ситуация не является нереальной. Если часто применять китайский алгоритм для перевода чисел, представленных вычетами по фиксированному множеству модулей, то разумно заранее вычислить те функции от этих модулей, значения которых используются в алгоритме. В следствии теоремы 8.21 мы увидим, что на оценку сложности наличие предварительной обработки ( или ее отсутствие) влияет весьма скромно. [7]
Для систем сравнений, число уравнений в которых больше двух, есть свой вариант китайской теоремы об остатках. Мы ее сформулируем без доказательства, поскольку это просто еще одно приложение китайского алгоритма остатков. [8]
В завершение, пользуясь китайским алгоритмом, получаем окончательный результат res. Если дана положительная оценка на res, то ищется наименьшее неотрицательное решение системы уравнений по китайскому алгоритму, если же оценивается res, то ищется наименьшее по абсолютной величине решение. На рис. 3.4 представлена диаграмма, иллюстрирующая приведенный алгоритм. [9]