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

Список задач

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

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

1. Реализовать вероятностный тест простоты Рабина. (1)

2. Разложить число на 2 множителя методом Поллака 1. (1)

3. Разложить число на 2 множителя методом Поллака 2. (2)

4. Реализовать процедуры кодирования и декодирования
   файла для заданного открытого (кодирование) и
   закрытого (декодирование) ключа в схеме RSA.
   Закодированный файл должен быть текстовым, т.е.
   содержать только ASCII-символы (русские буквы не
   являются ASCII-символами). (3)

5. Получить случайное простое число с заданным количеством
   десятичных цифр (в задачу входит реализация теста Рабина). (2)

6. Разложить число на множители методом квадратичного решета. (4)

7. Реализовать процедуры записи электронной подписи файла
   и проверки его подлинности, использующие схему кодирования
   с открытым ключом RSA. Процедура построения электронной
   подписи использует закрытый ключ, проверки -- открытый ключ.
   Ключи заданы. (3)

8. Пусть число m есть произведение попарно взаимно простых
   чисел m1, m2, ..., mk. Вычислить число x с заданным набором
   r1, r2, ..., rk остатков от деления на m1, m2, ..., mk
   (Китайская теорема об остатках). (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_2 длинного целого числа с заданной точностью.
   (Результат -- обычное вешественное число типа double.) (1)

12. Вычислить квадратный корень длинного целого числа.
   Если число не является квадратом, то программа должна
   выдавать целую часть корня. (1)

13. Решить уравнение x^2 = s (mod p) в поле вычетов по модулю p. (3)