Acceleration of Fermat's factorization method by decimation method with use of several bases
DOI:
https://doi.org/10.18372/2225-5036.21.8310Keywords:
public key cryptography, factorization, Fermat's factorization method, decimation, accelerationAbstract
Fermat's factorization method is the basis of the existing methods of factorization (General number field sieve, Quadratic sieve). We can achieve acceleration of Fermat's factorization method, by moving to modular equation 22mod(modmod)modxBNByBB=+ where B some module (base). The effectiveness of this approach increases when increasing base B. When you increased base, you must to increase the required amount of memory to store permissible values xmodB and increase computational complexity. The increase in computational complexity with increasing the required memory bigger than growth of the efficiency of acceleration. We have many problems arising when using larger bases (B), that is why we propose to use multiple small bases. We have a problem, of effective choice of the bases. This paper analyzes the efficiency, the use of screening on two bases b1 and b2, and give comparable characteristics of the option, when used for screening one base Bb1*b2=. Described conditions for the effectiveness of screening options for one and two bases.References
Жилин А.В. Использование RSA алгоритма для обеспечения задач криптографической защиты информации в современных информационно-телекоммуникационных системах / А.В. Жилин, А.В. Корнейко, В.В. Мохор // Захист інформації. – 2013. – Т.15, № 3. – С. 225-231.
Song Y. Yan. Cryptanalytic attacks on RSA / Song Y. Yan – Springer Science and Business Media, Inc. 2008. – Р.255
Горбенко И.Д. Анализ каналов уязвимости системы RSA / И.Д. Горбенко, В.И. Долгов, А.В. Потий, В.Н. Федорченко // Безопасность информации. – 1995. – № 2. – С.22-26.
Винничук С.Д., Жилин А.В., Мисько В.Н. Ускорение метода ферма факторизации чисел вида n = pq, где p и q простые, методом прореживания
Кнут Д. Искуство программирования том 2 (3-е изд.) 2001 – 423 с.
