Виничук, Степан ДмитровичМаксименко, Євген Васильович2020-05-282020-05-282018Винничук, С. Модифікований алгоритм факторизації великих чисел методом Ферма з використанням базової основи модуля / Степан Винничук, Євген Максименко // Information Technology and Security. – 2018. – Vol. 6, Iss. 2 (11). – Pp. 79–93. – Bibliogr.: 10 ref.https://ela.kpi.ua/handle/123456789/33838Метод факторизації Ферма вважається кращим при факторизації чисел виду 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.С. 79-93ukфакторизаціяметод Фермапроріджуваннябазова основаобчислювальна складністьfactorizationFermat methodthinningbase foundationcomputational complexityфакторизацияпрореживаниебазовое основаниевычислительная сложностьArticlehttps://doi.org/10.20535/2411-1031.2018.6.2.153492004.056.53::003.26.09