work factor calculation for brute-forcing crypto

David Malone dwmalone at
Sun Jul 19 07:43:33 EDT 2009

On Fri, Jul 17, 2009 at 01:37:43PM -0500, travis+ml-cryptography at wrote:
> I'm curious if there's a way to express this calculation as a
> mathematical formula, rather than an algorithm, but right now I'm just
> blanking on how I could do it.

This has been dubbed the "guesswork" of a distribution by some authors,
I think originating with:

	John O. Pliam. The disparity between work and entropy in
	February 1999

It turns out that its asymoptic behaviour is bit like that of Renyi
entropy, see:

	E. Arikan. An inequality on guessing and its application
	to sequential decoding. IEEE Transactions on Information
	Theory, 42:99105, Janurary 1996.

I did an explanitory writeup of this with some experiments at:


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list