Задание. 1. Проверить на простоту сгенерированные в лабораторной работе параметры алгоритма RSA (числа р и q)

1. Проверить на простоту сгенерированные в лабораторной работе параметры алгоритма RSA (числа р и q).

2. Распределение простых чисел.

2.1. Задан интервал вида [х, x+L]. Вычислить количест­во П(х, L) простых чисел в интервале и сравнить с величиной L/ln(x). При каких условиях П(x,L)/L близко к 1/ln(x)? Для IBM PC рекомендуется:

х=2000, L=500,

количество простых чисел для деления: 5-15,

количество оснований: 1—2.

2.2. Найти в заданном интервале все простые числа. Пусть L(i) - разность между двумя соседними простыми числами. Построить гистограмму для L(i). Вычислить выборочное среднее L_сред. Сравнить с величиной ln(x), где х - середина интервала. Для IBM PC рекомендуется:

Интервал: (1000, 1000+300),

количество простых чисел для деления: 5-20,

количество оснований: 1-3.

2.3. Для заданного набора чисел {k} оценить относительную погрешность формулы для k – го простого числа:

p(k)=k.ln(k), k={10, 15, 20, 30, 35}.

3. Методы генерации простых чисел.

3.1. В заданном преподавателем интервале построить график относительного количества натуральных чисел, проходя­щих «решето Эратосфена» (т. е. не делящихся на первые k простых).

Для IBM PC рекомендуется: Интервал: (500, 500+200).

Расчет производится для всех k<==10.

3.2. Для заданного интервала:

а) рассчитать точное количество РО простых чисел в ин­тервале, т.е. при проверке задать только тест на делимость.

Количество первых простых чисел для деления определя­ется из расчета: максимальное число для деления равно квадратному корню из максимального значения интервала.

б) составить тест с небольшим количеством пробных де­лений и одним основанием в тесте Ферма. Вычислить количество Р1 вероятно простых чисел, удовлетворяющих этому тесту.

в) составить тест с большим, чем в предыдущем случае, количеством пробных делений и двумя или тремя основания­ми в тесте Ферма. Вычислить количество Р2 вероятно простых чисел, удовлетворяющих этому тесту.

Для IBM PC рекомендуется: Интервал: (1500,1500 + 300).

Проанализировать полученные данные.

3.3. Известно, что в заданном интервале имеются числа Кармайкла. Найти их.

Варианты интервалов: (1050, 1050 + 100)

(1700, 1700 + 100)

(2400, 2400 + 100)

4. Домашнее задание: рассчитать оптимальную страте­гию получения простого числа — выбрать соотношение меж­ду количеством малых простых чисел и количеством тестов Ферма. Цель - минимизировать время проверки заданного числа на простоту.

Контрольные вопросы

1. Почему в качестве первого основания в тестах типа теста Ферма для проверки на простоту очень больших чи­сел целесообразно использовать число 2?

2. Какова вероятность Р(х) того, что наугад взятое нечет­ное очень большое число, не превосходящее х, окажется простым?

3. В качестве теста на простоту используется тест Ферма с двумя основаниями: 2 и Является ли такой выбор оснований удачным?

4. Вычислить:

18¹² (mod 13), 12⁷ (mod7), 2'°°(mod 11).