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