Integer factorization

Circuits for integer factorization

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.

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;