Задание 8: использование системы GAP

Указания

Часть 1 (тренировочная)

  • Использовать сценарий пакета GAP для выполнения предыдущего задания.

Часть 2 (индивидуальная)

  1. Реализовать алгоритм восстановления рациональной функции z = s / tF (X), deg(s) < deg(t) по заданному целому числу k ≥ deg(t) и 2 k старших коэффициентов обратного ряда Лорана для z.
  2. Реализовать схему восстановления вектора (y1, y2, ..., yk), переданного с ошибками в максимум l элементах, при помощи кода Рида–Соломона.
  3. Реализовать схему разделения секрета между несколькими сторонами так, чтобы никакая коалиция из k или меньше сторон могла бы его восстановить, в то время как коалиция из k + 1 сторон могла бы. При этом если минимум k сторон коррумпированы, любая коалиция из 3 k + 1 сторон (возможно, включающая коррумпированных участников) могла бы восстановить секрет.
  4. Реализовать схему восстановления вектора при помощи свёрнутого кода Рида–Соломона.
  5. Реализовать процедуры шифрования и расшифрования сообщения по алгоритму RSA.
  6. Реализовать алгоритм перемножения многочленов длины l максимум над нетривиальным полем за время O(llog23).
  7. Реализовать схему Миньотта для разделения секретной информации группой участников.
  8. Реализовать ρ-алгоритм Полларда для факторизации целых чисел.
  9. Реализовать алгоритм Диксона для факторизации целых чисел.
  10. Реализовать алгоритм факторизации целых чисел с помощью эллиптических кривых.
  11. Реализовать алгоритм вычисления преобразования Фурье методом простых множителей (Гуда–Томаса).
  12. Реализовать схему Асмута–Блума для разделения секретной информации группой участников.
  13. Для заданного qQ найти его представление в виде непрерывной дроби. Проверить правильность полученного представления.
  14. Требуется закодировать сообщение длины m бит серией из l-битных блоков (m делится на l) с возможностью восстановления исходного сообщения при искажении не более h блоков при помощи алгоритма Рида–Соломона. Определить количество требуемых для кодирования блоков и реализовать процедуры кодирования и декодирования.