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. Вычислить:
1812 (mod 13), 127 (mod7), 2'°°(mod 11).