Математические основы системы остаточных классов (стр. 5 из 19)
. (5.1)Другими словами, значение каждого модуля на единицу меньше очередной степени 2. Такой выбор значения модуля
зачастую упрощает выполнение основных арифметических операций, так как выполнять вычисления с числами, представленными по модулю 
, несколько проще, чем с числами, представленными в обратном коде. После того как значения модулей таким образом выбраны, полезно несколько ослабить условие 
и потребовать чтобы только 
, 
. (5.2)Таким образом, значение
принимается в качестве оптимального вместо 
, поскольку это, с одной стороны, не влияет на справедливость китайской теоремы об остатках, а с другой означает, что 
может быть любым - битовым двоичным числом. При таком допущении, операции сложения и вычитания по модулю выполняются следующим образом: 
, 
.Здесь
и 
указывают на действия, которые с учётом условия (5.2) должны быть выполнены с отдельными компонентами кортежей 
и 
при сложении или умножении соответственно. При вычитании можно пользоваться и соотношением: 
.Эти операции могут быть эффективно выполнены, даже если
больше машинного слова компьютера, так как совсем просто вычислить остаток положительного числа по модулю степени 2 или разложить число по степеням 2. Для работы с модулями вида 
необходимо знать, при каких условиях число 
является взаимно простым с числом 
. Для этого существует простое правило: 
. (5.3)Формула (5.3) утверждает, в частности, что
.Уравнение (5.3) следует из алгоритма Евклида и тождества
,где mod означает операцию нахождения остатка от деления. Поэтому на компьютере с длиной слова 232 можно выбрать
, 
, 
, 
, 
,что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до
.Как мы уже заметили, операции преобразования чисел в СОК и обратно очень важны. Модулярное представление
для заданного числа А может быть получено посредством деления А на 
с запоминанием остатков. В случае, когда 
, возможно применение более подходящего способа, который состоит в том, чтобы, используя СОК, вычислить полином 
.Если основание b = 2 и модули
имеют вид , оба подхода сводятся к совсем простому способу. Рассмотрим двоичные представления числа А с блоками по 
бит:
,где
и 
при 
.Тогда
,Поскольку
. Поэтому 
вычисляются путём сложения битовых чисел 
.Обратный переход от СОК к позиционной системе счисления выполняется немного сложнее. Как мы видели при доказательстве китайской теоремы об остатках, при вычислении обратных мультипликативных элементов требуется уметь вычислять значение функции Эйлера, которое в общем случае требует факторизации, т. е. разложения чисел
на простые множители. Даже это обстоятельство показывает, что обратное преобразование чисел из СОК в позиционную систему счисления приводит к большому числу вычислительных операций с высокой точностью, а именно этого нам хотелось бы избежать прежде всего. Поэтому, чтобы найти действительно пригодный для практического применения метод перехода от к А, необходимо иметь другое доказательство китайской теоремы об остатках. Такое доказательство предложено в 1958 г. Х. Л. Гарнером. Оно основано на использовании 
констант 
, где 
. (5.4)Константы
можно вычислить с помощью расширенного алгоритма Евклида, который по заданным i и j позволяет определить числа a и b такие, что 
, и можно положить 
. В частности, для величины, обратной к 
по модулю , легко получить сравнительно простую формулу
, где 
и
. Действительно, если 
, то 
. Поэтому при 
имеем 
; а так как эти последние величины расположены между нулём и 
, должно быть 
.Тогда
Вернёмся к общему случаю. Так как
, удовлетворяют условиям (5.4), то можно выполнить присваивания 
, 
, 
, (5.5) 
.Тогда число
(5.6)будет удовлетворять условиям
, 
для 
. (5.5)