(Short Paper) Parameter Trade-Offs for NFS and ECM

摘要

This paper analyzes two factoring algorithms, NFS (Number Field Sieve) and ECM (Elliptic Curve Method). The previous results only minimize their running times, however, we may need to minimize the storage size or running time with smaller success probability. We provide these trade-offs, L[s] (s ≤ 1/3) memory requires L[l - 2s] running time for NFS, for example. This can be interpreted that NFS requires much more running time when reducing memory complexity.