Основы модулярной арифметики

Fundamentals 
oF modular arithmetic

Practical course 

Stavropol
Publisher
North Caucasus Federal University
2023

UDC 004.942 (075.8)
BBK  22.19 ya73

F 75

Published by the decision 
of the Editorial and Publishing Council 
North Caucasus Federal 
University

© North Caucasus 
Federal University, 2023

F 75      Fundamentals of modular arithmetic: practical course / author-

comp.: A. S. Ionisyan, A. V. Shaposhnikov. – Stavropol: Publisher 
NCFU, 2023. – 121 p.

Modular arithmetic (a system of residual classes) and effective 
mathematical methods and algorithms for performing basic arithmetic 
operations (transfers to decimal and binary number systems and vice versa, 
addition, subtraction, multiplication, comparison, and case) are considered. 
Specific computational examples are given. There are a large number of 
tasks for self-checking.
It is intended for undergraduates studying in the direction of training 
01.04.02 Applied Mathematics and computer Science, the direction 
(profile) «Mathematical modeling», as well as for schoolchildren, students, 
undergraduates, postgraduates and other persons interested in high-
performance computing.
UDC  004.942 (075.8)
BBK  22.19 ya73

Authors-compilers:
Candidate of Physical-Mathem. Sciences, 
Associate Professor A. S. Ionisyan,
Candidate of Technical Sciences, Associate Professor A. V. Shaposhnikov

Reviewers:
Doctor of Physical/Mathematical Sciences, Professor G. V. Shagrova
(North Caucasus Federal University)
Candidate of Technical Sciences, Associate Professor R. V. Kron
(Stavropol State Agrarian University)

ОснОвы 
мОдулярнОй арифметики

Практикум 

Ставрополь
Издательство
Северо-Кавказского федерального университета
2023

УДК  004.942 (075.8)
ББК  22.19 я73

О 75

Печатается по решению 
редакционно-издательского совета 
Северо-Кавказского 
федерального университета

© Северо-Кавказский 
федеральный университет, 2023

О 75        Основы модулярной арифметики: практикум / авт.-сост.: 

А. С. Ионисян, А. В. Шапошников. – Ставрополь: Изд-во СКФУ, 
2023. – 121 с.

Рассмотрена модулярная арифметика (система остаточных классов) 
и эф-фективные математические методы и алгоритмы выполнения 
базовых арифметических операций (переводы в десятичную и двоичную 
системы счисления и обратно, сложение, вычитание, умножение, 
сравнение, деле-ние). Приведены конкретные вычислительные примеры. 
Для самопроверки имеется большое количество задач.
Предназначено для студентов-магистрантов, обучающихся по на-
правле-нию подготовки 01.04.02 Прикладная математика и информатика, 
направ-ленности (профилю) «Математическое моделирование», 
а также для школьников, студентов, магистрантов, аспирантов и прочих 
лиц, интере-сующихся высокопроизводительными вычислениями.

УДК 004.942 (075.8)
ББК 22.19 я73

Авторы-составители:
канд. физ.-мат. наук, доцент А. С. Ионисян,
канд. техн. наук, доцент А. В. Шапошников

Рецензенты:
д-р физ.-мат. наук, профессор Г. В. Шагрова
(Северо-Кавказский федеральный университет)
канд. техн. наук, доцент Р. В. Крон
(Ставропольский государственный аграрный университет)

сОдерЖание

Предисловие ........................................................................................................6

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

2.
Операция сложения чисел в СОК ...............................................27

3.
Операция вычитания чисел в СОК  ............................................32

4.
Операция умножения чисел в СОК  ...........................................38

5.
Перевод чисел из десятичной и двоичной систем
счисления в СОК  .............................................................................45

6.
Обобщенная позиционная система счисления  .......................56

7.
Перевод чисел из СОК в десятичную и двоичную
системы счисления  .........................................................................68

8.
Операция сравнения чисел в СОК  .............................................76

9.
Операция деления чисел в СОК  ..................................................83

10. Обнаружение и исправление ошибок в СОК-числах  ............96

11. Представление отрицательных чисел в СОК  .........................102

12. Комплексная арифметика в СОК  ..............................................107

Литература  ......................................................................................................119

- 6 -

Спутниковые и радиорелейные системы передачи данных

ПРЕДИСЛОВИЕ

Цель и задачи практикума. Практикум «Основы модулярной 
арифметики» предназначен для широкого круга читателей, 
интересующихся современными высокопроизводительными 
вычислениями.
Целью освоения практикума является формирование у читателя 
теоретических знаний, практических навыков и умений в 
использовании современных высокопроизводительных вычислений 
в организации информационных процессов в различных 
сферах.
Основной задачей изучения практикума является формирование 
у студентов знаний, умений и навыков, достаточных 
для создания несложного арифметико-логического устройства 
(АЛУ) выполнения основных арифметических операций над 
сверхдлинными неотрицательными целыми числами. 
Реализуемые компетенции.
ПК-1. Способен проводить научные исследования и получать 
новые научные и прикладные результаты самостоятельно 
и в составе научного коллектива на основе существующих методов 
в конкретной области про-фессиональной деятельности
ПК-7. Способен управлять информацией с использованием 
цифровых средств и алгоритмов обработки данных для решения 
задач профессио-нальной деятельности
Результаты изучения методов и алгоритмов высокопроизводительных 
вычислений в СОК
Знать: способы быстрого перевода чисел из двоичной и десятичной 
систем счисления в СОК и обратно, алгоритмы сложения, 
вычитания, умножения, деления и сравнения чисел в СОК, 
обобщенную позиционную систему счисления.
Уметь: реализовывать высокопроизводительные арифметические 
ал-горитмы в СОК на ЭВМ и системах программируемой 
логики на языках Pascal и VHDL (синтезируемое подмножество).

- 7 -

Предисловие

Владеть: методами реализации высокопроизводительных 
арифметиче-ских алгоритмов в СОК на ЭВМ и системах программируемой 
логики на языках Pascal и VHDL (синтезируемое 
подмножество).
Рекомендуемое программное обеспечение (программное 
обеспечение, кроме операционной системы Windows является 
бесплатным и свободно распространяемым)
1.
Операционная система - Windows (версия не менее 7),
Linux (Mint не ниже 20)
2.
Текстовый редактор с возможностью компиляции и запуска 
программ на языке программирования Pascal – Geany
(версии не ниже 1.0)
3.
Компилятор языка программирования Pascal – FreePascal
(версии не ниже 3.0)
4.
Среда разработки и отладки программ с графическим
пользователь-ским интерфейсом на языке FreePascal –
Lazarus (версия не ниже 2.0)
5.
Среда разработки и отладки аппаратуры на языке VHDL –
Xilinx ISE 14.7 (Webpack edition).
Рекомендуемое материально-техническое обеспечение 
Исправная ЭВМ с производительностью, достаточной для 
написания и отладки программ в рамках тем данного практикума. 
Рекомендуется наличие выхода в глобальную информационную 
сеть «Интернет» со скоростью доступа, достаточной для 
комфортной работы.
К каждому занятию приведены тема занятия, указаны знания, 
умения и навыки, формируемые на занятии в рамках формируемых 
компетенций. Далее идет теоретическая часть, являющаяся 
кратким обзором лекционного материала по теме. Для 
проверки освоения и закрепления материала приведены практические 
задания. Студентам рекомендуется выбрать свой вариант 
для решения задания и придерживаться его на протяжении всего 
курса.

- 8 -

Спутниковые и радиорелейные системы передачи данных

1.
МОДуЛяРная аРИфМЕтИка

Цель занятия: получение базовых математических знаний, 
умений и навыков, подводящих к модулярной арифметике.
Знания и умения, приобретаемые студентом в результате освоения 
темы, формируемые компетенции или их части: ПК-1, 
ПК-7.
В результате освоения темы обучающийся должен
•
знать: что такое множество, декартово произведение
множеств, отношение на множествах, функция, алгебраическая 
операция, нейтральный, противоположный и 
обратный элементы, алгебраическая структура «поле», 
конечное поле Галуа, первообразный корень, индекс, ортогональные 
базисы, ортогональные числа, система остаточных 
классов (СОК).
•
уметь: для полей Галуа, заданных простыми числами
создать просмотровые таблицы сложения, противоположных 
элементов, умножения,  обратных элементов, 
индексов, антииндексов, значений ортогональных чисел.
•
владеть: базовыми знаниями, умениями и навыками по
модулярной арифметике.

Теоретическая часть

Для счета за последние несколько тысяч лет человечество 
придумало много различных способов, начиная от примитивного 
складывания камешков в кучки и до сложных форматов представления 
вещественных чисел в упакованных форматах.
При этом, когда появились ЭВМ, выяснилось, что их возможности 
счета ограничены. Так, в большинстве языков программирования 
отделяют 8-битные числа (байты), 16-битные числа 
(машинные слова), 32-битовые числа (двойные машинные слова), 
64-битовые числа (длинные машинные слова). Для реализации 
криптографических методов обработки информации активно 
используются 256-битовые числа.

- 9 -

Практическая работа 1

Несколько особняком стоит обработка вещественных чисел. 
Математические сопроцессоры x86-подобных ЭВМ, как правило, 
представляют вещественные числа в 80-битном формате. 
Начиная с появления технологии MMX и далее, микропроцессоры 
упаковывают числа в большие информационные массивы, 
зачастую используя для этого регистры математического сопроцессора 
и обрабатывают такой массив одной командой, что, несомненно, 
ускоряет обработку, например, мультимедийной информации.

Существенным является факт, что с увеличением битовой длины 
числа, скорость его обработки замедляется. Причем, если для 
операций сложения/вычитания зависимость, в целом, линейная, 
то для операции деления – зависимость, в лучшем случае имеет 
характеристику O(n*log(n)), где n – длины сомножителей в битах. 
Операция деления до сих пор стоит особняком и считается одной 
их самых медленных арифметических операций.
Долгое время считалось, что наиболее быстро ЭВМ обрабатывают 
числа длиной 8 бит. Однако, более глубокое изучение 
архитектуры современных микропроцессоров показало, что на 
скорость обработки длина в битах чисел стандартного типа (int, 
word, long) влияет мало, так как внутренние структуры арифметико-
логического устройства микропроцессоров, чаще всего 
оптимизированы для проведения расчетов над 32 и 64-битовыми 
числами.
В 1830 году Эварист Галуа опубликовал работу, качественно 
изменившую подход к обработке числовой информации второй 
половины 20-го века. А именно, ранее, вполне обоснованно считалось, 
что множество целых чисел потенциально бесконечно в 
обе стороны для операций сложения, вычитания и умножения. 
Как показал Галуа, можно сконструировать множества, состоящие 
из небольшого конечного числа элементов-чисел и ввести 
для них групповые операции сложения, умножения так, что 
результат выполнения этих операций будет также находиться 
внутри этого множества, то есть образовывать алгебраическую 
структуру «поле». Если использовать для вычислений несколько 

- 10 -

Спутниковые и радиорелейные системы передачи данных

таких полей одновременно, то получается весьма эффективная 
методика, получившая название «Система остаточных классов» 
(СОК, RNS (англ.)).
Начнем изучение технологии высокопроизводительных вычислений 
в системе остаточных классов с подводящей математической 
теории. Сведения, излагаемые в данном разделе будут 
по возможности простыми, тем не менее предполагается наличие 
знаний по математике на уровне не ниже начальной школы.
Будем понимать под множеством (set) – совокупность объектов 
произвольной природы, объединенных неким общим 
свойством. Обозначать множества будем заглавными буквами 
латинского алфавита A, B, C, и т. д.  Объекты-элементы множеств 
будем обозначать строчными буквами латинского алфавита 
a, b, c, и т. д. Если букв латинского алфавита будет не 
хватать, то воспользуемся индексацией A1, A2, b1, b2 и т. п. Наконец, 
следуя правилам эффективного программирования, будем 
использовать «говорящие имена» для обозначения множеств и 
их элементов. Например, «PRIMES» – для обозначения массива-
множества простых чисел или «current» – для обозначения 
текущего обрабатываемого элемента множества. Конечный же 
смысл переменных будем раскрывать в комментариях к коду.
Количество элементов множества называется его мощностью. 
Существуют как конечные множества (finite set) с мощностью, 
выражаемой натуральным числом, так и бесконечные 
множества, глубокое изучение которых приводит к весьма занимательным 
математическим курьезам (одним из таких курьезов 
является расчет суммы натурального ряда).
Множество, не содержащее ни одного элемента называется 
пустым или нуль-множеством.
Над множествами, как правило, определены операции объединения (
union), пересечения (intersect), разности (subtract), дополнения 
до некоторого  супермножества (not), симметрической разности 
и т. п., позволяющие строить новые множества из уже заданных.
Самыми известными множествами, пожалуй являются множество 
натуральных чисел N, целых чисел Z, рациональных чисел 
Q, действительных чисел R, комплексных чисел C и т. п.

- 11 -

Если множество состоит из элементов, каждый из которых, 
в свою очередь принадлежит одному, возможно более мощному 
множеству, то такое множество называется подмножеством,  
а более мощное множество – надмножеством.
Пример.
A ={1, 2, 3}, B = {0, 1, 2, 3, 4, 5}. A – подмножество B.
Два множества считаются равными, если они являются подмножествами 
друг друга.
В данной работе элементы множеств – это числа (чаще всего 
неотрицательные целые числа).
Коснемся вопроса задания множеств.
Множества можно задавать:
1)  Непосредственным перечислением его элементов
A = {0, 1, 2, 3}
2)  Указанием группового свойства
A = {a: a = 0..3}
3)  Генерация элементов множества алгоритмом
A = {a: for a: = 0 to 3 do yield a;}
Далее, нам потребуется понятие упорядоченной пары.
Под упорядоченной парой будем понимать пару элементов 
(a, b), где первый элемент принадлежит множеству A, а второй 
элемент принадлежит множеству B. Множество всех возможных 
упорядоченных пар элементов множеств A и B, соответственно, 
назовем декартовым квадратом (cartesian product).
Пример.
A = {0, 1, 2}, B = {W, B}
тогда AxB = {(0, W),(1, W),(2, W),(0, B),(1, B),(2, B)}
Из декартова произведения можно вычленить любое его подмножество. 
Полученное подмножество называется «отношением».
Пример.
A = {0, 1, 2, 3}, B = {3, 4}
R = {(0,3), (0,4), (1,3), (1,4), (2,3), (2,4)} – отношение «меньше» 
на множестве декартова квадрата AxB (каждый первый элемент 
упорядоченной пары строго меньше соответствующего 
второго элемента упорядоченной пары).

Практическая работа 1