Inequality of computational effort of Pollard p-method according to dispaly selection and initial estimate for small-scale factorizable amounts
Степан Дмитрович Винничук, Евгений Васильевич Максименко, Виталий Николаевич Мисько · Ukrainian Information Security Research Journal · 2014
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.