Дипломная работа: Математические основы системы остаточных классов
Поскольку . Поэтому
вычисляются путём сложения
битовых чисел
.
Обратный переход от СОК к позиционной системе счисления выполняется немного сложнее. Как мы видели при доказательстве китайской теоремы об остатках, при вычислении обратных мультипликативных элементов требуется уметь вычислять значение функции Эйлера, которое в общем случае требует факторизации, т. е. разложения чисел на простые множители. Даже это обстоятельство показывает, что обратное преобразование чисел из СОК в позиционную систему счисления приводит к большому числу вычислительных операций с высокой точностью, а именно этого нам хотелось бы избежать прежде всего. Поэтому, чтобы найти действительно пригодный для практического применения метод перехода от
к А, необходимо иметь другое доказательство китайской теоремы об остатках. Такое доказательство предложено в 1958 г. Х. Л. Гарнером. Оно основано на использовании
констант
, где
. (5.4)
Константы можно вычислить с помощью расширенного алгоритма Евклида, который по заданным i и j позволяет определить числа a и b такие, что
, и можно положить
. В частности, для величины, обратной к
по модулю
, легко получить сравнитель