Preimage Trials

Problem

Return the number of random guesses needed to find a preimage of a hash with the given number of bits with probability at least `probability`:

n = ceil(ln(1 - p) / ln(1 - 1 / 2^bits))

If probability >= 1, return 2^bits as an integer.

Hint

For a 50 percent chance you need about 0.69 * 2^bits guesses.

case 1

in: [8,0.5]

expected: 178

case 2

in: [16,0.5]

expected: 45426

case 3

in: [4,0.5]

expected: 11

case 4

in: [8,0.99]

expected: 1177

Starter codePython

import math
def preimage_trials(bits, probability):
    # Your code here
    pass

4 test cases · run your code against them in the editor