Китайская теорема об остатках и СОК: Параллельная арифметика
В III веке нашей эры китайский математик Сунь-цзы записал интригующую головоломку: "Имеются вещи, число их неизвестно. Если считать их тройками, остаток 2. Если считать пятерками, остаток 3. Если считать семерками, остаток 2. Сколько всего вещей?". Эта, казалось бы, тривиальная задача привела к созданию математического аппарата, который сегодня используется для ускорения вычислений в цифровой обработке сигналов (DSP) и современной криптографии.
Математическое решение этой задачи обобщено в Китайской теореме об остатках (КТО). Теорема гласит: если у вас есть набор попарно взаимно простых модулей (например, 3, 5, 7), то любая система линейных сравнений (уравнений с остатками) по этим модулям всегда имеет единственное решение в пределах произведения этих модулей (в нашем примере — от 0 до 3*5*7 = 105). Ответ на загадку Сунь-цзы — число 23.
В компьютерных науках эта теорема породила Систему остаточных классов (СОК, или Residue Number System, RNS). В классической позиционной двоичной системе сложение или умножение длинных чисел требует последовательного переноса разрядов от младших к старшим (carry). Вы не можете сложить старшие биты, пока не узнаете, был ли перенос из младших. Это создает аппаратную задержку (bottleneck) в процессорах.
В Системе остаточных классов числа представляются не как биты, а как кортежи остатков от деления на набор взаимно простых базисных модулей. Если базис — это {3, 5, 7}, то число 14 представляется как вектор (2, 4, 0), так как 14 mod 3 = 2, 14 mod 5 = 4, 14 mod 7 = 0.
Магия СОК в том, что операции сложения, вычитания и умножения над этими векторами выполняются строго параллельно и абсолютно независимо для каждого модуля! Здесь вообще нет проблемы переноса разрядов. Чтобы перемножить два гигантских числа, процессор просто перемножает их маленькие остатки параллельно в разных аппаратных блоках, что происходит практически мгновенно. Затем результат возвращается в обычный двоичный вид с помощью алгоритмов на основе Китайской теоремы об остатках.
Этот метод невероятно эффективен для создания быстродействующих цифровых фильтров (FIR/IIR) в телекоммуникациях, обработки видео в реальном времени на ПЛИС (FPGA) и особенно в алгоритме RSA, где применение Китайской теоремы об остатках позволяет в 4 раза ускорить операцию расшифровки сообщений на серверах.
