Материал был изложен не в рамках одной лабораторной работы, а в цикле из семи лабораторных:

  • Лабораторная работа №1. Сложение, вычитание и сравнение длинных чисел.
  • Лабораторная работа №2. Умножение длинных чисел.
  • Лабораторная работа №3. Возведение в квадрат длинных чисел.
  • Лабораторная работа №4. Вычисление остатка длинных чисел.
  • Лабораторная работа №5. Модулярное умножение.
  • Лабораторная работа №6. Возведение длинных чисел в степень.
  • Лабораторная работа №7. Вычисление обратного по модулю.

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

Схема сдачи лабораторной работы выглядит следующим образом:

  • ознакомление с целью лабораторной работы
  • внимательное изучение теоретической части и приведенных примеров
  • ответ на контрольные вопросы для закрепления прочитанного материала.
  • выполнение практических заданий.

Все примеры и процедуры, реализующие алгоритмы «длинной» арифметики в лабораторных работах написаны на С++.

Обзор лабораторной работы №1.

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

В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется программно реализовать алгоритмы сложения, вычитания и сравнения «длинных» чисел. Язык реализации может быть произвольным.

Обзор лабораторной работы №2.

В данной лабораторной работе происходит ознакомление с алгоритмами умножения длинных чисел. В начале излагается идея умножения двух длинных чисел «в столбик», описывается сложность и недостатки приведенного алгоритма. Далее описывается более эффективный метод, известный как метод Карацубы, его преимущество над предыдущим. Следующим этапом в этой лабораторной является алгоритм умножения длинного числа на цифру, его описание и описание получаемого результата.

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

Обзор лабораторной работы №3.

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

В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется программно реализовать алгоритм возведения длинного числа в квадрат методом «треугольника». Язык реализации может быть произвольным.

Обзор лабораторной работы №4.

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

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

Обзор лабораторной работы №5.

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

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

Обзор лабораторной работы №6.

В данной лабораторной работе происходит ознакомление с алгоритмами возведения длинного числа в степень. Первоначально предлагается изучить идею бинарного алгоритма возведения в степень, его преимущества над алгоритм возведения в степень В путем В-1 ум­ножения. Далее этот же метод, но с использованием операции Монтгомери. Затем в лабораторной работе приводится обобщение бинарного алгоритма, а именно: k-арный алгоритм возведения в степень и k-арный алгоритм возведения в степень по модулю. Здесь приведены сложности этих алгоритмов, а также их преимущества и недостатки. Следующим этапом является вычисление степени с помощью заранее заготовленной таблицы: табличный алгоритм возведения в степень по модулю, к-арный табличный алгоритм возведения в степень и k-арный табличный алгоритм возведения в степень по модулю. Также как и для предыдущих примеров приведены сложности этих алгоритмов. В конце теоретической части предлагается изучить алгоритм одновременного вычисления произведения степеней.

В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется  реализовать процедуры бинарного алгоритма возведения в степень, бинарного алгоритма возведения в степень с использованием операции Монтгомери, k-арного алгоритма возведения в степень и бинарного алгоритма одновременного вычисления произведения степеней. Язык реализации может быть произвольным.

Обзор лабораторной работы №7.

В данной лабораторной работе происходит ознакомление с алгоритмами вычисления обратного по модулю. Первоначально приводятся общие сведения и необходимость применения данной процедуры. Далее предлагается изучить расширенный алгоритм Евклида, а также алгоритмы вычисления обратного С = A-1(mod В) и z = -a-1 (mod 2m).

В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется  реализовать процедуры расширенного алгоритма Евклида, вычисления обратного С = A-1(mod В), вычисления z = -a-1 (mod 2m). Язык реализации может быть произвольным.