How many bits should a token have to be unguessable (given some computational resources)? If an attacker may try 10 billion (1E10) random numbers per second.
And its attack can last 500 years (500*365*24*3600 = 1.5768E10 seconds).

Then the attacker will try 1E10*1.5768E10 = 1.5768E20 combinations.

Now suppose I have 100 billion (1E11) tokens, which are random numbers of n bits.

I want to calculate n so that the probability the attacker finds any token is around 1 in a billion (1E9).

I believe the answer is n = log2(1E11*1.5768E20/1E9) = 73.74 bits.

Questions:


Is this calculation correct?
If instead of independent random numbers the attacker can avoid repeating numbers, how much is n? I guess I should use factorials, and I guess this relates to the birthday paradox, but my mathematics seems to escape me know.
If simply knowing one of the tokens serves as authentication, what is the recommended n for an attacker with a few million dollars available, as of 2017?


Update:

By using the formula in https://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions, with my specific numbers, in WolphramAlpha, I get: sqrt(2*(2^n)*ln(1/(1-(1/1E9))))=1.5768E20.

Wolphram solves for n: n=163.088. I guess this is the answer to my question 2. I think my calculation for question 1 is correct, but since question 2 is the more realistic scenario I am satisfied with that and will close this question.
Well whilst AES can take 256 bit keys, it still only accepts a 128 bit IV. And the width of the AES block is considered secure in 2017. So that would be a good guide.

Also, there are type 4 UUIDs that use 122 bits of uncertainty and are currently in widespread use.  There's not a lot more to say other than to extract this from my reference:-


  Thus, for there to be a one in a billion chance of duplication, 103 trillion version 4 UUIDs must be generated.


Increasing the size to 128 bits would require 8e14 tokens for the same 1 in a billion risk of collision. Should be okay.