Acceleration of Fermat's factorization method by decimation method with use of several bases

Abstract

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.