1
$\begingroup$

I am trying to calculate how many randomly generated ids I need to produce for there to be a 1% probability I get a duplicate id.

There are $2^{128}$ possible ids.

I understand this is just the birthday problem with a big number:

$0.01=1-\frac{\operatorname{nPr}\left(2^{128},x\right)}{2^{128x}}$

However, I don't know how to solve this algebraically. I cannot plug in values for x and compute the probability because $2^{128}!$ is too large to handle.

Can you show me how to solve this algebraically, or get the numbers small enough to compute? If neither is possible, then how can I get an estimate?

$\endgroup$
5
  • $\begingroup$ For what it's worth, I originally considered using logarithms. However $2^{(128)} \approx (10)^{(39)}$ is such a large number that, after thinking about it, I question this approach. Consequently, after leaving several comments, I deleted them. $\endgroup$
    – user2661923
    Commented May 28, 2021 at 1:34
  • $\begingroup$ $3.419952072579840648562326367\cdot 10^{36}$ connections roughly $\endgroup$
    – Roddy MacPhee
    Commented May 29, 2021 at 19:31
  • $\begingroup$ @RoddyMacPhee that looks bigger than $2^{128}$ - I would have thought something like $2.6 \times 10^{18}$ was more plausible $\endgroup$
    – Henry
    Commented Jul 26, 2021 at 13:14
  • $\begingroup$ Probably messed up the math. Thinking of other problems. $\endgroup$
    – Roddy MacPhee
    Commented Jul 26, 2021 at 13:20
  • $\begingroup$ @RoddyMacPhee so very roughly you need to double your number and take the square root to get mine $\endgroup$
    – Henry
    Commented Jul 26, 2021 at 13:20

0

Reset to default