Задание 4 (индивидуальное): применение алгоритма Евклида

Указания

Для каждого из заданий найти график времени работы алгоритма в зависимости от длины входных данных. Для решения задания необходимо использовать реализацию алгоритма Евклида из задания 3.

Варианты

  1. Найти все целочисленные решения заданного Диофантового уравнения:
    a1x1 + a2x2 + ... + anxn = k
    при заданных ∀ i ai, xi, kZ.
  2. Выполнить декомпозицию заданной дроби на все возможные элементарные слагаемые:
    a / b = a1 / b1 + a2 / b2 + ... + an / bn
    при заданных a, bZ.
  3. Для заданного pZ проверить условие p ≡ 1 (mod 4) и если это так, найти числа r, tZ, такие, что:
    p = r2 + t2
  4. Реализовать процедуру восстановления рационального числа s / tQ по заданной последовательности цифр его десятичного представления:
    s / t = 0,z1z2...zk
    при условии, что 10k > 2 M2, где M — верхняя граница знаменателя (t < M).
  5. Требуется закодировать сообщение длины m бит серией из l-битных блоков (m делится на l) с возможностью восстановления исходного сообщения при искажении не более h блоков при помощи алгоритма Рида–Соломона. Определить количество требуемых для кодирования блоков и реализовать процедуры кодирования и декодирования.
  6. Реализовать процедуры шифрования и расшифрования сообщения по алгоритму RSA.
  7. Для заданного qQ найти его представление в виде непрерывной дроби. Проверить правильность полученного представления.
  8. Реализовать схему Миньотта для разделения секретной информации группой участников.
  9. Реализовать ρ-алгоритм Полларда для факторизации целых чисел.
  10. Реализовать алгоритм Диксона для факторизации целых чисел.