crypto

Prompt

Bob wanted to become a famous hacker, that is why he decided to implement a dictionary-based password-guessing algorithm for all users of service Y. He wrote a recursive function func that takes an initial word as input and tests it as a password for accounts on service Y. After that, using a random oracle, it determines the number t, where 0 ⩽ t ⩽ 80. For the given t the function extends the initial word by appending each of the 2t most frequent characters in passwords (according to some statistics) and then calls itself recursively, passing each of these extensions as an argument. To avoid a stack overflow, he limited the depth of function calls to K ⩽ 800: if the number of calls exceeds K, the function does nothing. Next, he just added an infinite loop that calls func and passes an empty string to it. Can you estimate the total number of possible words that Bob’s program tests as passwords?