В монографии излагаются основы модульной арифметики. Основное внимание уделяется вопросам перевода чисел из модульного представления в позиционное, сравнению чисел и определению переполнения при арифметических операциях. Приводится история развития компьютерных систем на основе модульной арифметики и примеры решения некоторых инженерных вопросов: расширения диапазона измерений интенсивности и устранения фазовой неоднозначности в задачах интерферометрии, голографии и структурированного освещения.
Монография будет интересна научным работникам, инженерам и студентам, специализирующимся в области прикладной математики, криптографических средств защиты информации, информационных систем, оптики и голографии.
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ ............................................................................................................................ 9
1. МОДУЛЬНАЯ АРИФМЕТИКА .................................................................................... 13
1.1. Основные понятия модульной арифметики .......................................................... 13
1.1.1. Сравнение по модулю..................................................................................... 14
1.1.2. Классы вычетов ............................................................................................... 15
1.1.3. Представление отрицательных чисел ........................................................... 15
1.1.4. Свойства сравнений ........................................................................................ 18
1.1.5. Системы сравнений ........................................................................................ 19
1.1.6. Арифметические операции в модульной арифметике ................................ 20
1.2. Переход от позиционного представления чисел к модульному .......................... 21
1.3. Переход от модульного представления чисел к позиционному .......................... 23
1.3.1. Переход от модульного представления к позиционному на основе
китайской теоремы об остатках ..................................................................... 24
1.3.2. Алгоритм Гарднера ......................................................................................... 26
1.3.3. Геометрический способ перевода чисел от модульного представления
к позиционному ............................................................................................... 28
1.4. Сравнение чисел и определение переполнения при арифметических
операциях .................................................................................................................. 44
1.4.1. Сравнение чисел при двух модулях .............................................................. 44
1.4.2. Сравнение чисел при трех модулях .............................................................. 46
1.5. Анализ переполнения чисел при сложении или умножении в модульном
представлении .......................................................................................................... 48
1.5.1. Анализ переполнения при сложении чисел, представленных
в системе остаточных классов при двух модулях ........................................ 49
1.5.2. Анализ переполнения при сложении чисел, представленных
в системе остаточных классов при трех модулях ........................................ 51
1.5.3. Переполнение при умножении модульных чисел ....................................... 52
1.6. Деление модульных чисел ...................................................................................... 53
1.6.1. Нахождение решений сравнений первой степени на основе теории
непрерывных дробей ...................................................................................... 53
1.6.2. Определение результата деления чисел в системе
остаточных классов ........................................................................................ 57
1.6.3. Деление в многомодульных системах .......................................................... 60
1.7. Нахождение наибольшего общего делителя модульных чисел .......................... 65
1.7.1. Алгоритм нахождения НОД с взаимным вычитанием ................................ 65
1.7.2. Алгоритм нахождения НОД делением ......................................................... 66
1.7.3. Нахождение наибольшего общего делителя в системе
остаточных классов с двумя модулями последовательным вычитанием .. 68
1.7.4. Нахождение наибольшего общего делителя в системе
многомодульных остаточных классов последовательным вычитанием ... 70
1.7.5. Обобщенный алгоритм для нахождения наибольшего
общего делителя .............................................................................................. 71
1.7.6. Обобщенный алгоритм для модульных чисел ............................................. 73
1.8. Возведение в степень по модулю ........................................................................... 73
1.8.1. Метод, использующий числа меньшей длины ............................................. 74
1.8.2. Метод вычислений, основанный на представлении степени
в двоичном виде .............................................................................................. 75
2. ИСТОРИЯ РАЗРАБОТКИ КОМПЬЮТЕРОВ, ОСНОВАННЫХ
НА МОДУЛЬНОЙ АРИФМЕТИКЕ .............................................................................. 77
3. АЛГОРИТМЫ ШИФРОВАНИЯ, ОСНОВАННЫЕ
НА МОДУЛЬНОЙ АРИФМЕТИКЕ .............................................................................. 81
3.1. Нахождение простых чисел .................................................................................... 83
3.1.1. Решето Эратосфена ......................................................................................... 83
3.1.2. Числа Мерсенна .............................................................................................. 84
3.1.3. Проект распределенных вычислений по поиску
простых чисел Мерсенна – GIMPS ............................................................... 87
3.2. Факторизация целых чисел ..................................................................................... 88
3.2.1. Метод факторизации Ферма .......................................................................... 89
3.2.2. Метод Крайчика – Ферма ............................................................................... 93
3.2.3. Квадратичное решето ..................................................................................... 96
3.3. Алгоритм шифрования RSA ................................................................................. 101
4. РАСШИРЕНИЕ ДИАПАЗОНА ИЗМЕРЕНИЙ ИНТЕНСИВНОСТИ ...................... 109
4.1. Использование методов структурированного освещения
для определения профиля ..................................................................................... 109
4.2. Использование методов пошагового фазового сдвига
для определения фазы ........................................................................................... 111
4.3. Источники погрешностей при использовании методов
пошагового фазового сдвига в проекционных методах ..................................... 115
4.4. Снижение нелинейных искажений интенсивности ............................................ 116
4.5. Расширение диапазона измерений интенсивности на основе
модульной арифметики ......................................................................................... 124
5. РАСШИРЕНИЕ ОБЛАСТИ ФАЗОВОЙ НЕОДНОЗНАЧНОСТИ
ПРИ ИНТЕРФЕРЕНЦИОННЫХ И ПРОЕКЦИОННЫХ ИЗМЕРЕНИЯХ
НА ОСНОВЕ МОДУЛЬНОЙ АРИФМЕТИКИ .......................................................... 129
5.1. Устранение фазовой неоднозначности методом развертывания ...................... 130
5.2. Устранение фазовой неоднозначности на основе решения
системы сравнений ................................................................................................ 133
5.3. Коррекция ошибочных значений ......................................................................... 136
5.4. Расширение области фазовой неоднозначности в методах
структурированного освещения ........................................................................... 142
ЗАКЛЮЧЕНИЕ ................................................................................................................. 147
БИБЛИОГРАФИЧЕСКИЙ СПИСОК .............................................................................. 148