Кодирование с открытым ключом

Список задач

В скобках указана сложность задачи по логарифмической шкале: увеличение оценки на 1 балл соответствует усложнению в 2 раза.

Решения всех задач должны использовать class BigInteger и работать для целых чисел произвольной длины.

1. Разложить число на 2 множителя методом Полларда, основанном на поиске цикла в рекуррентной последовательности. (1)
2. Разложить число на 2 множителя с помощью (p-1)-алгоритма Полларда. (2)
3. Реализовать процедуры кодирования и декодирования файла для заданного открытого (кодирование) и закрытого (декодирование) ключа в схеме RSA. Закодированный файл должен быть текстовым, т.е. содержать только ASCII-символы (русские буквы не являются ASCII-символами). (3)
4. Получить случайное простое число с заданным количеством десятичных цифр (в задачу входит реализация теста Рабина). (2)
5. Разложить целое число на множители методом Ленстра, использующим (p-1)-алгоритм Полларда на эллиптических кривых. (4)
6. Разложить число на множители методом квадратичного решета. (4)
7. Реализовать процедуры записи электронной подписи файла и проверки его подлинности, использующие схему кодирования с открытым ключом RSA. Процедура построения электронной подписи использует закрытый ключ, проверки — открытый ключ. Ключи заданы. (3)
8. Пусть число m есть произведение попарно взаимно простых чисел m₁, m₂, ..., m_k. Вычислить число x с заданным набором r₁, r₂, ..., r_k остатков от деления на m₁, m₂, ..., m_k (Китайская теорема об остатках). (2)
9. Реализовать класс BigReal со всеми арифметическими операциями, а также методами преобразования из строки (конструктор с аргументом типа String) и в строку (метод toString()). Число задается мантиссой и порядком, а также точностью (числом знаков мантиссы). Точность результата равна минимуму из точностей операндов. Реализовать стековый калькулятор длинных вещественных чисел. (3)
10. Для заданного простого числа p найти порождающий элемент мультипликативной группы поля вычетов по модулю p (как известно, эта группа циклическая). Такие элементы называют "первообразными корнями по модулю p", их используют для генерации псевдослучайных чисел. Элемент s является первообразным корнем по модулю p тогда и только тогда, когда для всякого простого делителя q числа (p-1) элемент s в степени (p-1)/q отличен от 1 по модулю p. (Задача требует разложения на множители числа p-1.) (4)
11. Вычислить log₂ длинного целого числа с заданной точностью. (Результат — обычное вещественное число типа double.) (1)
12. Вычислить квадратный корень длинного целого числа. Если число не является квадратом, то программа должна выдавать целую часть корня. (1)
13. Решить уравнение x²=s (mod p) в поле вычетов по модулю p. (3)