Класифікація та експериментальні дослідження ефективності алгоритмів факторизації

Анотація

Предметом дослідження є алгоритми факторизації, а саме експериментальна перевірка ефективності сучасних алгоритмів цілочисельної факторизації, виявлення закономірностей між алгоритмами факторизації та розміром чисел, що факторизуються, з погляду часу, необхідного для виконання факторизації. Мета роботи – аналіз продуктивності алгоритмів факторизації з використанням різних складених чисел, зокрема чисел середнього розміру ( розрядів), що дає змогу оцінити їх ефективність і час виконання. У процесі дослідження необхідно виконати такі завдання: систематизувати сучасні алгоритми факторизації, експериментально перевірити ефективність сучасних алгоритмів факторизації Полларда ( та ), методу еліптичної кривої, алгоритму Діксона й квадратичного решета. Для досягнення мети використовувалися загальнонаукові методи: аналіз предметної галузі та математичного апарату, теорія множин, числа й поля, планування та експериментальне дослідження. Досягнуті результати. Експериментальні дослідження продемонстрували, що алгоритми Полларда ефективні для чисел з малими дільниками, але втрачають продуктивність зі збільшенням розміру чисел. Метод еліптичної кривої довів свою доцільність у пошуку дільників середнього розміру та кращу масштабованість порівняно з класичними стохастичними методами. Алгоритм Діксона, незважаючи на відносну простоту реалізації, продемонстрував стохастичні коливання часу виконання, що обмежує його практичну цінність у сценаріях зі строгими часовими обмеженнями. Найбільш стабільних і передбачуваних результатів було досягнуто для квадратичного решета, яке довело його придатність для факторизації чисел середнього розміру й забезпечило найменший розкид значень часу за умов багаторазового виконання на ідентичних наборах даних. Висновки. Експерименти повністю підтверджують теоретичні очікування щодо продуктивності досліджуваних методів. Результати свідчать про те, що прості алгоритми (метод Полларда й метод еліптичної кривої) ефективні для попереднього оброблення та виявлення слабких ключів, тоді як квадратичне решето є оптимальним вибором для факторизації чисел середнього розміру. Для великих модулів RSA практично використовувати більш складні алгоритми, наприклад загальне решето числового поля. Подальший розвиток алгоритмів факторизації передбачає паралелізацію процесу факторизації та розроблення алгоритмів, що застосовують скринінг неможливих розв’язків.