4
$\begingroup$

RFC 3766, Section 4.1 discusses picking $n$ to achieve some target cost for employing the GNFS, i.e., $T$ is known and $N$ is unknown in the below equation:

$$T = \kappa \cdot \exp{\left(c \cdot (\ln{N})^{1/3} (\ln{\ln{N}})^{2/3}\right)}$$

In the RFC, the authors use $c = 1.92$. By using their empirically-derived coefficient $\kappa= 0.02$, the authors effectively make the units for $T$ to be "instructions."

The authors give an example in Sec 4.1, solving for $N$ given target cost $T = 5 \cdot 10^{33}$, employing an approximation that is not described:

5*10^33 = (6*10^-16)*e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))

Solving this approximately for n yields:

 n = 10^(625) = 2^(2077)

How did they get this equation, and does the approximation seem reasonable?

The perceived discrepancy.

Using Wolfram Alpha:

  • the equation is solved as $n=7.667...\times10^{1354}$ (which is quite different than $10^{625}$)
  • substituting $n=10^{625}$ into the equation yields $T = 1.29917...\times10^{20}$ (which is quite different than $5 \cdot 10^{33}$)

Showing my work.

Well, the equation can be copy-pasted into Alpha without modification; but, I suspect that the discrepancy may be due to a typo, or the approximation is pretty loose, or some combo:

  • the coefficient 6*10^-16 is (per Sec. 2.2) used to adjust the equation to relate to an adversary doing 1 MIPS years of instructions, or $10^6$ instructions/sec, calculated as: $$0.02\cdot \frac{1}{10^{6}} \frac{1}{86400} \frac{1}{365} \approx 6 \cdot 10^{-6}$$
  • But the trillionaire adversary in Sec 4.1 can do 5e12 MIPs of instructions per year.
  • Also, they state "50 year resistance against a trillionaire is assumed to be the minimum security requirement"

Thus, perhaps this is just a typo and the real equation is more like the work accomplished by the trillionaire over 50 years, when it can do 5e12 instructions per year:

5*10^33 = 0.02 / (5 * 10^12 * 50) * e^(1.92*cubrt(ln(n)*(ln(ln(n)))^2))

But this doesn't get me any closer to the results they report.

$\endgroup$
  • $\begingroup$ Your cubrt() term doesn't look correct to me; it doesn't commute across the two multiplied terms. Try entering the equation literally to see if there is a difference... $\endgroup$ – rmalayter Jul 1 '16 at 1:05
  • $\begingroup$ The equation literally is 5*10^33 == (6*10^-16) * E^(1.92 * (Log[x])^(1/3) * (Log[Log[x]])^(2/3)) but this exceeds the computation time on Alpha. Splitting this into parts---x = Log[n] and 5*10^33 == (6*10^-16) * E^(1.92 * (x)^(1/3) * (Log[x])^(2/3))---yields the same answer as in the post ($x = 3119.737$, thus $n=7.667 \cdot 10^{1354}$). Maybe I made the same mistake twice, and am not acting your advice correctly. $\endgroup$ – GermaneDork Jul 1 '16 at 6:43
  • $\begingroup$ My point was that $$(c(\ln{N})^{1/3} (\ln{\ln{N}})^{2/3})$$ is in the given equation, and that is not equal to $$c((\ln{N}) (\ln{\ln{N}})^{2})^{1/3}$$ ...and the latter is what your cubrt() formula equals $\endgroup$ – rmalayter Jul 5 '16 at 15:21
  • $\begingroup$ Actually, I see that I was fooled by the double-precision rounding in the environment in which I was testing (nodejs)... those expressions are equivalent, so that doesn't seem to be the issue from a symbolic sense. But given that those two expressions were not equal in nodejs, could it be floating-point rounding and whatever iteration scheme is used in the solver? $\endgroup$ – rmalayter Jul 5 '16 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.