标签: birthday-paradox

我这样做是为了测试randint的随机性:

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

我尝试了大约10倍以上,我得到的最好结果是在转发器之前迭代了121次.这是您从标准库中获得的最佳结果吗？

出于演示目的,在散列时碰撞的几个字符串示例是什么？MD5是一个相对标准的散列选项,所以这就足够了.

我遇到过一些代码，通过 生成多个 UUID UUID.randomUUID()，获取每个 UUID 的最后 7 位数字（最新版本的 UUID 在熵方面是均匀分布的），并使用它作为将行插入数据库的键。

我想知道碰撞的概率是多少。我想起了生日问题。这是这个问题的一个例子，不是吗？一年不是 365 天，而是 16^7 种可能的字符串。然后根据维基百科页面，给定n 个字符串的碰撞概率为

其中d是 16^7。

一位同事声称他们能够毫无问题地插入 50,000 行。我对此表示怀疑，因为与n=50,000和d=16^7发生碰撞的可能性是

1-((16^7-1)/16^7)^(50000*(50000-1)/2) = 99.05%\n

但后来我检查了我们的数据库。确实，50,000 次插入成功了。

这怎么可能？（除此之外，他们真的很幸运。）我是否误用了生日问题？

编辑

这是一个最小的测试，表明应该存在碰撞。

import java.util.UUID;\nimport java.util.HashSet;\n\npublic class MyClass {\n    public static void main(String args[]) {\n        final int N = 50000;\n        for (int trial = 0; trial < 10; trial++) {\n …

我一直在对Random类进行一些测试,我使用了以下代码:

while (x++ <= 5000000)
{
    y = rnd.Next(1, 5000000);
    if (!data.Contains(y))
        data.Add(y);
    else
    {
        Console.WriteLine("Cycle {2}: Repetation found for number {0} after {1} iteration", y, x, i);
        break;
    }
}

我一直在改变rnd max limit(即5000000),我改变了迭代次数,得到了以下结果:

1) if y = rnd.Next(1, 5000) : The average is between 80 to 110 iterations
2) if y = rnd.Next(1, 5000000) : The average is between 2000 to 4000 iterations
3) if y = rnd.Next(1, int.MaxValue) : The average is between 40,000 to 80,000 iterations.

为什么我得到这些平均值,即我检查每个值的10次,80%的时间都在这个平均范围内.我不认为我们可以把它称为随机. …

我正在寻找一些关于基于生日悖论的 MD5、SHA1 和 SHA256 碰撞可能性的精确数学。

我正在寻找类似图表，上面写着“如果你有 10^8 个键，这是概率。如果你有 10^13 个键，这就是概率等等”

我查看了大量文章，但我很难找到可以提供这些数据的内容。（对我来说理想的选择是计算任何提供的哈希大小的公式或代码）

这基本上是一个数学问题,但编程很相关:如果我有10亿个包含URL的字符串,并且我采用每个字符串的MD5哈希的前64位,我应该期望什么样的冲突频率？

如果我只有1亿个网址,答案会如何变化？

在我看来,碰撞将非常罕见,但这些事情往往令人困惑.

使用MD5以外的其他东西会更好吗？请注意,我不是在寻找安全性,只是一个很好的快速哈希函数.此外,MySQL中的本机支持很好.

编辑:不太重复

我需要编写一个随机字符串生成类,它从31个字符的字符集和一些字母表中生成7char字符串(10 + 26-5,省略5个元音).简单的数学给出了一组31 ^ 7种可能的组合~275亿.我对bday悖论有疑问,我进行了一些测试,重复数量呈指数级增长.我可以做些什么来避免这种情况吗？

At 1 million, duplicates encountered till now = 19
At 2 million, duplicates encountered till now = 69
At 3 million, duplicates encountered till now = 157
At 4 million, duplicates encountered till now = 280
At 5 million, duplicates encountered till now = 470
At 6 million, duplicates encountered till now = 662
At 7 million, duplicates encountered till now = 896
At 8 million, duplicates encountered till now = 1185
At 9 million, …

请帮助解释维基百科中描述的生日效果:

生日攻击的工作原理如下:

1. 选择任何消息m并计算h(m).
2. 更新清单L.检查h(m)是否在列表L中.
3. 如果(h(m),m)已经在L中,则找到了冲突消息对.否则将对(h(m),m)保存在列表L中并返回步骤1.

从生日悖论我们知道,在执行大约2 ^(n/2)个哈希评估之后,我们可以期望找到匹配的条目.

以上是否意味着通过上述整个循环的2 ^(n/2)次迭代(即2 ^(n/2)返回到步骤1),或者它是否意味着对已经在L中的各个项目的2 ^(n/2)次比较？

对于10个整数的列表,有10个!可能的订单或排列.为什么random.shuffle仅在5000次尝试后会给出重复项？

>>> L = range(10)
>>> rL = list()
>>> for i in range(5000):
...     random.shuffle(L)
...     rL.append(L[:])
... 
>>> rL = [tuple(e) for e in rL]
>>> len(set(rL))
4997
>>> for i,t in enumerate(rL):
...     if rL.count(t) > 1:
...         print i,t
... 
102 (7, 5, 2, 4, 0, 6, 9, 3, 1, 8)
258 (1, 4, 0, 2, 7, 3, 5, 9, 6, 8)
892 (1, 4, 0, 2, 7, 3, 5, 9, 6, 8)
2878 (7, 5, …

我正试图用Python解决生日悖论.我很接近,但最后一块让我感到茫然.我正在使用随机生成给定范围和要创建的项目数的数字列表.这样可行.

然后我检查列表(上面生成的)是否有重复.这样可行.

然后我尝试生成给定(n)列表.这是我遇到麻烦的地方.它生成一个列表然后返回"NoneType"不可迭代.令我困惑的是,列表已生成,但Python并未将其视为列表.

这是代码:

def make_bd(n, r):
    """Generates (r) numbers of birthdays in a range (n)."""
    import random
    t = [random.randrange(n) for i in range(r)]
    print (t)


def has_dupe(test):
    """Here I test to see if I can detect a duplicate birthday.
This is based on problem #4."""

    d = []
    count = 0
    for number in test:
        if number in d:
            count = count + 1
        d.append(number)
    if count >= 1:
        return True
    return False

def dupebd(n,r,t):
    count_dupe = 0 …