Computational methods in discrete mathematics

Absence of dynamism at method NFS

Y. L. Zachesov^a, A. M. Grishin<sup>b

a</sup> Research Institute "Kvant", Moscow
^b Moscow

Abstract: At present, the number field sieve (NFS) and a software package GGNFS are the primary tools for solving the factorization problem. Extrapolation of the data complexity of the algorithm NFS shows that it is impossible to apply this algorithm for factoring 768-bit or more modules. This work compares the evaluation of labor-intensiveness of sub-exponential algorithms of whole number factorization and evaluation of productivity of supercomputers from the Top 500 list. The conclusion following from the comparison is that these algorithms are now non-dynamic.

UDC: 519.61