МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА” ІКТА кафедра ЗІ З В І Т до лабораторної роботи №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 простих чисел в інтервалі: тільки із заданим тестом на подільність. / / Максимальне число для ділення: