Метод Ферма вважається кращим за факторизації чисел 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 раз.

  Повний текст PDF - 455.501 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"