], Bernstein proposed a circuit-based implementation of the
matrix step of the number field sieve factorization algorithm. These
circuits offer an asymptotic cost reduction under the measure
run time''. We evaluate the cost of these
circuits, in agreement with [1
], but argue that compared to
previously known methods these circuits can factor integers that
are 1.17 times larger, rather than 3.01 as claimed (and even this,
only under the non-standard cost measure).
We also propose an improved circuit design based on a new mesh routing
algorithm, and show that for factorization of 1024-bit integers
the matrix step can, under an optimistic assumption about the matrix size,
be completed within a day by a device that costs
a few thousand dollars. We conclude that from a practical standpoint,
the security of RSA relies exclusively on the hardness of the relation
collection step of the number field sieve.