Математика. Китайская теорема об остатках - 1. Алгоритм Гарнера.

Китайская теорема об остатках широко применяется

в теории чисел, криптографии и других дисциплинах:

1. Взаимно однозначное соответствие между некоторым числом и набором его остатков, определяемым набором взаимно простых чисел, существование которого утверждается в теореме, на практике помогает работать не с длинными числами, а с наборами их коротких по длине остатков. Кроме того вычисления по каждому из модулей можно выполнять параллельно.

Если в качестве базиса взять, к примеру, первые 500 простых чисел, длина каждого из которых не превосходит 12 бит, то этого хватит для представления десятичных чисел длиной до 1519 знаков. (Откуда взялось число 1519 понять очень просто: сумма десятичных логарифмов первых 500 простых чисел равна 1519,746…). Например, в алгоритме RSA вычисления производятся по модулю очень большого числа n, представимого в виде произведения двух больших простых чисел. Теорема позволяет перейти к вычислениям по модулю этих простых делителей, которые по величине уже порядка корня из n, а значит, имеют в два раза меньшую битовую длину. Отметим также, что применение вычислений согласно китайской теореме об остатках делает алгоритм RSA восприимчивым к атакам по времени.

2. На теореме основаны схема Асмута - Блума и схема Миньотта -- пороговые схемы разделения секрета в группе участников. Секрет могут узнать только k из n участников, объединив свои ключи.

3. Одним из применения является быстрое преобразование Фурье на основе простых чисел

4. Теорема лежит в основе принципа Хассе поиска целочисленных корней уравнения.

5. Из теоремы следует мультипликативность функции Эйлера.

6. На теореме основывается алгоритм Полига-Хеллмана нахождения дискретного логарифма за полиномиальное время для чисел, имеющих специальный вид.

7. Теорема имеет множество применений в шифровании и дешифровании в криптографических системах, например, в криптосистеме Рабина или в шифре Виженера.

Подробнее в прикрепленном файле.