Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Looks like being a bit too precise to me. –  CodesInChaos Jul 6 '13 at 17:23
add comment

1 Answer

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.

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.