Для ряду задач захисту інформації криптостійкістьвикористовуваних алгоритмів пов'язана з вирішенням обчислювальної задачі розкладання на множники (факторизації) багаторозрядних чисел. Алгоритми сучасних методів факторизації можуть використовувати, якскладову, інші відомі алгоритми. Тому дослідженнявластивостей відомих методів та розробка способівприскорення їх роботи є актуальною задачею. Для ?-методу Поларда факторизації відомі загальні оцінкидля числа ітерацій, але не представлені результати досліджень щодо впливу на нього початкового наближен-ня. Для оцінки такого впливу запропоновано визнача-ти середнє число ітерацій для p-метода Поларда наприкладі 2*107 варіантів чисел, що не перевищують 231,виду N=p?q, де p и q прості. При визначенні середніхзначень числа ітерацій розраховувалось сумарне числоітерацій для всіх досліджуваних варіантів чисел N, якеділилось на число цих варіантів. Для забезпеченнярозкладання чисел на множники кожен раз, коли іте-раційний процес зациклювався, константа с в поліномі,що реалізує ітераційний процес 21 ( )mod ? ? ? k k x x c N ,збільшувалась на одиницю. Проведені дослідження зоцінки середнього значення числа ітерацій в заледностівід вибору константи с в поліномі, а також від виборупочаткового наближення. Визначено, що для дослі-джуваних варіантів чисел середнє значення числа іте-рацій менше ніж відомі оцінки, а за рахунок виборупочаткового наближення воно може бути зменшенебільш ніж на третину.
Для ряда задач защиты информации криптостойкость используемых алгоритмов связана с решением вычислитель-ной задачи разложения на множители (факторизации) многоразрядных чисел. Алгоритмы современных методовфакторизации могут использовать, как составляющую часть, известные алгоритмы. Поэтому исследование свойствизвестных методов и разработка способов ускорения их работы представляется актуальной задачей. Для ?-метода Полларда факторизации известны общие оценки для числа итераций, но не представлены результаты исследованийпо влиянию на него начального приближения. Для оценки такого влияния предложено определять среднее число итера-ций для ?-метода Полларда на примере 2*107 вариантов чисел, не превышающих 231, вида N=p?q, где p и q прос-тые. При определении средних значений числа итераций рассчитывалось суммарное число итераций по всем исследуе-мым вариантам чисел N и делилось на количество этих вариантов. Для обеспечения разложения чисел на множите-ли каждый раз, когда итерационный процесс зацикливался, константа с в полиноме увеличивалась на единицу. Прове-дены исследования по оценке среднего значения числа итераций в зависимости от выбора константы с в полиноме, реализующем итерационный процесс вида 21 ( )mod ? ? ? k k x x c N , а также от выбора начального приближения. Определе-но, что для исследуемых вариантов чисел среднее значение количества итераций ниже известных оценок, а за счет вы-бора начального приближения оно может быть уменьшено более чем на треть.
For a range of information security tasks the cryptostrengthof algorithms applied is linked to solving acomputational problem of multi-digit numbers factorization.Algorithms of modern factorization methods canuse existing algorithms as integral part. That is why aresearch of existing methods and development of the wayto accelerate their work is considered to be a highly topicalproblem. For Pollard p factorization method generalevaluation of iterations number is known, but the resultsof initial approximation influence study have not beenpresented. To evaluate such influence it is suggested todefine the average number of iterations for Pollard? factorization method in the context of numbersoptions of 2*107 not exceeding 231, of the N=p*q type,where p and q are prime factors. While defining the averageiterations number the total iterations count for alloptions of N under study was calculated and divided bythe number of these options. To provide factoring constantc in the polynomial was increased by one wheneveriteration process ran into a cyclic path. Studies are conductedto evaluate the average iterations number dependingon the choice of constant c in the polynomial, representingiteration process 21 ( )mod ? ? ? k k x x c N , as well ason initial estimate. It has been defined that for the numberoptions under study the average iterations number islower than existing evaluations, and it can be decreased byone third, due to the initial estimate.
