Проблема факторизації безпосередньо пов'язана з визначенням криптостійкості RSA, яке базується на припущенні, що не існує швидких алгоритмів факторизації, які за короткий час дозволили б зламати код, а якщо через деякий час і вийде це зробити, то дані втратять свою актуальність. У цій статті ми протестуємо і зробимо висновки по одному із способів факторизації.
Наведемо визначення факторизації.
Факторизацією цілого числа називається його розкладання у твір простих сумнівножувачів. Таке розкладання, згідно з основною теоремою арифметики, завжди існує і є єдиним (з точністю порядку прямування множників).
Будемо позначати число, яке потрібно розкласти буквою N, а два сумнівножителя, в результаті множення яких отримаємо N, як a і b.
Алгоритм факторизації Ленстри (факторизація на еліптичних кривих) є одним з найшвидших методів факторизації. Він має багато спільного з методом Полларда (p - 1), але працює значно швидше, слід зазначити, що він є субекспоненційним методом. Головна особливість алгоритму - це те, що час, витрачений на факторизацію, залежить не від розмірності N, а від розміру найменшого ділника числа N.
Детально про цей метод ви зможете почитати з матеріалу в списку використаної літератури, але все ж наведемо основні стадії алгоритму.
- Введемо число N.
- Виберемо певне значення B, яке є максимальною межею числа-ділника N.
- Створюємо випадковим чином значення x, y, a, які належать безлічі цілих чисел від 0 до N-1. Ці значення визначають криву, а також x і y визначають початкову точку P.
- Обчислюємо b = y. 2-x. 3-ax mod n і g = Н.О.Д. (N, 4a. 3 + 27b. 2). Важливо, що б g не був рівний N, інакше повертаємося до п. 2. Якщо 1 < g < n, тоді припинимо обчислення - ділник знайдено. Цей варіант можливий при малих значеннях числа N (наприклад 10), при зростанні N ця можливість зустрічається все рідше.
- Далі потрібно виконати цикл, в результаті якого для кожного простого числа p (в межі від 2 до B-1) обчислимо точку P, домножену на p r, де r найбільший ступінь, що задовольняє умову p r < B.
В арифметиці полів немає операції ділення, яка необхідна у формулах для знаходження координат точок, так що ми перетворюємо вираз у вигляді множення, а зворотний елемент шукаємо за розширеним алгоритмом Євкліда. До того ж кожне нове обчислення ми виробляємо за модулем числа N.
Алгоритм завершить свою роботу, коли буде знайдений Н.О.Д. (N, P), який більше 1 і менше N. Щоб уникнути помилки у відповіді, функція знаходження Н.О.Д. повинна перевіряти тільки позитивні значення.
Розгляньмо графік часу, який нам знадобиться для факторизації різних чисел. (Результат наведено з написаної мною програми)
N=10 – 0,005 sec;
N=437 – 0,019 sec;
N=3127 – 0,055 sec;
N=23707 – 0,191 sec;
N=1752967 — 1,534 sec;
N=6682189 — 0,143 sec;
N=12659363 — 3,376 sec;
N=494370889 – 4,484 sec;
N=1435186847 — 87,377 sec;
Оскільки крива генерується з випадкових значень, час факторизації при кожному новому запуску програми буде різним. Дивлячись чи вдала крива нам попадеться. Тому спробуємо взяти ці ж числа і виконати факторизацію ще кілька разів і звіримо результати.
N=10 – 0,016 sec;
N=437 – 0,016 sec;
N=3127 – 0,218 sec;
N=23707 – 0,079 sec;
N=1752967 — 1,484 sec;
N=6682189 — 1,125 sec;
N=12659363 – 6,906 sec;
N=494370889 – 4,781 sec;
N=1435186847 — 81,766 sec;
І для закріплення зробимо останній замір.
N=10 – 0,012sec;
N=437 – 0,022 sec;
N=3127 – 0,156 sec;
N=23707 – 0,205 sec;
N=1752967 — 1,418 sec;
N=6682189 — 1,056 sec;
N=12659363 – 0,25 sec;
N=494370889 – 5,488 sec;
N=1435186847 – 14,117 sec;
Як ми бачимо на останньому графіку, час витрачений на останнє число помітно зменшився, це характеризується тим, що крива генерується випадковим чином. Слід зауважити, що час, витрачений на виконання алгоритму, залежить і від значення B, яке ми вводимо. Я намагався брати значення наближені до значень двох сумнівножувачів (a і b), але якщо ви будете виконувати операцію над числом, де початкові множники не відомі навіть приблизно, то варто вибирати межу вище. Але чим вище межа, тим більше і часу піде на обчислення точок, тому що їх буде більше, це потрібно враховувати.
Слід враховувати і продуктивність обчислювальної машини. Я виробляв обчислення на Процесорі AMD Athlon (tm) II X4 645 з частотою 3.10 ГГц. Навантаження на Процесор було близько 40% при роботі програми. Навантаження на Пам'ять помічено не було.
Підсумок
Алгоритм працює за досить хороший час, але тільки для відносно не великих значень. Адже як ми бачимо за графіком 1 і 2, число після 1 мільярда в більшості випадків має великий розрив з часом, витрачене на число 494370889, але це було очікувано, адже як було помічено раніше, метод є субекспоненційним.
Дякую, що дочитали мою першу статтю.
Використана література: «Математичні основи захисту інформації»
