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

Июль 29, 2022

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

Содержание

2. Основанием смешанной системы счисления называется множество из r≥2 целых чисел n1,n2,…,nr, не обязательно взаимно простых. Если
3. Пусть n1,n2,…,nr – попарно взаимно простые числа. Пусть nj и Ci – обратные к Ni по
4. Формулы определения цифр z1= x1mod n1, z2= C2(x2-z1) mod n2, z3= C3(x3-(N2z2+z1)) mod n3, … zr=
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', заданные своими модулярными компонентами,
7. Определение цифр в позиционной системе счисления Пусть целое х задано модулярными компонентами. Мы хотим вычислить его
9. Скачать презентацию

Слайд 2

Основанием смешанной системы счисления
называется множество из r≥2 целых чисел

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

Слайд 3

Пусть n1,n2,…,nr – попарно взаимно простые числа. Пусть
nj и Ci

– обратные к Ni по модулю ni.
Рассмотрим целое число 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.

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

Слайд 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

Слайд 7

Определение цифр в позиционной системе счисления
Пусть целое х задано модулярными

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