Benchmarking factorisation algorithms

Our collective inability to work out how to factorise large integers is what underpins a significant proportion of the world’s internet security. You can read more about this here.

This blog post seeks to provide some insight into a natural follow-up question: “how hard is it, really, to factorise the types of integers that are used to keep the internet secure?”

Answering this kind of question is difficult because, in truth, there are no publically known algorithms that can factorise the types of integers we are talking about here. On the flip side, to our knowledge, nobody has been able to show such algorithms do not exist. Really, the only real scientific answer is: we don’t know.

Therefore, instead of approaching this from a theoretical point of view, we try and provide some practical insights. We demonstrate a way of measuring the performance of factorisation algorithms and present performance metrics for some really simple factorisation algorithms. The results give us a meaningful insight as how tractible it is to factorise the types of integers we care about.

naive1

Let’s start throwing some code at this problem! What we need is Python function which, given a modulus, n, returns a factor of said modulus. Remember that a factor of n is simply an integer that divides n. The simplest such Python function we can think of is the naive1 function listed below. This function iterates over all integers smaller than n and returns the first such integer that divides n.

def naive1(n):
  for i in range(2, n):
    if n % i == 0:
      return i

The default bit length of the moduli in RSA keys generated by ssh-keygen on Ubuntu 20.04 is 3072 bits. Hence, we could take such a 3072 bit modulus and see how long this algorithm take to find it’s factor. Unfortunately, as you will soon see, this is a rather ill-advised approach. Instead, we run the algorithm on a series of moduli with increasingly large bit lengths until we get to a problem we cannot solve in a reasonable time. Note I have made a benchmarking tool publically available to do exactly this.

In my experiments, naive1 was only able to factorise moduli of 60 bits in length:¹

Moreover, ignoring the very small moduli, our experiments reveal an obvious trend. Bearing in mind the y-axis is logarithmic, the straight line indicates an exponential increase in run time as the bit lengths increase linearly. This is not entirely unexpected, because with each bit length we nominally double the size of the moduli and hence the range of number that we iterate over. Extrapolating from this trend, we estimate naive1 would take something like $1.0 \cdot 10^{451}$ seconds to factor a 3072-bit modulus. To put this in to context, the Earth is only $1.4 \cdot 10^{17}$ seconds old.

naive2

We can do better. There are many things we can improve. For our second attempt, naive2, we will focus on our knowledge of RSA moduli to check a smaller range of numbers. In previous blog posts (here and here) we have inferred a number of facts about RSA moduli:

• The modulus always comprises exactly two prime factors.
• The bit length of the prime factors is always exactly half the bit length of the modulus.

From this we can deduce that the smallest prime factor of an RSA moduli, $n$, of bit length $\text{bits}(n)$ is:

Also, unless the modulus is 4 we can safely rule out 2 being a factor and, hence, we do not need to check any even numbers.

Let’s turn our knowledge into code:

import isqrt

def naive2(n):
  # Return 2 for even moduli.
  if n % 2 == 0:
    return 2

  # Start with the same lower and upper bounds as before.
  lb = 2
  ub = n

  # Lower bound is at least 2**(n.bit_length()//2-1).
  lb = max(lb, 2**(n.bit_length()//2-1))
  # Lower bound is at least n // (2**(n.bit_length()//2) - 1).
  lb = max(lb, n // (2**(n.bit_length()//2) - 1))
  # Upper bound is at most isqrt(n) + 1.
  ub = min(ub, isqrt.isqrt(n) + 1)

  # Ensure lb is odd.
  lb = lb + 1 if lb % 2 == 0 else lb

  # Now iterate.
  for i in range(lb, ub, 2):
    if n % i == 0:
      return i

Note that we use the isqrt package to efficiently calculate integer square roots for large integers.³

We have ran naive2 using the same benchmarking tool as before, resulting in the following performance (in red):

You can see that the band of timings is less neat but in general a fair bit faster. The expansion of the band is because we have bounded the range of integers we are checking to the range where the actual prime factors occur and, hence, some of them will occur relatively early in the range and some will occur late. Those that occur early will result in a fast run time.

For additional fun, we have also ran naive2 on PyPy, which compiles the Python code and is generally a lot faster. You can see the performance figures for this in green.

Why Python?

Note that while naive2 is significantly faster than naive1 (arguably by at least two orders of magnitude when running in PyPy) the performance band still roughly follows the same exponential trend we observed for naive1. In practice, this means an algorithm of this kind has no hope of succesfully factorising 3072 bit moduli. Note that even if we implement this algorithm in the most efficient way possible by, e.g., tweaking the divisibility check or implementing everything in assembly code, all this will achieve is bringing the run times down by a constant scaling factor. The run times still scale exponentially. To really solve this problem we need a different kind of algorithm with a different computational complexity.

I have no doubt I’ll present some more elaborate factorisation functions on this blog in the near future – please check back!