Модулярная арифметика

1. Модулярная арифметика

Согласно китайской теореме об остатках для попарно взаимно
простых чисел n1,n2,…,nr имеются формулы, позволяющие
кодировать любое число из интервала [0, n) r–oй чисел из
0, n1 0, n2 0, nr , где n=n1·n2·…·nr. Если каждое из чисел ni
можно ввести в машину и обычные операции кольца Z/niZ также
могут быть реализованы на этой машине, то мы располагаем
арифметикой на [0, n), определенной так:
0
~ (0,…,0),
1
~ (1,…,1)
х~
(x mod n1,…, x mod nr),
(x+y) mod n
~ ((x+y) mod n1,…, (x+y) mod nr),
(x-y) mod n ~
((x-y) mod n1,…, (x-y) mod nr),
(xy) mod n ~
((xy) mod n1,…, (xy) mod nr),
хy -1 ~ ( xy -1mod n1,…, xy -1mod nr).

2.

Основанием смешанной системы счисления
называется множество из r 2 целых чисел
n1,n2,…,nr, не обязательно взаимно простых.
Если положим Ni n j и n=n1·n2·…·nr, то имеется
j i
биекция (взаимно однозначное соответствие):
0, n1 0, n2 0, nr 0, n ,
(z1 ,...,z r ) x =
r
z N
i
i
i=1
Обратное отображение определяется при помощи
евклидовых делений:
x=q1n1+z1, q1= q2n2+z2, … , qr-1= qrnr+zr.
В случае, когда все числа ni равны, получаем
обычную позиционную систему счисления
(смешанная система счисления, следовательно,
эта система, в которой основания варьируется).

3. Теорема 1 (формулы определения цифр).

Пусть n1,n2,…,nr – попарно взаимно простые числа. Пусть
Ni n j
nj и Ci – обратные к Ni по модулю ni.
j i
Рассмотрим целое число x, модулярные компоненты
которого x1,x2,…,xr тогда цифры x в системе со
смешанным основанием ni обозначим через zi ; они
находятся по формулам:
z1= x1mod n1,
z2= C2(x2-z1) mod n2,
z3= C3(x3-(N2z2+z2)) mod n3,
……………
zr= Cr(xr-(Nr-1zr-1+…+ N2z2+z1)) mod nr.

4. Формулы определения цифр

z1= x1mod n1,
z2= C2(x2-z1) mod n2,
z3= C3(x3-(N2z2+z1)) mod n3,
…
zr= Cr(xr-(Nr-1zr-1+…+ N2z2+z1)) mod nr.

5.

x1=z1,
x2=(z1+z2n1)mod n2,
x3=(z1+z2n1+z3n1n2)mod n3,
…
xr=(z1+z2n1+…+zrn1n2…nr-1)mod nr.

6.

Сравнение двух целых чисел
Пусть имеются два целых числа x и x', заданные
своими модулярными компонентами, и мы хотели
узнать, которое из этих чисел (можем считать, что они
оба лежат в [0,m)) больше, по возможности не вычисляя
явный вид этих чисел. Вычислим сначала цифры zi и zi',
соответствующие x и x' в смешанной системе
счисления, определяемой модулями. В этом случае x<x'
тогда и только тогда, когда наибольший вес i, на котором
различаются эти числа, таков, что zi<zi'.

7. Определение цифр в позиционной системе счисления

Пусть целое х задано модулярными компонентами. Мы
хотим вычислить его цифры в системе с основанием b.
По схеме Горнера
x mod b(…((zr mod)·nr-1+ zn-1 mod b)…)·n1+z1 mod b
(x-(x mod b))/b
Так мы получили первую цифру. И т.д.

8. Алгоритм умножения двух чисел

1. Находим последовательность наименьших простых
чисел, произведение которых больше произведения
этих двух. Обозначим их n1, …,nr.
2. Представим модулярное разложение выбранных
чисел a и b по n1,…,nr: a1,…, ar; b1,…, br.
3. Восстановим число x. Для этого вычислим z1,…, zr.
4. Определим последнюю цифру числа, используя
формулу x(j)= zi ∙ Ni.
5. Ищем модулярное представление числа
x' =(x – x0) /10:
x' =((x1 – x0) ∙y1 mod n1, (x2 – x0) ∙y2 mod n2,…, (xr – x0) ∙yr
mod nr). Если все модулярные представления равны
нулю, то вычисление закончено. Иначе переходим к
пункту 4.