МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА
кафедра ЗІ
З В І Т
до лабораторної роботи №4
з курсу:
«Криптографія і стеганографія»
на тему:
«Генерація простих чисел, що використовуються в асиметричних системах шифрування»
Варіант 23
ЗАВДАННЯ
1. Перевірити на простоту два довільних цілих числа розрядністю не менше 5.
2. Розподіл простих чисел.
Заданий інтервал виду [x, x+L]. Обрахувати кількість П(x,L) простих чисел в інтервалі і порівняти з величиною L/ln(x). При яких умовах П(x,L)/ L є близьким до 1/ ln(x) при заданих x=2000, L=500, кількість простих чисел для ділення 5 – 15, кількість основ 1 – 2?
3. Визначити в інтервалі (1000, 1000+300) усі прості числа. Нехай L(i) –різниця між двома сусідніми простими числами. Побудувати гістограму для L(i) . Обрахувати вибіркове середнє Lсеред. Порівняти з величиною ln(x), де x – середина інтервалу. Задано: кількість простих чисел для ділення 5 – 20, кількість основ 1 – 3.
4. Для заданого набору чисел {k} оцінити відносну похибку формули для k -го простого числа: p(k)= k/lnk, k={10,15,20,30,35}.
5. В інтервалі (500, 500+200) побудувати графік відносної кількості натуральних чисел, що проходять «решето Ератосфена», тобто таких, що не діляться на перші k простих. Розрахунок зробити для всіх k ≤ 10.
6. Для інтервалу (1500, 1500+300):
а) розрахувати точну кількість Р0 простих чисел в інтервалі, тобто при перевірці задати тільки тест на подільність. Кількість перших простих чисел для ділення визначається з розрахунку: максимальне число для ділення дорівнює квадратному кореню з максимального значення інтервалу;
б) скласти тест з більшою, ніж у попередньому випадку, кількістю пробних ділень та двома або трьома основами в тесті Ферма. Розрахувати кількість Р2 ймовірно простих чисел , які задовольняють цьому тесту. Проаналізувати отримані результати.
7. Відомо, що в заданому інтервалі є числа Кармайкла. Визначити їх. Варіанти інтервалів: (1050, 1050+100), (170, 1700+100), (2400+100).
ХІД РОБОТИ
1. Перевірка на простоту.
/
/
2. Знаходження простих чисел в інтервалі.
/
/
П(x,L) = 64
L/ln(x) = 500/7.6 = 65.78
П(x,L) є досить близьким до L/ln(x).
3. Знаходження простих чисел в інтервалі.
/
/
Гістограма L(i) –різниця між двома сусідніми простими числами.
/
Lсеред = 6,80
Lсер приблизно дорівнює Ln(xсер)
Ln(xсер) = 7,06
Оцінка відносної похибки формули для k-го простого числа за формулою
p(k) = k/lnk, k = {10,15,20,30,35}
p(10) = 10/(ln(10)) = 4.3 p(15) = 15/(ln(15)) = 5.5
p(20) = 20/(ln(20)) = 6.6 p(25) = 25/(ln(25)) = 7.7
p(30) = 30/(ln(30)) = 8.8 p(35) = 35/(ln(35)) = 9.8
З цих обрахунків легко бачити, що збільшенням номера k, збільшується відносна похибка формули для k-го простого числа.
4. Побудова графіка відносної кількості натуральних чисел, що проходять «решето Ератосфена».
/
/
/
5. Розрахунок точної кількості Р0 простих чисел в інтервалі:
тільки із заданим тестом на подільність.
/
/
Максимальне число для ділення:
