Модифікований алгоритм факторизації великих чисел методом Ферма з використанням базової основи модуля
Вантажиться...
Дата
2018
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Institute of Special Communication and Information Protection of National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”
Анотація
Метод факторизації Ферма вважається кращим при факторизації чисел виду N = p • q у випадках коли множники p і q близькі за значенням. Обчислювальна складність базового алгоритму методу факторизації Ферма визначається кількістю пробних значень Х при вирішенні рівняння Y² = X² – N, а також складністю виконання арифметичних операцій з великими числами: зведення в квадрат, складання, обчислення квадратного кореня. Зниження обчислювальної складності зазначеного методу забезпечується за рахунок використання безлічі основ модулів в рівнянні Y²modb = (X²-N)modb, що в свою чергу дозволяє знехтувати складністю операцій обчислення квадратного кореня. Для зменшення числа пробних значень Х розглядалася можливість використання базової (первинної) основи модуля bb. Оптимальний вибір базової основи модуля bb дозволяє зменшити число пробних Х на величину, близьку за значенням до величини коефіцієнта прискорення z(N, bb) = bb/bb*, де bb* – число елементів множини коренів рівняння (Ymodb)²modb = ((Xmodb)²modb - Nmodb)modb. Показано, що в загальному випадку базова основа модуля bb є добутком ступенів простих чисел р, коефіцієнт прискорення для якого z(N, bb) є функцією Nmodp і показників ступенів р. Визначено ступінь впливу значення залишків Nmodp (в разі р=2 використовуються залишки Nmod8) і показників ступенів простих р на величину коефіцієнта прискорення z(N, bb)). Запропоновано постановку задачі пошуку оптимального значення базової основи модуля bb при обмеженнях на обсяг пам'яті ЕОМ і спосіб її вирішення. Наведено оцінку ефективності запропонованого модифікованого алгоритму методу факторизації Ферма. Встановлено, що запропонований алгоритм для чисел 2¹⁰²⁴ забезпечує зниження обчислювальної складності в порівнянні з базовим алгоритмом в середньому в 10⁷ разів. Використання запропонованого методу дозволить проектувати більш ефективні, з точки зору швидкодії, апаратно-програмні засоби проведення криптоаналізу асиметричних криптографічних алгоритмів та, як наслідок, підвищити якість оцінки криптостійкості алгоритму RSA.
Опис
Ключові слова
факторизація, метод Ферма, проріджування, базова основа, обчислювальна складність, factorization, Fermat method, thinning, base foundation, computational complexity, факторизация, прореживание, базовое основание, вычислительная сложность
Бібліографічний опис
Винничук, С. Модифікований алгоритм факторизації великих чисел методом Ферма з використанням базової основи модуля / Степан Винничук, Євген Максименко // Information Technology and Security. – 2018. – Vol. 6, Iss. 2 (11). – Pp. 79–93. – Bibliogr.: 10 ref.