# How to calculate bit strength of Integer Factorization Cryptography (IFC) such as RSA using Python

I would like to know how to calculate the bit-strength of Integer Factorization Cryptography (IFC) such as RSA by using Python. I gathered it is based off the complexity of factorizing the modulus (public key). I want to be able to calculate the bit strength of arbitrary key-lengths of RSA for example, such as 4096 which is not given by NIST etc.

This is similar to this question Security strength of RSA in relation with the modulus size, where the answer is provided by using Mathematica.

The fastest publicly known algorithm for factoring is the General Number Field Sieve (GNFS). This has the complexity defined in L-notation. The formulae includes little-o 1, which I'm not sure how to fit into the calculations, in the Mathematica example it is left out (treated as being equal to 1).

Here is the relevant Mathematica code:

I generated these numbers with the following Mathematica code:

({#, N@Log2@g[#]} &) /@ {1024, 2048, 3072, 7680, 15360}


where g is defined as:

g[b_] := Exp[(64/9 * Log[2^b])^(1/3) * (Log[Log[2^b]])^(2/3)]


If I understand correctly taking log2 of the exp would cancel out, so the result it's equivalent to just:(64/9 * Log[2^b])^(1/3) * (Log[Log[2^b]])^(2/3).

I have tried the following Python code but it seems to be way off.

import fractions
import math

ln = math.log

n = pow(2, 1024)  ## change for other RSA key-sizes

a = fractions.Fraction(1,3)
c = pow(fractions.Fraction(64,9), fractions.Fraction(1,3))
# c = 1.9229994270765445

def g(a, c, n):
return math.exp(c * pow(ln(n), a) * pow(ln(ln(n)), 1 - a))

x = g(a, c, n)
# x = 1.3158442944491604e+26
s = ln(x)
# s = 60.1416909264604


The result for 1024 is 60.14, whereas NIST says 80, and Mathematica got 86.77. The results for other key-sizes are all way off.

This is the results from Mathematica (3rd column) which are very close to NIST (1st column).

Strength  RSA modulus size   Complexity bit-length
80        1024              86.76611925028119
112        2048              116.8838132958159
128        3072              138.7362808527251
192        7680              203.01873594417665
256       15360              269.38477262128384


My results from my Python code are (10243, 60.14), (2048, 81.02), (3072, 96.16), etc.

I thought maybe this is due to rounding errors, but using WolfRamAlpha (I don't have Mathematica which is why I'm trying to use Python instead) I get the same results as Python.

This is what I put into WolfRamAlpha:

(64/9 * Log[2^1024])^(1/3) * (Log[Log[2^1024]])^(2/3)


Decimal result is 60.14169092646040456.... Pretty much same as my Python code. How did NIST and referenced answer get such different results. My code looks equivalent to me. I don't see my mistake.

What am I doing wrong?

• log2 is log base 2. $log2(exp(x))$ is x times 1.44270 approximately, which gives the expected results. – dave_thompson_085 Jun 20 '14 at 7:47
• Can you make this an answer, since it is what I was doing wrong, I mistook log2 as log, whereas log * exp cancels, log2 * exp does not. – sexybear Jun 23 '14 at 1:57
• Can the downvoter mention the reason for the down-vote – sexybear Jun 23 '14 at 1:58

log2 is log base 2. $log(exp(x))$ would cancel, but $log2(exp(x))$ is x times 1.44270 approximately, which gives the expected results