**
Arjen K. Lenstra ^{},
Adi Shamir^{},
Jim Tomlinson^{},
Eran Tromer^{} **

In [1], 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
``construction cost 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.

factorization, number field sieve, RSA, mesh routing

- Introduction
- Background on the number field sieve
- 2.1. Smoothness.
- 2.2. Ordinary NFS.
- 2.3. Relation collection.
- 2.4. Testing for smoothness.
- 2.5. The matrix step.
- 2.6. NFS parameter optimization for matrix exponent .
- 2.7. Improved NFS.

- The circuits for integer factorization from [1]
- 3.1. Matrix-by-vector multiplication using mesh sorting.
- 3.2. The throughput cost function from [1].
- 3.3. Application of the throughput cost.
- Remark 3.4
- 3.5. Implication of the throughput cost.
- 3.6. Alternative interpretation.
- Remark 3.7
- Remark 3.8

- Operation count, equipment cost, and real time
- 4.1. Lowering the cost of the standard-NFS matrix step.
- 4.2. Operation count based estimates.
- Remark 4.3

- Hardware for the matrix step for 1024-bit moduli
- 5.1. Matrix sizes.
- 5.2. Estimated relation collection cost.
- 5.3. Processing the ``small'' matrix using Bernstein's circuits.
- 5.4. A routing-based circuit.
- 5.5. An improved routing-based circuit.
- 5.6. An improved circuit for the ``large'' matrix.
- 5.7. Summary of hardware findings.

- Conclusion
- Bibliography
- Using off-the-shelf hardware for the circuit approach
- The traditional approach to the matrix step