- 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.

Background on the number field sieve

2.1. Smoothness.

for

where and are real numbers with
and
logarithms are natural. Thus,
,
,
if ,
and if then
for any fixed , and
where is the number of primes .
Let ,
, , and be fixed real numbers with
. A random
positive integer
is
-smooth with
probability
for

We abbreviate to and
to . Thus,
a random integer
is -smooth with
probability
. The notation
in [1] corresponds to
here.
We write ``
'' for ``
for
.''
2.2. Ordinary NFS.

prime

(cf. [11]).
In the relation collection step a set of more than relations
is sought. Given this set, one or more linear dependencies modulo among
the corresponding -dimensional bit vectors are constructed
in the matrix step. Per dependency there is a chance of at least 50%
(exactly 50% for RSA moduli) that
a factor of is found in the final step, the square root step. We
discuss some issues of the relation collection and
matrix steps that are relevant for [1].
2.3. Relation collection.

and

With 2.1 and under
the usual assumption that and behave, with respect to
smoothness probabilities, independently as random integers of comparable
sizes, the probability that both are -smooth is
2.4. Testing for smoothness.

2.5. The matrix step.

2.6. NFS parameter optimization for matrix exponent .

and

Minimizing the resulting

leads to and : even though would allow more ``relaxed'' relations (i.e., larger smoothness bounds and thus easier to find), the fact that more of such relations have to be found becomes counterproductive. It follows that an operation count of is optimal for relation collection, but that for it is better to use suboptimal relation collection because otherwise the matrix step would dominate. We find the following optimal NFS parameters:

**:**-

, , and , with operation counts of relation collection and matrix steps equal to and , respectively. For the operation counts of the two steps are the same (when expressed in ) and the overall operation count is . This corresponds to the heuristic asymptotic runtime of the NFS as given in [11]. We refer to these parameter choices as the*ordinary parameter choices*. **:**-

, , and as given by Relations (2), (4), and (3), respectively, with operation count for relation collection and cost for the matrix step, where . More in particular, we find the following values. **:**-

, , and , for an operation count and cost for the relation collection and matrix steps, respectively. These values are familiar from [1, Section 6: Circuits]. With and equating operation count and cost, this suggests that factoring -bit composites using NFS with matrix exponent is comparable to factoring 512-bit ones using standard-NFS with ordinary parameter choices (disregarding the effects of the 's). **:**-

, , and , for an operation count and cost of for the relation collection and matrix steps, respectively.

2.7. Improved NFS.