# Decimal point in keyspace notations? (eg 2^54.15)?

I was reading up on CryptoCat's (pretty ridiculous) programming issues and how is dramatically reduced the key search space (link to bug synopsis)

One thing that caught my eye was

So 2^54.15 turns into 2^27.08

Unless I'm missing something, the impact of the fractional exponent is negligible. So, any ideas why the author is reporting it as 2^54.15 and not just 2^54 ? I mean for O notations, we usually state only the degree of the highest order polynomial (that expresses algorithmic complexity), ignoring the factors and lower order powers.

So am I missing something here when it comes to expression of keyspaces?

-
Looks like being a bit too precise to me. –  CodesInChaos Jul 6 '13 at 17:23

Consider an imaginary runtime of $5x^{2.5} + 2x - 3$. As $x$ gets large this is almost entirely dominated by $x^{2.5}$. However, $x^2$ is significantly smaller than $x^{2.5}$, especially when $x$ gets large - so when notated in Big-O notation this would indeed be $O(x^{2.5})$ or $O(x^{2}\sqrt{x})$.
However, we're not talking about Big-O notation of an algorithm here. We're talking about key spaces, which are of a specific size, rather than a coefficient of something that might be big. So you'll have to decide on a case-by-case basis whether or not the fractional part is "significant" or not. In this case, $2^{27.08}$ is about 5% larger than $2^{27}$. Apparently the author found this difference significant.
Note that the original fraction came into place due to the author insisting on using $2$ as the base of the exponent. The exact keyspace is $2 \cdot 10^{16}$, which is approximately $2^{54.15}$.