In this post on cracking md5crypt hashes, I listed the sizes of a number of password search spaces as exponents of 10, e.g. 1.9 * 10¹⁷, but I realize now that there’s a much better way to discuss large search spaces. I’ve been taking a Stanford online course on cryptography over the last couple months which has made me realize, among many other things, that it’s much more useful to think in powers of two in matters of cryptography, computing, and information theory in general.

However, powers of ten are easy to deal with in back-of-the-envelope calculations, and many articles/papers/posts deal in powers of ten. I had no idea how to convert from 10^x to 2^y in any straightforward fashion, so I talked to a couple friends with much stronger math backgrounds than mine and did a bit of reading. Here’s what I found:

For x = 2n, we want to solve for n.
The solution:
n = log(x) / log(2)
For example:
log(1017) / log(2) = 56.472777613085164
thus
1017 ≈ 256

N.B. that’s a very rough approximation at that scale. Definitely good enough for the purposes of estimating the nearest power of two, but worth keeping in mind there’s still a large difference (well, exactly double) between any two integer powers of two.

I was confused about the log operations – is this log base-10? if not, what actual operation is taking place? Turns out it’s the natural logarithm, aka log_e x. However, it’s not actually important that this is base-e, just that the base of both logarithm operations is the same – it cancels out. We can show this in Python, where a base can be provided as an optional second argument to math.log:

>>> log(10000) / log(2)
13.28771237954945
>>> log(10000, 10) / log(2, 10)
13.287712379549452

How to actually use this in practice? Lots of ways:

Wolfram Alpha:

Python:

Javascript:

OS X spotlight (different result…?):

UPDATE 2015-12-29:

I wrote a command-line tool to do this conversion quickly, on GitHub here. It’s in my PATH so I can do this:

[tkerr@pro ~]$ tentotwo 39
10 ^ 39   =   2 ^ 129.55519570060713   ≈  2 ^ 130
[tkerr@pro ~]$ tentotwo -r 128
2 ^ 128   =   10 ^ 38.531839444989586   ≈  10 ^ 39