Vynnychuk S. Application of the basic module's foundation for factorization of big numbers by the Fеrmаt method / S. Vynnychuk, Y. Maksymenko, V. Romanenko // Вост.-Европ. журн. передовых технологий. - 2018. - № 6/4. - С. 14-23. - Бібліогр.: 21 назв. - англ.Метод Ферма вважається кращим за факторизації чисел N = p x q у випадку близьких p і q. Обчислювальна складність базового алгоритму методу визначається кількістю пробних значень Х під час розв'язку рівняння Y<^>2 = X<^>2 - N, а також складністю арифметичних операцій. Для її зниження запропоновано як допустимі розглядати ті з пробних Х, для яких (X<^>2 - N)modbb є квадратним залишком по модулю bb, названого базовым. У разі використання базової основи модуля bb число пробних Х зменшується в число раз, близьке до Z(N,bb) = bb/bb<^>*, де bb<^>* - число елементів множини T коренів рівняння (Ymodb)2modb = ((Xmodb)<^>2 - Nmodb)modb, а Z - коефіцієнт прискорення. Визначено, що на величину Z(N,bb) впливають значения залишків Nmodp (за p = 2 використовуються залишки Nmod8). Запропоновано постановку задачі пошуку bb з максимальным Z(N,bb) за обмежень на обсяг пам'яті ЕОМ, де визначаються показники степенів простих чисел - множників bb, і спосіб її розв'язку. Для зменшення числа арифметичних операцій із великими числами запропоновано замість таких виконувати операції зі значеннями різниць між найближчими значеннями елементів множини T. Тоді арифметичні операції множення і додавання з великими числами виконуються рідко. А якщо квадратний корінь з X<^>2 - N визначати тільки у випадках, коли значення (X<^>2 - N)modb будуть квадратними залишками для багатьох різних основ модуля b, то обчислювальною складністю цієї операції можна знехтувати. Встановлено, що тоді запропонований модифікований алгоритм методу Ферма для чисел 2<^>1024 забезпечує зниження обчислювальної складності в порівнянні з базовим алгоритмом в середньому в 10<^>7 раз. Індекс рубрикатора НБУВ: В127.4
Рубрики:
Шифр НБУВ: Ж24320 Пошук видання у каталогах НБУВ Повний текст Наукова періодика України Додаткова інформація про автора(ів) публікації: (cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці) Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|