Система — остаточные классы

Cтраница 1

Система остаточных классов позволяет существенно улучшить параметры вычислительных машин по сравнению с машинами, построенными на той же физико-технологической базе, но в позиционной системе счисления, а также получить новые, более прогрессивные конструктивные и структурные решения.  [1]

Система остаточных классов дает возможность эффективно распараллелить арифметические операции, которые называются модульными. Кроме модульных операций часто выполняются и операции, носящие позиционный характер.  [2]

Система остаточных классов допускает расширение или сокращение набора оснований без искажения при этом исходного числа. Например, для представления числа используется три основания — pi, Р2, Рз; тогда число изображается в виде A ( ai, а %, с з); если ввести новые основания — р4 и рз, то изображ: ение числа изменится и будет иметь вид А ( а, а %, сез, 4, б) — Аналогичным образом можно сократить набор оснований. Расширение оснований увеличивает диапазон и разрядность представления чисел, а сокращение — уменьшает. Образование остатков о производится независимо друг от друга. Последнее и определяет данную систему счисления как непозиционную; каждый разряд содержит в себе информацию обо всем числе. При выполнении сложения, вычитания и умножения каждая цифра результата зависит лишь от соответствующих цифр операндов.  [3]

Система остаточных классов является фундаментальной для теории и практики машинной арифметики и позволяет ставить и решать новые задачи, недоступные для позиционных систем счисления.  [4]

Система остаточных классов позволяет распараллелить весь процесс обработки данных, что подтверждает вывод многих авторов о том, что в настоящее время основное внимание уделяется способам параллельной обработки.  [5]

Сочетание системы остаточных классов и нейронных сетей, которые дополняют друг друга, вызывает интерес по той причине, что легко реализовать принципы обменных операций между быстродействием, точностью и надежностью с целью создания отказоустойчивого нейрокомпьютера.  [6]

Использование системы остаточных классов для кодирования числовой информации дает возможность эффективно распараллеливать алгоритмы выполнения элементарных арифметических операций автономных и неавтономных как П — задач, так и не П — задач, что и обеспечивает высокую производительность и надежность. В [4] показано, что в системе остаточных классов были созданы специализированные ЭВМ с уникальной для машин второго поколения производительностью 1 25 миллионов операций в секунду.  [7]

Применение системы остаточных классов обеспечивает независимую и параллельную обработку каждого разряда числа, что и определяет структуру нейрокомпьютера.  [8]

Кроме того, система остаточных классов является мощным методом повышения надежности. Показано [116], что система остаточных классов с двумя контрольными основаниями позволяет сохранить работоспособность машины при отказах двух элементов. Но и третий, и четвертый отказы не выводят машину из строя. СОК, является исключительно живучей, приближаясь в этом смысле к биологическим системам. К тому же следует отметить, что при переходе на БИС различия в сложности позиционных и непозиционных ЭВМ становятся незначительными.  [9]

Основной теоретико-числовой базой системы остаточных классов ( СОК) является теория сравнений. Вопросы теории сравнений были разработаны выдающимся отечественным математиком П. Л. Чебы-шевым и изложены в его классическом труде Теория сравнений. Система остаточных классов дает нестандартное представление для чисел и используется для повышения эффективности операций над кодами в остатках. Дело в том, что в данной системе числа представляются своими остатками от деления на выбранную систему оснований и все рациональные операции могут выполняться параллельно над цифрами каждого разряда в отдельности.  [10]

При выборе модулей системы остаточных классов необходимо учитывать вышеперечисленные свойства простых чисел. Так, при построении многоступенчатой системы остаточных классов можно рекомендовать для выбора модулей высших ступеней простые числа Мерсенна и Ферма, что упростит реализацию арифметических устройств и сократит время выполнения арифметической операции не только в табличном варианте, но и в регистровом варианте арифметических устройств. Кроме того, числа Мерсенна и Ферма можно использовать в качестве модулей системы СОК при байтовом кодировании информации.  [11]

Сочетание корректирующих свойств системы остаточных классов и адаптивных свойств искусственных нейронных сетей позволяет реализовать непозиционный нейрокомпьютер с реконфигурируемой в динамике вычислительного процесса структурой.  [12]

Для упрощения вычислений в системе остаточных классов желательно, чтобы модули р ( / г Е [1, ]) имели как можно более простое представление. Однако в полной мере экономия в вычислениях может быть достигнута лишь в том случае, когда обработка информации выполняется с помощью специальных вычислительных средств, эффективно представляющих модулярную арифметику.  [13]

Перспективным является представление чисел в системе остаточных классов, что позволяет повысить скорость выполнения А. Широко распространен микропрограммный принцип управления, с помощью к-рого сравнительно просто осуществляются: извлечение корня, возведение в степень, вычисление тригонометрия, функций, а также составные операции, что расширяет состав А.  [14]

Применение принципов построения ПЗУ в системе остаточных классов, с троичным представлением информации, записью информации блочными ( геометрическими) кодами, матричным кодированием информации и кодированием кодом позиций переходов позволяет уменьшить число операций и время записи информации, увеличить плотность ее записи и, в некоторых случаях, быстродействие устройства, а также повысить информационную содержательность и эффективность ПЗУ.  [15]

Страницы:      1    2    3    4

Нахождение обратных чисел в модульной арифметике (по сложению и умножению)

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

Модулярная арифметика часто изучается в школе как "арифметика часов". Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов утра следующего дня:

3 + 14 = 5 (mod12)

или

(3+14) mod 12 = 5

Это арифметика по модулю 12.

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

a º b(mod n)

читается так: "а сравнимо с b по модулю n". Это соотношение справедливо для целых значений а, b и n ¹ 0, если, и только если

a = b + k * n

для некоторого целого k.

Отсюда, в частности, следует

n |(a – b)

Это читается как "n делит (а — b)".Если

a º b(mod n)

то b называют вычетом числа а по модулю n.

Операцию нахождения вычета числа а по модулю n

a(mod n)

называют приведением числа а по модулю n или приведением по модулю.

В нашем примере

(3+ 14) mod 12 = 17 mod 12 = 5

или

17 º 5 (mod 12),

число 5 является вычетом числа 17 по модулю 12.

Набор целых чисел от 0 до (n-1) называют полным набором вычетов по модулю п. Это означает, что для любого целого а(а>0) его вычет г по модулю n есть некоторое целое число в интервале от 0 до (n-1), определяемое из соотношения

r = a – k * n,

где k-целое число.

Например, для n =12 полный набор вычетов:

{0,1,2, …,11}

Обычно предпочитают использовать вычеты

r Î {0,1,2,…,n-1}

но иногда полезны вычеты в диапазоне целых:

 

Заметим, что

-12(mod 7) º -5(mod 7) º 2(mod 7) º 9(mod 7) и т.д.

Модулярная арифметика аналогична во многом обычной арифметике: она коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по модулю n с использованием операций сложения и умножения образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности.

Фактически мы можем либо сначала приводить по модулю n, а затем выполнять операции, либо сначала выполнять операции, а затем приводить по модулю n, поскольку приведение по модулю n является гомоморфным отображением из кольца целых в кольцо целых по модулю n:

(a + b) mod n = [a(mod n) + b(mod n )] mod n,

(a — b) mod n = [a(mod n) — b(mod n )] mod n,

(a * b) mod n = [a(mod n) * b(mod n )] mod n,

[a * (b + c)] mod n = {[a * b(mod n)] + [a * c(mod n)]} mod n.

Криптография использует множество вычислений по модулю n, потому что задачи типа вычисления дискретных логарифмов и квадратных корней очень трудны. Кроме того, с вычислениями по модулю удобнее работать, потому что они ограничивают диапазон всех промежуточных величин и результата.

Для модуля n длиной k бит промежуточные результаты любого сложения, вычитания или умножения будут не длиннее 2k бит. Поэтому возведение в степень в модулярной арифметике можно выполнить без генерации очень больших промежуточных результатов.

Вычисление степени числа а по модулю n

a^x mod n

можно выполнить как ряд умножений и делений. Существуют способы сделать это быстрее.

Система остаточных классов

Поскольку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз приведение по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более).

Например, если нужно вычислить

a⁸ mod n,

не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

(a * a * a * a * a * a * a * a) mod n

Вместо этого выполняют три малых умножения и три малых приведения по модулю:

((a² mod n)² mod n)² mod n.

Тем же способом вычисляют

a¹⁶ mod n = (((a² mod n)² mod n)²mod n)² mod n.

 

Вычисление

a^x mod n.

где х не является степенью 2, лишь немного сложнее. Двоичная запись числа х позволяет представить число х как сумму степеней 2:

x = 25₍₁₀₎ ® 1 1 0 0 1₍₂₎, поэтому 25 = 2⁴+ 2³ + 2⁰

Тогда

a²⁵ mod n = (a * a²⁴) mod n = (a * a⁸ * a¹⁶) mod n = a * ((a²)²)² * (((a²)²)²)² mod n = ((((a² * a)²)²)² * a) mod n.

При разумном накоплении промежуточных результатов потребуется только шесть умножений:

(((((((a² mod n) * a) mod n)² mod n)² mod n)² mod n) * a) mod n

Этот метод уменьшает трудоемкость вычислений до 1,5xk операций в среднем, где k-длина числа в битах [123].

Поскольку многие алгоритмы шифрования основаны на возведении в степень по модулю n, целесообразно использовать алгоритмы быстрого возведения в степень.

 

 



1. Сравнительный анализ методов вычисления позиционных характеристик чисел в системе остаточных классов

Джурабаев Анвар
студент 2 курса
группы ПМИ-б-о-16-2

2.

Что такое система остаточных классов

Это непозиционная система счисления. СОК основывается на
теории сравнений и была предложена в 50-е годы двадцатого века.
Теорию вычислений в СОК иногда называют модулярной
арифметикой, основной теоремой которой является Китайская
теорема об остатках (КТО, Chinese remainder theorem – CRT).

3. Операция сравнения

Пусть набор оснований будет равен (3;5;7)
(0;2;6) =12 < (2;1;5) =26
1.
2.
Восстановления числа в ПСС
1.1 КТО
1.2 ОПСС
1.3 КТО в ОПСС
1.4 КТОд
Вычислить позиционную характеристику чисел

4. Позиционная характеристика

Под позиционной характеристикой числа в СОК
понимается такая функция которая зависит только от
остатков на основе которой можно определить
взаимное расположения числа с другими числами на
числовой прямой
1.

КТО
2. Функция ядра
3. КТОд

5. Основная критерия для сравнения чисел с помощью ПХ

160
140
120
100
80
60
40
20
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Для набора модулей (3;5;7)
22
23
24
25
26
27
28
29
30

6. Китайская теорема об остатках

X
n
P
i
i 1
1
pi
Pi xi
P

7. Функция ядра

X
C ( X ) = i
p
i =1
i
n

8. Китайская теорема об остатках с дробями

X
P
n
i 1
Pi
1
pi
pi
xi
1
n
k p
i 1
i
i
1

9. Сравнительный анализ

300
250
t(мс)
200
150
100
50
0
8
16
32
64
128
разрядность(бит)
КТО_4
ФЯ_4
КТОд_4
КТО
ФЯ
КТОД
256

10. Вывод Наиболее эффективной методом для вычисления позиционной характеристики числа является КТОд.

11. Список литературы. 1. Червяков Н. И. Методы, алгоритмы и техническая реализация основных проблемных операций, выполняемых в

системе
остаточных классов //Инфокоммуникационные технологии. –
2011. – Т. 9., №. 4. – С. 4-12.
2. Chervyakov N.I., Molahosseini A.S., Lyakhov P.A., Babenko M.G.,
Deryabin M.A. Residue-to-binary conversion for general moduli sets
based on approximate Chinese remainder theorem // International
Journal of Computer Mathematics. – 2017. – Т. 94. – №. 9. – С. 18331849.
3. Дерябин М.А, Разработка математических моделей и методов
снижения энергопотребления в системах мобильной связи на
основе системы остаточных классов: дис… канд. техн. наук:
Ставрополь. – 2016. С. 66-113

2.8.

Обзор модулярной арифметики

Поскольку проверки на четность используются в дальнейшем довольно часто, следует иметь ясное представление об арифметике, лежащей в основе соответствующих преобразований. Как было показано, сложение по модулю 2 является той арифметической операцией, которая применяется в простых проверках на четность, и оно совпадает с логическим сложением (исключающее ИЛИ). Правила сложения таковы:

системе <нет других чисел, отличных от 0 и 1. Если действовать на павилам обычной арифметики, то нужно разделить результат и взять остаток. Когда позже будет рассматриваться

алгебра линейных уравнении и многочленов с коэффициентами, являющимися числами в системе счисления но модулю 2, то для сложения будет использоваться та же таблица. При умножении применяются следующие правила:

Таким образом, умножение совпадает с логическим И.

Иногда будут применяться вычеты по модулю, отличному от 2. Например, в предыдущем разделе использовались вычеты по модулю 37. В общих чертах теория для любого простого основания (например, 37) очень похожа на теорию для основания 2, так что подробности здесь можно опустить. Для понимания соответствующей арифметики и алгебры следует лишь внимательно прочесть начало этого раздела и внести небольшие изменения. При сложении и вычитании по модулю следует разделить каждое число на и взять положительный остаток.

При умножении по модулю (когда не простое число) следует быть более осторожным. Предположим, что числа сравнимы с числамиа и по модулю Это означает, что или для некоторых целых чисел Для произведения имеем

Рассмотрим теперь частный случай: Имеем Но ни а, ни не равны 0! Важное свойство умножения, состоящее в том, что если произведение равно 0, то по крайней мере один из сомножителей равен 0, выполнение только для простых оснований. Именно это определяет важность простых оснований. Теперь видно, почему число 37 было столь удобным в разд. 2.7. Читатель должен хорошо разобраться в модулярной арифметике, особенно для простого основания, поскольку в гл. 11 появится более сложная задача построения соответствующей модулярной алгебры. Поэтому в следующем разделе дается еще один пример кодирования такого типа.

1.

Определение модуля:

Модулем числа а называется расстояние (в единичных отрезках) от начала координат до точки А с координатой а.

Пример.

Модуль числа 7 равен 7, так как точка D с координатой 7 удалена от начала отсчета на 7 единичных отрезков.

Модуль числа -6 равен 6, так как точка С с координатой 6 удалена от начала отсчета на 6 единичных отрезков. Пишут:

   

2. По определению модуля, модуль — это расстояние.

А так как расстояние не может быть отрицательным числом, то и модуль не может быть отрицательным числом.

3. Модуль положительного числа равен самому числу.

Например,

   

4. Модуль отрицательного числа равен противоположному числу.

Например,

   

5. Модуль нуля равен нулю:

   

6. Противоположные числа имеют равные модули:

   

Например,

   

Из определения модуля: