D. J. Bernstein
Integer factorization
Circuits for integer factorization

# Calculating the cost exponents

## The parameter space

Take any real numbers B > 0, D > 0, F >= 0, Y > 0 such that 2B - (1/D)/3Y - (1/D+BD)/3(Y-F) + F >= Y.

As far as we know, any key n can be factored by a (B,D,F,Y) NFS calculation. You can read the rest of this page, and calculate cost exponents, without the following definition: ``a (B,D,F,Y) NFS calculation'' is NFS with ``degree'' (D+o(1)) (log n)^(1/3) (log log n)^(-1/3), ``a,b bound'' L^(B+o(1)), ``rational prime bound'' L^(Y+o(1)), ``k bound'' (number of fields) L^(F+o(1)), and ``algebraic prime bound'' L^(Y-F+o(1)). As usual, L means exp((log n)^(1/3) (log log n)^(2/3)).

Conventional (B,D,F,Y) NFS sieving takes time L^(2B+o(1)) on a machine of size L^(Y+o(1)). Circuit (B,D,F,Y) NFS sieving takes time L^(2B+o(1)) on a machine of size L^(o(1)). In both cases, it is easy to trade time for hardware cost, leaving the product of time and size constant.

Conventional (B,D,F,Y) NFS linear algebra takes time L^(2Y+o(1)) on a machine of size L^(Y+o(1)). Circuit (B,D,F,Y) NFS linear algebra takes time L^(1.5Y+o(1)) on a machine of size L^(Y+o(1)). It is once again possible to trade time for hardware cost.

## Particular choices of parameters

Conventional NFS, as described in the literature, uses conventional (B,D,F,Y) NFS sieving and conventional (B,D,F,Y) NFS linear algebra, with B=0.9509418059..., D=1.4017532352..., F=0.1250325942..., and Y=0.9509418059...=B. This choice of (B,D,F,Y) minimizes max{2B,2Y}.

Conventional NFS, as optimized by Pomerance in April 2002, uses conventional (B,D,F,Y) NFS sieving and conventional (B,D,F,Y) NFS linear algebra, with B=1.0057382450..., D=1.4101733897..., F=0, and Y=0.7488351294.... This choice of (B,D,F,Y) minimizes Y+max{2B,2Y}. I missed this possibility in my October 2001 grant proposal because I was assuming, as in the literature, that 2B=2Y.

Circuit NFS, as described in my grant proposal, uses circuit (B,D,F,Y) NFS sieving and circuit (B,D,F,Y) NFS linear algebra, with B=0.9880259179..., D=1.4227573217..., F=0, and Y=0.7904207343...=4B/5. This choice of (B,D,F,Y) minimizes max{2B,2.5Y}.

An intermediate possibility uses circuit (B,D,F,Y) NFS sieving and conventional (B,D,F,Y) NFS linear algebra, with B=1.0400419115..., D=1.3867225487..., F=0, and Y=0.6933612743...=2B/3. This choice of (B,D,F,Y) minimizes max{2B,3Y}. Notice that the relatively slow linear algebra means that Y has been decreased to bring sieving and linear algebra into balance.

Sample Maple code to do the max{2B,2.5Y} minimization:

```   extrema(target,
{target-2*b-s1*s1,
target-(5/2)*y-s2*s2,
b-s3*s3,d-s4*s4,f-s5*s5,y-s6*s6,
2*b-(1/d)/(3*y)-(1/d+b*d)/(3*(y-f))+f-y-s7*s7},
{target,b,d,f,y,s1,s2,s3,s4,s5,s6,s7},
'v');
Digits:=20;
for i in v do
if (evalf(eval(target,i)) > 0) then
if (evalf(eval(s1,i)) >= 0) then
if (evalf(eval(s2,i)) >= 0) then
if (evalf(eval(s3,i)) >= 0) then
if (evalf(eval(s4,i)) >= 0) then
if (evalf(eval(s5,i)) >= 0) then
if (evalf(eval(s6,i)) >= 0) then
if (evalf(eval(s7,i)) >= 0) then
print([evalf(eval(b,i)),evalf(eval(d,i)),
evalf(eval(f,i)),evalf(eval(y,i))]);
end if;
end if;
end if;
end if;
end if;
end if;
end if;
end if;
end do;
```