ГЕНЕРАЦІЯ ПРОСТИХ ЧИСЕЛ, ЩО ВИКОРИСТОВУЮТЬСЯ В АСИМЕТРИЧНИХ СИСТЕМАХ ШИФРУВАННЯ. Звіт з Криптографія. Робота № 101091

ГЕНЕРАЦІЯ ПРОСТИХ ЧИСЕЛ, ЩО ВИКОРИСТОВУЮТЬСЯ В АСИМЕТРИЧНИХ СИСТЕМАХ ШИФРУВАННЯ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКТА

Факультет:

КН

Кафедра:

ЗІ

Інформація про роботу

Рік:

2025

Тип роботи:

Звіт

Предмет:

Криптографія

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет “Львівська політехніка” ІКТА кафедра ЗІ / ЗВІТ На тему:“ ГЕНЕРАЦІЯ ПРОСТИХ ЧИСЕЛ, ЩО ВИКОРИСТОВУЮТЬСЯ В АСИМЕТРИЧНИХ СИСТЕМАХ ШИФРУВАННЯ ” до лабораторної роботи №5 з курсу:“ Основи криптографії ” Мета роботи: вивчення методів генерації простих чисел, що використовуються в системах шифрування з відкритим ключем, та перевірка чисел на простоту. Завдання Перевірити на простоту два довільних цілих числа розрядністю не менше 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 ймовірно простих чисел , які задовольняють цьому тесту. Проаналізувати отримані результати. 2. Пошук простих чисел в інтервалі 2000-2500 / / У межах інтервалу [2000, 2500] було знайдено 64 простих числа, що становить 12.77% усіх чисел у проміжку. П=?? 500/ ?? ( 2000) = 65.78 П < L/ln(x) П(x,L)/ L є близьким до 1/ ln(x) при малому інтервалі. Теоретична оцінка кількості простих чисел за формулою L / ln(x) склала приблизно 65.79. Це значення є близьким до реального результату, що підтверджує ефективність логарифмічного наближення розподілу простих чисел. 3. Пошук простих чисел в інтервалі 2000-2500 / / / / Розгянувши гістогаму знаходимо L(сер.) ?= ?+?+?+??+??+?+?+?+?+?+??+??+??+?+??+?+?+??+??+?+? ?? =7.52 та порівнюємо з Ln(x), в результаті отримаємо що ?? ( 1151)=7.048 L>ln(x) 4. Оцінка відносної похибки Формула відносної похибки: ε(k) = |(k / ln(k) – p(k)) / p(k)| де: • p(k) — істинне значення k-го простого числа • k / ln(k) — наближене значення за формулою • ε(k) — відносна похибка k p(k) — істинне k / ln(k) — наближення Відносна похибка 10 29 4.34 0.8502 15 47 5.54 0.8821 20 71 6.68 0.9060 30 113 8.82 0.9219 35 149 9.84 0.9339 У цьому випадку спостерігається суттєва відносна похибка між наближеним значенням та істинним значенням. Навіть при збільшенні значення k, точність формули не покращується помітно — відносна похибка залишається високою. Для того, щоб точність була вища, наближення має бути ближча по значенню до істинного значення. 5. Пошук простих чисел в інтервалі 500-700 / / / У цьому завданні досліджували, як змінюється кількість чисел у проміжку [500; 700], які не діляться на перші k простих чисел. Зі збільшенням кількості дільників таких чисел ставало дедалі менше. Кожне число забарвлювали відповідно до його першого дільника, що дозволило візуально відстежити, на якому етапі воно "вибувало" з розрахунків. Побудований графік наочно підтвердив тенденцію: що більше простих чисел враховується, то менше чисел проходять фільтрацію. б) тестом на подільність та тестом Ферма / / Перевірка інтервалу [1500; 1800] виявила 39 простих чисел як за стандартним тестом на подільність, так і за розширеним комбінованим тестом із додатковими основами для тесту Ферма. Це свідчить про те, що в цьому випадку тест Ферма не ідентифікував жодних "брехунців" серед складених чисел і, відповідно, не вплинув на результат. Така ситуація підтверджує точність звичайного тесту за умови достатньої кількості простих дільників та відсутності псевдопростих чисел у даному інтервалі. Висновок У ході лабораторної роботи було досліджено різні методи генерації та перевірки простих чисел, що відіграють ключову роль у криптографічних системах з відкритим ключем. Зокрема, розглянуто тести на подільність, тест Ферма, а також наближені формули для оцінки кількості простих чисел у заданих інтервалах. Дослідження показало, що логарифмічна оцінка кількості простих чисел (L / ln(x)) добре наближає реальні значення. Було проаналізовано розподіл простих чисел і встановлено, що середня різниця між ними приблизно дорівнює ln(x). Оцінка формули для k-го простого числа продемонструвала значну відносну похибку, навіть при збільшенні значення k. Окрему увагу приділено аналізу решета Ератосфена, де спостерігалося закономірне зменшення кількості чисел, що проходять фільтрацію, із додаванням кожного нового простого дільника. Візуалізація цього процесу допомогла глибше зрозуміти принцип дії алгоритму. Також проведено перевірку простих чисел за комбінованим тестом (подільність + Ферма), яка показала, що результати залишаються незмінними за відсутності псевдопростих чисел у вибірці.

Звіт Криптографія

kakaduka

08.04.2025 12:04-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись