← all shorts

Math

The Birthday Paradox

#183 · 4 min read

In a gathering of just 23 individuals, the chances that two of them share the same birthday tip beyond 50%. This statistical quirk, known as the Birthday Paradox, confounds intuition, yet its implications extend from classroom rosters to the security of digital systems.

A curious truth emerges from the mathematics of probability: bring 23 people together, and there's a greater than even chance that two of them celebrate their birth on the very same day. This statistical anomaly, often termed the birthday problem, frequently surprises, running counter to our everyday estimations of likelihood.

Our intuition often misleads us here, suggesting that with 365 possible days, one would need a much larger group to find a match. The error lies in how we frame the question. We are not looking for someone to share *our* birthday, but for *any* two people within the group to share *any* common birthday. The distinction shifts the focus from 23 individual comparisons to the multitude of possible pairings. Among those 23 individuals, there exist 253 unique pairs, each a potential point of coincidence. As the number of these pairings grows rapidly with each additional person, the probability of a shared date escalates far more quickly than anticipated.

The underlying calculation hinges on the complementary event: the probability that *no two* people share a birthday. For the first person, the probability of having a unique birthday is 365/365. For the second, it's 364/365, as they must avoid the first person's day. The third must avoid two days (363/365), and so on. Multiplying these decreasing fractions yields the probability of *no shared birthdays*. Subtracting this from one reveals the probability of at least one shared birthday. At 23 people, this crosses the 50% threshold, reaching approximately 50.7%. By the time a group reaches 70 people, the probability of a shared birthday exceeds 99.9%, a near certainty.

Beyond the Classroom: Cryptographic Attacks

The implications of this probabilistic phenomenon stretch beyond party tricks and classroom demographics. In computer science, particularly cryptography, the birthday problem underpins a significant vulnerability known as the birthday attack. This attack exploits the same mathematical principle to find collisions in hash function outputs. A hash function takes an input (like a message or a file) and produces a fixed-size string of characters, its "hash," which serves as a unique digital fingerprint. Ideally, different inputs should produce different hashes.

However, just as with birthdays, if enough inputs are hashed, the probability of two different inputs yielding the same hash value—a collision—increases dramatically due to the sheer number of possible pairings. An attacker can generate numerous variations of a legitimate message and numerous variations of a malicious message, hoping that a pair (one legitimate, one malicious) hashes to the same value. The birthday paradox ensures that finding such a collision requires far fewer attempts than one might intuitively expect, often the square root of the total possible hash outputs, rather than half. This means a 128-bit hash function, which theoretically has 2^128 possible outputs, can be vulnerable to a birthday attack with around 2^64 operations, making it computationally feasible for certain algorithms.

What we still don't know

While the core mathematical principle of the birthday paradox is well-understood, its real-world application still presents nuances. Most calculations assume a uniform distribution of birthdays throughout the year, ignoring factors like seasonal birth rate variations, leap years, or the slightly higher prevalence of some birth dates due to medical interventions. While these factors can subtly shift the probabilities, they rarely invalidate the paradox's fundamental premise, often leading to an *earlier* probability of collision.

Furthermore, extending the paradox to higher-order collisions—finding three, four, or more people sharing a birthday—rapidly increases the required group size. While the probability of two people sharing a birthday crosses 50% at 23 individuals, finding three people with the same birthday requires a group of 88, and four people requires 187. The intuitive leap between these probabilities remains a cognitive challenge, highlighting the persistent counter-intuitive nature of the paradox.

A concept often confused with the birthday problem is the pigeonhole principle. While related to the distribution of items into containers, the pigeonhole principle states that if `n` items are put into `m` containers, with `n > m`, then at least one container must contain more than one item. This guarantees a collision when the number of people exceeds the number of days (e.g., 366 people guarantee a shared birthday), but it doesn't quantify the probability of collisions *before* that point, which is what the birthday paradox addresses.

The Birthday Paradox, while seemingly a simple mathematical curiosity, subtly reshapes our understanding of chance, demonstrating how the hidden network of potential connections can swiftly elevate the improbable to the inevitable.

在仅有23个人的聚会上,其中两人拥有相同生日的概率会超过50%。这种被称为“生日悖论”的统计现象,挑战了人们的直觉,但其影响却从课堂名册延伸到了数字系统的安全领域。

概率论中出现了一个引人深思的事实:只要聚集23个人,其中就有大于一半的几率,两个人的生日会落在同一天。这种统计学上的异常现象,通常被称为birthday problem,经常令人惊讶,与我们对可能性的日常估计相悖。

在这里,我们的直觉常常误导我们,认为在365天中,需要一个更大的群体才能找到匹配。错误在于我们如何提出问题。我们不是在寻找与*我们*生日相同的人,而是在群体中寻找*任何*两个人共享*任何*共同生日。这一区别将焦点从23个单独的比较转向了众多可能的配对。在23个人中,存在253个独特的配对,每一个都可能是巧合的节点。随着人数的增加,这些配对的数量迅速增长,共享日期的概率也比预期更快地上升。

核心计算依赖于互补事件:即*没有两个人*共享生日的概率。对于第一个人,拥有独特生日的概率是365/365。对于第二个人,他们必须避开第一个人的日期,概率是364/365。第三个人必须避开两个日期(363/365),依此类推。将这些递减的分数相乘,就得到了*没有共享生日*的概率。从1中减去这个概率,就得到了至少有一个共享生日的概率。当人数达到23人时,这个概率就超过了50%的门槛,达到大约50.7%。当一个群体达到70人时,共享生日的概率超过99.9%,几乎可以确定。

课堂之外:密码学攻击

这种概率现象的影响远远超出了聚会游戏和课堂人口统计。在计算机科学中,尤其是在cryptographybirthday problem构成了一个重要的漏洞,称为birthday attack。这种攻击利用相同的数学原理来在hash function输出中找到冲突。哈希函数接受一个输入(比如一条消息或一个文件),并生成一个固定大小的字符字符串,即它的“哈希”,作为唯一的数字指纹。理想情况下,不同的输入应该产生不同的哈希值。

然而,就像生日一样,如果足够多的输入被哈希处理,由于可能配对数量的巨大,两个不同输入产生相同哈希值的概率——即冲突——会急剧增加。攻击者可以生成大量合法消息的变体和大量恶意消息的变体,希望找到一对(一个合法,一个恶意)哈希值相同。生日悖论确保了找到这种冲突所需的尝试次数远少于人们直觉上的预期,通常为总可能哈希输出的平方根,而不是一半。这意味着一个理论上拥有2^128种可能输出的128位哈希函数,可能会在大约2^64次操作中受到生日攻击,使得某些算法在计算上变得可行。

我们仍不了解的

尽管生日悖论的核心数学原理已经广为人知,但其在现实世界中的应用仍然存在细微之处。大多数计算假设一年中生日分布是均匀的,忽略了诸如季节性出生率变化、闰年或由于医疗干预导致某些出生日期稍高的因素。虽然这些因素可以微妙地改变概率,但它们很少会推翻悖论的基本前提,通常会导致*更早*的碰撞概率。

此外,将悖论扩展到高阶碰撞——找到三个人、四个人或更多人共享生日——迅速增加了所需群体的大小。虽然两个人共享生日的概率在23人时超过50%,但找到三个人共享生日需要88人,四个人则需要187人。这些概率之间的直觉跳跃仍然是一个认知挑战,突显了悖论的持续反直觉性。

经常与生日问题混淆的一个概念是pigeonhole principle。虽然与将物品分配到容器中有关,鸽巢原理指出,如果将`n`个物品放入`m`个容器中,且`n > m`,那么至少有一个容器必须包含不止一个物品。这保证了当人数超过天数时(例如366人保证有共享生日)会发生冲突,但它并没有量化在这一点之前冲突的概率,而这正是生日悖论所关注的。

生日悖论虽然看似一个简单的数学奇观,却微妙地重塑了我们对机会的理解,展示了潜在连接网络如何迅速将不可能变为必然。

En un grupo de tan solo 23 personas, las probabilidades de que dos de ellas celebren su cumpleaños el mismo día superan el 50%. Este fenómeno estadístico, conocido como el [[Paradoja Natalicia]], desconcierta la intuición, pero sus implicaciones abarcan desde las listas escolares hasta la seguridad de los sistemas digitales.

Una curiosa verdad emerge de las matemáticas de la probabilidad: reunir a 23 personas implica una probabilidad mayor al 50 % de que dos de ellas celebren su nacimiento el mismo día. Esta anomalía estadística, a menudo denominada el birthday problem, frecuentemente sorprende, contradiciendo nuestras estimaciones cotidianas sobre la probabilidad.

Nuestra intuición suele engañarnos aquí, sugiriendo que, con 365 días posibles, se necesitaría un grupo mucho mayor para encontrar una coincidencia. El error radica en cómo formulamos la pregunta. No estamos buscando a alguien que comparta *nuestro* cumpleaños, sino que estemos buscando a *dos personas* dentro del grupo que compartan *cualquier* cumpleaños común. Esta distinción desplaza el enfoque de 23 comparaciones individuales a la multitud de posibles parejas. Entre esos 23 individuos, existen 253 pares únicos, cada uno un posible punto de coincidencia. A medida que el número de estas parejas crece rápidamente con cada persona adicional, la probabilidad de una fecha compartida aumenta mucho más rápido de lo esperado.

El cálculo subyacente se basa en el evento complementario: la probabilidad de que *ninguna* de las personas comparta un cumpleaños. Para la primera persona, la probabilidad de tener un cumpleaños único es 365/365. Para la segunda, es 364/365, ya que debe evitar el día de la primera persona. La tercera debe evitar dos días (363/365), y así sucesivamente. Multiplicar estas fracciones decrecientes da la probabilidad de *ningún cumpleaños compartido*. Restar esto de uno revela la probabilidad de al menos un cumpleaños compartido. Con 23 personas, esta probabilidad cruza el umbral del 50 %, alcanzando aproximadamente el 50,7 %. Para cuando un grupo alcanza los 70 miembros, la probabilidad de un cumpleaños compartido supera el 99,9 %, casi una certeza.

Más allá del aula: ataques criptográficos

Las implicaciones de este fenómeno probabilístico se extienden más allá de los trucos de fiestas y la demografía escolar. En ciencias de la computación, especialmente cryptography, el birthday problem subyace a una vulnerabilidad significativa conocida como el birthday attack. Este ataque explota el mismo principio matemático para encontrar colisiones en los hash function. Una función hash toma una entrada (como un mensaje o un archivo) y produce una cadena fija de caracteres, su "hash", que sirve como una huella digital única. Idealmente, diferentes entradas deberían producir diferentes hashes.

Sin embargo, al igual que con los cumpleaños, si se hashifican suficientes entradas, la probabilidad de que dos entradas diferentes produzcan el mismo valor hash —una colisión— aumenta dramáticamente debido al gran número de posibles parejas. Un atacante puede generar numerosas variaciones de un mensaje legítimo y de un mensaje malicioso, esperando que un par (uno legítimo, uno malicioso) se hashifique al mismo valor. La paradoja del cumpleaños asegura que encontrar tal colisión requiere muchas menos intentos de los que se podría esperar intuitivamente, a menudo la raíz cuadrada del total de posibles salidas hash, en lugar de la mitad. Esto significa que una función hash de 128 bits, que teóricamente tiene 2^128 posibles salidas, puede ser vulnerable a un ataque de cumpleaños con alrededor de 2^64 operaciones, haciendo que sea computacionalmente factible para ciertos algoritmos.

Lo que aún no sabemos

Aunque el principio matemático fundamental de la paradoja del cumpleaños está bien comprendido, su aplicación en el mundo real aún presenta matices. La mayoría de los cálculos asumen una distribución uniforme de cumpleaños a lo largo del año, ignorando factores como las variaciones estacionales en las tasas de nacimiento, los años bisiestos o la ligeramente mayor prevalencia de ciertas fechas de nacimiento debido a intervenciones médicas. Aunque estos factores pueden desplazar ligeramente las probabilidades, rara vez invalidan el principio fundamental de la paradoja, a menudo conduciendo a una *probabilidad de colisión más temprana*.

Además, extender la paradoja a colisiones de orden superior —encontrar tres, cuatro o más personas que compartan un cumpleaños— aumenta rápidamente el tamaño del grupo necesario. Mientras que la probabilidad de que dos personas compartan un cumpleaños cruza el 50 % con 23 individuos, encontrar tres personas con el mismo cumpleaños requiere un grupo de 88, y cuatro personas requieren 187. El salto intuitivo entre estas probabilidades sigue siendo un desafío cognitivo, destacando la persistente naturaleza contraintuitiva de la paradoja.

Un concepto a menudo confundido con el problema del cumpleaños es el pigeonhole principle. Aunque relacionado con la distribución de elementos en contenedores, el principio del palomar establece que si se colocan `n` elementos en `m` contenedores, con `n > m`, entonces al menos un contenedor debe contener más de un elemento. Esto garantiza una colisión cuando el número de personas excede el número de días (por ejemplo, 366 personas garantizan un cumpleaños compartido), pero no cuantifica la probabilidad de colisiones *antes* de ese punto, que es lo que aborda la paradoja del cumpleaños.

La paradoja del cumpleaños, aunque aparentemente una simple curiosidad matemática, modifica sutilmente nuestra comprensión del azar, demostrando cómo la red oculta de posibles conexiones puede elevar rápidamente lo improbable a lo inevitable.

Num encontro de apenas 23 pessoas, as chances de que duas delas compartilhem a mesma data de nascimento ultrapassam 50%. Esse peculiar fenómeno estatístico, conhecido como [[Paradoxo do Aniversário]], desafia a intuição, mas suas implicações se estendem desde listas escolares até a segurança dos sistemas digitais.

Uma verdade curiosa emerge das matemáticas da probabilidade: reúna 23 pessoas, e há uma chance maior do que a metade de que duas delas celebrem seu nascimento no mesmo dia. Essa anomalia estatística, frequentemente chamada de birthday problem, surpreende com frequência, contrariando nossas estimativas cotidianas de probabilidade.

Nossa intuição costuma nos enganar aqui, sugerindo que, com 365 possíveis dias, seria necessária uma grupo muito maior para encontrar uma coincidência. O erro está em como formulamos a pergunta. Não estamos procurando alguém que compartilhe *nosso* aniversário, mas sim *qualquer* duas pessoas dentro do grupo que compartilhem *qualquer* aniversário comum. A distinção muda o foco de 23 comparações individuais para o número imenso de possíveis pares. Entre aqueles 23 indivíduos, existem 253 pares únicos, cada um um potencial ponto de coincidência. À medida que o número desses pares cresce rapidamente com cada pessoa adicional, a probabilidade de uma data compartilhada aumenta muito mais rapidamente do que se espera.

O cálculo subjacente baseia-se no evento complementar: a probabilidade de que *nenhuma* das pessoas compartilhe um aniversário. Para a primeira pessoa, a probabilidade de ter um aniversário único é 365/365. Para a segunda, é 364/365, pois ela deve evitar o dia da primeira pessoa. A terceira deve evitar dois dias (363/365), e assim por diante. Multiplicando essas frações decrescentes, obtemos a probabilidade de *nenhum aniversário compartilhado*. Subtraindo isso de um, revelamos a probabilidade de ao menos um aniversário compartilhado. Com 23 pessoas, isso ultrapassa a marca de 50%, atingindo aproximadamente 50,7%. Quando um grupo chega a 70 pessoas, a probabilidade de um aniversário compartilhado excede 99,9%, uma praticamente certeza.

Além da sala de aula: ataques criptográficos

As implicações dessa fenômeno probabilístico estendem-se além de brincadeiras em festas e da demografia em salas de aula. Em ciência da computação, particularmente cryptography, o birthday problem fundamenta uma vulnerabilidade significativa conhecida como birthday attack. Esse ataque explora o mesmo princípio matemático para encontrar colisões nas saídas de hash function. Uma função de hash recebe uma entrada (como uma mensagem ou um arquivo) e produz uma string fixa de caracteres, seu "hash", que serve como uma impressão digital digital única. Idealmente, entradas diferentes devem produzir hashes diferentes.

No entanto, assim como com aniversários, se o suficiente entradas forem hashadas, a probabilidade de duas entradas diferentes gerarem o mesmo valor de hash — uma colisão — aumenta dramaticamente devido ao número imenso de possíveis pares. Um atacante pode gerar numerosas variações de uma mensagem legítima e numerosas variações de uma mensagem maliciosa, esperando que um par (uma legítima, uma maliciosa) gere o mesmo valor de hash. A paradoxo do aniversário garante que encontrar tal colisão exige muito menos tentativas do que se poderia intuitivamente esperar, frequentemente a raiz quadrada do número total de saídas de hash possíveis, em vez da metade. Isso significa que uma função de hash de 128 bits, que teoricamente tem 2^128 saídas possíveis, pode ser vulnerável a um ataque de aniversário com cerca de 2^64 operações, tornando-a computacionalmente viável para certos algoritmos.

O que ainda não sabemos

Embora o princípio matemático fundamental do paradoxo do aniversário seja bem compreendido, sua aplicação no mundo real ainda apresenta nuances. A maioria dos cálculos assume uma distribuição uniforme de aniversários ao longo do ano, ignorando fatores como variações estacionais nas taxas de nascimento, anos bissextos ou a ligeiramente maior ocorrência de certas datas de nascimento devido a intervenções médicas. Embora esses fatores possam deslocar discretamente as probabilidades, raramente invalidam a premissa fundamental do paradoxo, frequentemente levando a uma *probabilidade de colisão mais cedo*.

Além disso, estender o paradoxo para colisões de ordem superior — encontrar três, quatro ou mais pessoas compartilhando um aniversário — aumenta rapidamente o tamanho do grupo necessário. Enquanto a probabilidade de duas pessoas compartilharem um aniversário ultrapassa 50% com 23 indivíduos, encontrar três pessoas com o mesmo aniversário exige um grupo de 88, e quatro pessoas exigem 187. O salto intuitivo entre essas probabilidades permanece um desafio cognitivo, destacando a persistente natureza contra-intuitiva do paradoxo.

Um conceito frequentemente confundido com o problema do aniversário é o pigeonhole principle. Embora relacionado à distribuição de itens em recipientes, o princípio da casa dos pombos afirma que se `n` itens forem colocados em `m` recipientes, com `n > m`, então pelo menos um recipiente deve conter mais de um item. Isso garante uma colisão quando o número de pessoas excede o número de dias (por exemplo, 366 pessoas garantem um aniversário compartilhado), mas não quantifica a probabilidade de colisões *antes* desse ponto, que é o que o paradoxo do aniversário aborda.

O Paradoxo do Aniversário, embora aparentemente uma curiosidade matemática simples, molda discretamente nossa compreensão do acaso, demonstrando como a rede oculta de conexões potenciais pode elevar rapidamente o improvável ao inevitável.

23人ほどの集まりに、同じ誕生日の人がいる確率は50%を上回る。この統計的な奇跡は「誕生日パラドックス」と呼ばれ、直感を裏切るが、その影響は学級の名簿からデジタルシステムのセキュリティに至るまで広がっている。

確率の数学から興味深い真実が浮かび上がってくる。23人を一緒にすると、その中に同じ誕生日を持つ2人がいる確率は50%以上になるのだ。この統計的異常現象はしばしば「birthday problem」と呼ばれるが、この現象は日常的な確からしさの見積もりと反対の結果を生み出すため、多くの人々を驚かせる。

我々の直感はここでしばしば誤る。365日ある中で、同じ誕生日を持つ人がいるためにははるかに多くの人数が必要だと考えるのが自然である。しかし、この誤りは問題をどう立てているかに依存している。我々が探しているのは、自分自身の誕生日と一致する人がいることではなく、グループの中の誰かと誰かが同じ誕生日を持っていることである。この違いにより、23人の比較という個別的な検討から、多数のペアの可能性に焦点が移る。23人の中には253のペアが存在し、それぞれが偶然の点となる。このペアの数は、1人1人人数が増えるごとに急速に増加し、共有される誕生日の確率は予測よりもはるかに速く上昇する。

この計算の根幹には補集合の事象が存在する。つまり、誰も同じ誕生日を持っていない確率を計算するのである。最初の人は365/365の確率で独自の誕生日を持つ。2人目は最初の人の誕生日を避ける必要があるため、364/365の確率となる。3人目は2つの日を避ける必要があるため、363/365となり、以下同様に進む。これらの減少する分数を掛け合わせることで、誰も同じ誕生日を持っていない確率が得られる。これを1から引くと、少なくとも1組の同じ誕生日を持つ確率が求められる。23人の場合、この確率は50%の閾値を越え、約50.7%になる。70人になると、同じ誕生日を持つ確率は99.9%を超え、ほぼ確実になる。

教室の外へ:暗号攻撃

この確率論的現象の影響は、パーティーのトリックや教室での人口統計学にとどまらない。コンピュータ科学、特にcryptographyにおいて、birthday problemは「birthday attack」と呼ばれる重大な脆弱性の基盤となる。この攻撃は、同じ数学的原理を用いてhash functionの出力における衝突を発見する。ハッシュ関数は入力(メッセージやファイルなど)を受け取り、固定長の文字列である「ハッシュ」を生成し、それは一意的なデジタル指紋として機能する。理想的には、異なる入力は異なるハッシュを生成すべきである。

しかし、誕生日と同様に、十分な数の入力をハッシュ化すると、ペアの可能性の数が膨大になるため、異なる入力が同じハッシュ値を生成する衝突の確率が急激に増加する。攻撃者は、合法的なメッセージのバリエーションと悪意のあるメッセージのバリエーションを多数生成し、合法的なものと悪意のあるもののペアが同じハッシュ値になることを狙う。誕生日のパラドックスにより、このような衝突を発見するためには直感的に予測されるよりもはるかに少ない試行回数で済む。通常は全ハッシュ出力の平方根程度の試行回数で済むため、理論上は2^128の出力を持つ128ビットのハッシュ関数であっても、約2^64の操作で誕生日攻撃が可能となり、特定のアルゴリズムにとっては計算的に現実的な攻撃となる。

まだわかっていないこと

誕生日パラドックスの核心となる数学的原理はよく理解されているが、その現実世界への応用にはまだ微妙な点が残っている。ほとんどの計算は年間を通じて誕生日が均等に分布していることを前提としており、季節による出生率の変動や閏年、あるいは医療的介入によって一部の日付がやや多いといった要因を無視している。これらの要因は確率に僅かながら影響を与えるが、パラドックスの基本的な前提を無効化することはほとんどなく、むしろ衝突の確率がより早く現れる傾向がある。

さらに、このパラドックスを3人、4人、あるいはそれ以上の人数が同じ誕生日を持つような高次の衝突に拡張すると、必要なグループの規模が急激に増える。2人が同じ誕生日を持つ確率が23人で50%を超えるのに対し、3人が同じ誕生日を持つには88人、4人が同じ誕生日を持つには187人必要となる。これらの確率の間の直感的な飛躍は依然として認知的課題であり、このパラドックスが持つ反直感的な性質が際立つ。

しばしば誕生日問題と混同される概念に「pigeonhole principle」がある。これは物の分布に関するものであり、n個の物をm個の箱に入れるとき、n > mであれば少なくとも1つの箱には2つ以上の物が入ることを主張する。これは人数が日数を超えた場合(例えば366人)に衝突が保証されるが、その時点以前での衝突の確率を定量的に示すものではない。これは誕生日パラドックスが扱う問題とは異なる。

誕生日パラドックスは、単なる数学的好奇心に過ぎないように見えるが、潜在的な接続のネットワークがいかに迅速に不可能なことを必然に変えるかを、我々の確率理解を静かに再構築する。

Dans un regroupement de seulement 23 individus, les chances que deux d'entre eux partagent la même date d'anniversaire dépassent 50%. Ce phénomène statistique, connu sous le nom de [[Paradoxe des anniversaires]], défie l'intuition, mais ses implications s'étendent des listes de classes à la sécurité des systèmes numériques.

Une vérité curieuse émerge des mathématiques de la probabilité : rassemblez 23 personnes, et il y a plus d'une chance sur deux que deux d'entre elles célèbrent leur naissance le même jour. Cette anomalie statistique, souvent appelée le birthday problem, surprend fréquemment, allant à l'encontre de nos estimations quotidiennes de la probabilité.

Notre intuition nous trompe ici, suggérant qu'avec 365 jours possibles, il faudrait un groupe bien plus grand pour trouver une coïncidence. L'erreur réside dans la manière dont nous formulons la question. Nous ne cherchons pas quelqu'un partageant *notre* anniversaire, mais deux personnes quelconques du groupe partageant *n'importe quel* jour commun. Cette distinction déplace le point de vue de 23 comparaisons individuelles vers un grand nombre de combinaisons possibles. Parmi ces 23 personnes, il existe 253 paires uniques, chacune représentant un potentiel point de coïncidence. Alors que le nombre de ces combinaisons croît rapidement avec chaque personne additionnelle, la probabilité d'une date partagée augmente bien plus rapidement qu'on ne l'attend.

Le calcul sous-jacent repose sur l'événement complémentaire : la probabilité qu'*aucune* paire de personnes ne partage une date d'anniversaire. Pour la première personne, la probabilité d'avoir une date unique est 365/365. Pour la deuxième, elle est de 364/365, car elle doit éviter la date de la première. La troisième doit éviter deux dates (363/365), et ainsi de suite. En multipliant ces fractions décroissantes, on obtient la probabilité d'*absence de dates partagées*. En la soustrayant à un, on obtient la probabilité d'au moins une date partagée. À 23 personnes, cette probabilité dépasse le seuil des 50 %, atteignant environ 50,7 %. Lorsqu'un groupe atteint 70 personnes, la probabilité d'une date partagée dépasse 99,9 %, une certitude presque totale.

Au-delà de la salle de classe : les attaques cryptographiques

Les implications de ce phénomène probabiliste dépassent les tours de magie et les statistiques de classe. En informatique, particulièrement cryptography, le birthday problem sous-tend une vulnérabilité majeure connue sous le nom de birthday attack. Cette attaque exploite le même principe mathématique pour trouver des collisions dans les sorties de hash function. Une fonction de hachage prend une entrée (comme un message ou un fichier) et produit une chaîne de caractères de longueur fixe, son « haché », qui sert d'empreinte numérique unique. Idéalement, des entrées différentes devraient produire des hachés différents.

Cependant, tout comme avec les anniversaires, si suffisamment d'entrées sont hachées, la probabilité que deux entrées différentes produisent la même valeur de hachage — une collision — augmente dramatiquement en raison du nombre énorme de combinaisons possibles. Un attaquant peut générer de nombreuses variantes d'un message légitime et de nombreuses variantes d'un message malveillant, espérant qu'une paire (une légitime, une malveillante) produise la même valeur de hachage. Le paradoxe des anniversaires garantit que trouver une telle collision nécessite bien moins d'essais qu'on ne pourrait intuitivement le penser, souvent la racine carrée du nombre total de sorties possibles, plutôt que la moitié. Cela signifie qu'une fonction de hachage de 128 bits, qui théoriquement possède 2^128 sorties possibles, peut être vulnérable à une attaque d'anniversaire avec environ 2^64 opérations, rendant cela calculablement réalisable pour certains algorithmes.

Ce que nous ne savons toujours pas

Bien que le principe mathématique fondamental du paradoxe des anniversaires soit bien compris, son application dans le monde réel présente encore des nuances. La plupart des calculs supposent une distribution uniforme des anniversaires tout au long de l'année, ignorant des facteurs comme les variations saisonnières des taux de naissance, les années bissextiles, ou la légère prédominance de certaines dates dûe à des interventions médicales. Bien que ces facteurs puissent subtilement modifier les probabilités, ils ne rendent presque jamais invalide le principe fondamental du paradoxe, souvent conduisant à une *probabilité de collision plus précoce*.

De plus, l'extension du paradoxe aux collisions d'ordre supérieur — trouver trois, quatre, ou plus de personnes partageant un même anniversaire — augmente rapidement la taille du groupe nécessaire. Alors que la probabilité de deux personnes partageant une date d'anniversaire dépasse 50 % avec 23 individus, trouver trois personnes partageant la même date nécessite un groupe de 88 personnes, et quatre personnes nécessitent 187. Le saut intuitif entre ces probabilités reste un défi cognitif, soulignant la nature persistante contre-intuitive du paradoxe.

Un concept souvent confondu avec le problème des anniversaires est le pigeonhole principle. Bien qu'en lien avec la distribution d'objets dans des conteneurs, le principe des tiroirs affirme que si `n` objets sont placés dans `m` conteneurs, avec `n > m`, alors au moins un conteneur doit contenir plus d'un objet. Cela garantit une collision lorsque le nombre de personnes dépasse celui des jours (par exemple, 366 personnes garantissent un anniversaire partagé), mais il ne quantifie pas la probabilité de collisions *avant* ce point, ce que le paradoxe des anniversaires traite précisément.

Le paradoxe des anniversaires, bien qu'apparemment une simple curiosité mathématique, modifie subtilement notre compréhension du hasard, démontrant comment le réseau caché de connexions potentielles peut rapidement élever l'improbable à l'inévitable.

Dalam sebuah pertemuan hanya 23 individu, peluang bahwa dua dari mereka berbagi tanggal lahir melampaui 50%. Keanehan statistik ini, yang dikenal sebagai Paradox Ulang Tahun, membingungkan intuisi, namun implikasinya mencakup dari daftar kelas hingga keamanan sistem digital.

Sebuah kebenaran yang menarik muncul dari matematika probabilitas: kumpulkan 23 orang, dan ada kemungkinan lebih dari setengah bahwa dua di antara mereka merayakan hari lahir pada tanggal yang sama. Anomali statistik ini, sering disebut sebagai birthday problem, sering kali mengejutkan, bertentangan dengan estimasi sehari-hari kita tentang kemungkinan.

Intuisi kita sering menyesatkan di sini, menyarankan bahwa dengan 365 hari yang mungkin, diperlukan kelompok yang jauh lebih besar untuk menemukan kecocokan. Kesalahan terletak pada cara kita membingkai pertanyaan. Kita bukan mencari seseorang yang berbagi *tanggal lahir kita*, tetapi mencari *dua orang* dalam kelompok yang berbagi *tanggal lahir yang sama*. Perbedaan ini menggeser fokus dari 23 perbandingan individu ke jumlah besar pasangan yang mungkin. Diantara 23 individu tersebut, terdapat 253 pasangan unik, masing-masing berpotensi menjadi titik kebetulan. Seiring jumlah pasangan ini meningkat secara pesat dengan setiap tambahan orang, probabilitas tanggal lahir yang sama meningkat jauh lebih cepat dari yang diharapkan.

Perhitungan dasar bergantung pada kejadian komplementer: probabilitas bahwa *tidak ada dua* orang yang berbagi tanggal lahir. Untuk orang pertama, probabilitas memiliki tanggal lahir yang unik adalah 365/365. Untuk orang kedua, itu adalah 364/365, karena mereka harus menghindari tanggal lahir orang pertama. Orang ketiga harus menghindari dua tanggal (363/365), dan seterusnya. Mengalikan pecahan-pecahan ini yang menurun menghasilkan probabilitas *tidak ada tanggal lahir yang sama*. Mengurangkan ini dari satu mengungkap probabilitas setidaknya satu tanggal lahir yang sama. Pada 23 orang, ini melewati ambang 50%, mencapai sekitar 50,7%. Saat kelompok mencapai 70 orang, probabilitas tanggal lahir yang sama melebihi 99,9%, hampir pasti.

Di Luar Ruang Kelas: Serangan Kriptografi

Implikasi fenomena probabilitas ini melampaui trik pesta dan demografi kelas. Dalam ilmu komputer, khususnya cryptography, birthday problem menjadi dasar kerentanan penting yang dikenal sebagai birthday attack. Serangan ini memanfaatkan prinsip matematika yang sama untuk menemukan tabrakan dalam keluaran hash function. Fungsi hash mengambil masukan (seperti pesan atau file) dan menghasilkan string karakter ukuran tetap, "hash"-nya, yang berfungsi sebagai sidik jari digital unik. Idealnya, masukan yang berbeda seharusnya menghasilkan hash yang berbeda.

Namun, seperti dengan tanggal lahir, jika cukup banyak masukan di-hash, probabilitas dua masukan berbeda menghasilkan nilai hash yang sama—tabrakan—meningkat secara dramatis karena jumlah besar pasangan yang mungkin. Seorang penyerang dapat menghasilkan banyak variasi dari pesan sah dan banyak variasi dari pesan jahat, berharap bahwa pasangan (satu sah, satu jahat) menghasilkan nilai hash yang sama. Paradoks ulang tahun memastikan bahwa menemukan tabrakan seperti itu membutuhkan upaya jauh lebih sedikit dari yang secara intuitif diharapkan, sering kali akar kuadrat dari total keluaran hash yang mungkin, bukan setengahnya. Ini berarti fungsi hash 128-bit, yang secara teoritis memiliki 2^128 keluaran mungkin, dapat rentan terhadap serangan ulang tahun dengan sekitar 2^64 operasi, membuatnya layak secara komputasi untuk beberapa algoritma.

Apa yang Masih Kita Tidak Tahu

Meskipun prinsip matematis inti paradoks ulang tahun sudah dipahami dengan baik, aplikasi dunia nyatanya masih menyajikan nuansa. Kebanyakan perhitungan mengasumsikan distribusi tanggal lahir yang seragam sepanjang tahun, mengabaikan faktor seperti variasi laju kelahiran musiman, tahun kabisat, atau sedikitnya peningkatan frekuensi beberapa tanggal lahir akibat intervensi medis. Meskipun faktor-faktor ini dapat sedikit menggeser probabilitas, mereka jarang menghilangkan prinsip dasar paradoks, sering kali menghasilkan *probabilitas tabrakan yang lebih awal*.

Selain itu, memperluas paradoks ke tabrakan orde lebih tinggi—menemukan tiga, empat, atau lebih orang yang berbagi tanggal lahir—secara cepat meningkatkan ukuran kelompok yang diperlukan. Sementara probabilitas dua orang berbagi tanggal lahir melewati 50% pada 23 individu, menemukan tiga orang dengan tanggal lahir yang sama memerlukan kelompok sebesar 88, dan empat orang memerlukan 187. Lompatan intuitif antara probabilitas ini tetap menjadi tantangan kognitif, menyoroti sifat paradoks yang tetap kontra-intuitif.

Sebuah konsep yang sering dikacaukan dengan masalah ulang tahun adalah pigeonhole principle. Meskipun terkait dengan distribusi item ke dalam wadah, prinsip burung gereja menyatakan bahwa jika `n` item ditempatkan ke dalam `m` wadah, dengan `n > m`, maka setidaknya satu wadah harus berisi lebih dari satu item. Ini menjamin tabrakan ketika jumlah orang melebihi jumlah hari (misalnya, 366 orang menjamin tanggal lahir yang sama), tetapi tidak mengkuantifikasi probabilitas tabrakan *sebelum* titik tersebut, yang merupakan fokus paradoks ulang tahun.

Paradoks Ulang Tahun, meskipun tampaknya hanya keanehan matematika sederhana, secara halus mengubah pemahaman kita tentang peluang, menunjukkan bagaimana jaringan tersembunyi dari koneksi potensial dengan cepat menaikkan yang tidak mungkin menjadi pasti.

في تجمع يتكون من 23 فردًا فقط، تزيد فرص أن يشارك اثنان منهم نفس تاريخ الميلاد عن 50%. هذه الظاهرة الإحصائية، المعروفة باسم [[الпарадокс]] عيد الميلاد، تتعارض مع الحدس، لكن تأثيراتها تمتد من قوائم الفصول الدراسية إلى أمن الأنظمة الرقمية.

يظهر حقيقة غريبة من رياضيات الاحتمال: اجتمع 23 شخصًا معًا، وهناك احتمال أكبر من 50% أن يكون هناك شخصان من بينهم يحتفلان بعيد ميلادهما في نفس اليوم. هذه الاستثناء الإحصائي، والذي يُعرف غالبًا باسم birthday problem، يثير غالبًا الدهشة، ويتعارض مع تصوراتنا اليومية لاحتمالات حدوث الأشياء.

غالبًا ما تخدعنا حدسنا هنا، ونفترض أن مع وجود 365 يومًا محتملة، فسيحتاج الأمر إلى مجموعة أكبر بكثير للعثور على تطابق. الخطأ يكمن في كيفية صياغة السؤال. فنحن لا نبحث عن شخص يشارك *نَحن* عيد ميلادنا، بل نبحث عن *أي* شخصين داخل المجموعة يشاركان *أي* عيد ميلاد مشترك. والاختلاف هذا يغير التركيز من 23 مقارنة فردية إلى عدد كبير من التوائم المحتملة. بين هؤلاء 23 الفرد، هناك 253 زوجًا فريدًا، كل منها نقطة محتملة للصدفة. مع زيادة عدد هذه التوائم بسرعة مع كل شخص إضافي، يرتفع احتمال وجود تطابق في التاريخ بشكل أسرع مما يتخيله المرء.

تُعتمد الحسابات الأساسية على الحدث المكمل: احتمال أن *لا يشارك* أي شخصين عيد ميلاد. بالنسبة للشخص الأول، احتمال أن يكون لديه عيد ميلاد فريد هو 365/365. بالنسبة للشخص الثاني، هو 364/365، حيث يجب عليه تجنب يوم عيد ميلاد الشخص الأول. يجب على الشخص الثالث تجنب يومين (363/365)، وهكذا. بضرب هذه الكسور المتناقصة نحصل على احتمال *عدم وجود تطابق في عيدين ميلاد*. بطرح ذلك من واحد نحصل على احتمال وجود تطابق واحد على الأقل. عند 23 شخصًا، يعبر هذا الحد 50%، ليصل إلى حوالي 50.7%. بحلول الوقت الذي تصل فيه المجموعة إلى 70 شخصًا، يتجاوز احتمال وجود تطابق في عيد ميلاد 99.9%، وهو ما يقرب من اليقين.

خارج الفصل الدراسي: الهجمات التشفيرية

تتجاوز تداعيات هذه الظاهرة الاحتمالية الحيل والألعاب الاجتماعية والديموغرافيا في الفصل الدراسي. في علوم الحاسوب، وخاصة cryptography، يُشكل birthday problem نقطة ضعف كبيرة تُعرف باسم birthday attack. تستغل هذه الهجمة نفس المبدأ الرياضي لإيجاد تصادمات في إخراجات hash function. تأخذ دالة التجزئة إدخالًا (مثل رسالة أو ملف) وتنتج سلسلة ثابتة من الأحرف، والتي تُعرف بـ "الهاش"، والتي تُعتبر بصمة رقمية فريدة. في المثالي، يجب أن تنتج إدخالات مختلفة هاشات مختلفة.

ومع ذلك، تمامًا مثل عيدين ميلاد، إذا تم تجزئة عدد كافٍ من الإدخالات، فسيزداد احتمال أن تنتج إدخالين مختلفين نفس قيمة الهاش—وهو ما يُعرف بالتصادم—بشكل كبير بسبب عدد كبير جدًا من التوائم المحتملة. يمكن للمهاجم إنشاء العديد من الإصدارات المختلفة من رسالة قانونية، وعدد كبير من الإصدارات المختلفة من رسالة خبيثة، في محاولة لعثور على زوج (واحد قانوني، وواحد خبيث) ينتج نفس القيمة. يضمن مفارقة عيد الميلاد أن العثور على مثل هذا التصادم يتطلب عددًا أقل بكثير من المحاولات مما يتخيله المرء عادة، غالبًا الجذر التربيعي لعدد الإخراجات المحتملة للهاش، وليس نصفه. هذا يعني أن دالة هاش بحجم 128 بت، والتي تفترض أن لها 2^128 إخراجًا محتملًا، يمكن أن تكون عرضة لهجوم عيد الميلاد باستخدام حوالي 2^64 عملية، مما يجعل الأمر عمليًا من الناحية الحاسوبية لبعض الخوارزميات.

ما لا نزال لا نعرفه

بينما يُفهم مبدأ رياضي مفارقة عيد الميلاد جيدًا، فإن تطبيقه في العالم الحقيقي لا يزال يحمل بعض التعقيدات. تفترض معظم الحسابات توزيعًا موحدًا لعيد الميلاد على مدار السنة، وتتجاهل عوامل مثل تغيرات معدلات الولادة الموسمية، أو السنوات الكبيسة، أو ارتفاع قليلاً في بعض تواريخ الولادة بسبب التدخلات الطبية. بينما يمكن لهذه العوامل أن تغير الاحتمالات بشكل طفيف، إلا أنها نادراً ما تلغي المبدأ الأساسي للمفارقة، وغالبًا ما تؤدي إلى *حدوث تصادم أبكر*.

بالإضافة إلى ذلك، فإن توسيع المفارقة إلى تصادمات من الدرجة الأعلى—إيجاد ثلاثة أو أربعة أشخاص أو أكثر يشاركون نفس عيد الميلاد—يزيد بسرعة من حجم المجموعة المطلوبة. بينما يعبر احتمال وجود شخصين يحتفلان بعيد ميلادهما في نفس اليوم 50% عند 23 فردًا، فإن العثور على ثلاثة أشخاص يحتفلون بنفس عيد الميلاد يتطلب مجموعة من 88 شخصًا، والأربعة يتطلب 187 شخصًا. يظل القفز الحدسي بين هذه الاحتمالات تحديًا ذهنيًا، مما يبرز الطبيعة المضادة للحدس المستمرة للمفارقة.

مبدأ غالبًا ما يُخلط مع مشكلة عيد الميلاد هو pigeonhole principle. على الرغم من ارتباطه بتوزيع العناصر في الحاويات، إلا أن مبدأ الحظائر ينص على أنه إذا وضعت `n` عنصرًا في `m` حاوية، مع `n > m`، فإن على الأقل حاوية واحدة يجب أن تحتوي على أكثر من عنصر واحد. وهذا يضمن حدوث تصادم عندما يتجاوز عدد الأشخاص عدد الأيام (مثل 366 شخصًا يضمنون تصادمًا في عيد الميلاد)، ولكن لا يحدد احتمال حدوث التصادم *قبل* ذلك، وهو ما تتناوله مفارقة عيد الميلاد.

رغم أن مفارقة عيد الميلاد تبدو في البداية مجرد فضول رياضي بسيط، إلا أنها تعيد تشكيل فهمنا للصدفة بشكل خفي، وتدل على كيف يمكن للشبكة الخفية من الاتصالات المحتملة أن ترفع من غير المرجح إلى المؤكد بسرعة.

В группе из 23 человек вероятность того, что у двоих совпадают дни рождения, превышает 50%. Этот статистический парадокс, известный как [[Birthday Paradox]], противоречит интуитивным ожиданиям, но его последствия охватывают от списков учеников в классах до безопасности цифровых систем.

Из математики вероятности вытекает любопытная истина: собрав 23 человека, вероятность того, что у двух из них дни рождения совпадут, превышает 50%. Эта статистическая аномалия, часто называемая birthday problem, часто удивляет, противореча нашим повседневным оценкам вероятности.

Наша интуиция здесь часто нас подводит, подсказывая, что для нахождения совпадения потребуется гораздо большая группа, учитывая 365 возможных дней. Ошибка кроется в том, как мы формулируем вопрос. Мы не ищем человека, разделяющего *наше* день рождения, а ищем *любую* пару людей в группе, разделяющих *любой* общий день рождения. Эта разница смещает фокус с 23 отдельных сравнений на множество возможных пар. Среди 23 человек существует 253 уникальные пары, каждая из которых — потенциальная точка совпадения. По мере того как количество таких пар быстро растёт с каждым новым человеком, вероятность совпадения даты резко увеличивается.

Подсчёт основывается на противоположном событии: вероятности того, что *ни у кого* из людей не будет совпадающего дня рождения. Для первого человека вероятность иметь уникальный день рождения составляет 365/365. Для второго — 364/365, так как он должен избежать дня рождения первого человека. Третий должен избегать двух дней (363/365) и так далее. Перемножение этих уменьшающихся дробей даёт вероятность *отсутствия совпадающих дней рождения*. Вычитание этого значения из единицы показывает вероятность наличия хотя бы одного совпадения. При 23 людях это значение превышает 50%-ный порог, достигая приблизительно 50,7%. К моменту, когда группа достигает 70 человек, вероятность совпадения дня рождения превышает 99,9%, становясь почти достоверной.

За пределами классной комнаты: криптографические атаки

Влияние этой вероятностной закономерности выходит за рамки развлекательных упражнений и демографии в классе. В информатике, особенно в cryptography, birthday problem лежит в основе важной уязвимости, известной как birthday attack. Эта атака использует ту же математическую принципиальность, чтобы найти коллизии в hash function выходах. Функция хэширования принимает входные данные (например, сообщение или файл) и производит строку фиксированного размера, её "хэш", который служит уникальным цифровым отпечатком. Идеально, если разные входные данные производят разные хэши.

Однако, как и с днями рождения, при хэшировании достаточного количества входных данных вероятность того, что два разных входа дадут одинаковый хэш — коллизию, — резко возрастает из-за огромного количества возможных пар. Атакующий может создать множество вариантов легитимного сообщения и множество вариантов вредоносного сообщения, надеясь, что пара (одно легитимное, одно вредоносное) даст одинаковое значение хэша. Парадокс дня рождения гарантирует, что нахождение такой коллизии требует гораздо меньше попыток, чем можно интуитивно ожидать, часто квадратный корень от общего количества возможных выходов хэша, а не половина. Это означает, что 128-битная функция хэширования, теоретически имеющая 2^128 возможных выходов, может быть уязвима для атаки дня рождения с приблизительно 2^64 операциями, что делает её вычислительно возможной для определённых алгоритмов.

Что мы всё ещё не знаем

Хотя основной математический принцип парадокса дня рождения хорошо понятен, его применение в реальном мире всё ещё имеет свои нюансы. Большинство расчётов предполагает равномерное распределение дней рождения в течение года, игнорируя факторы, такие как сезонные вариации рождаемости, високосные годы или немного большее распространение некоторых дат рождения из-за медицинских вмешательств. Хотя эти факторы могут незначительно сдвинуть вероятности, они редко опровергают основную предпосылку парадокса, часто приводя к *более ранней* вероятности коллизии.

Кроме того, распространение парадокса на коллизии более высокого порядка — нахождение трёх, четырёх или более людей, разделяющих день рождения — быстро увеличивает необходимый размер группы. В то время как вероятность того, что у двух людей будет одинаковый день рождения, превышает 50% при 23 людях, нахождение трёх человек с одинаковым днём рождения требует группы из 88 человек, а четыре человека — 187. Интуитивный скачок между этими вероятностями остаётся когнитивной задачей, подчёркивающей постоянную контринтуитивность парадокса.

Понятие, часто путающееся с проблемой дня рождения, — это pigeonhole principle. В то время как он связан с распределением предметов в контейнеры, принцип Дирихле утверждает, что если `n` предметов размещены в `m` контейнерах, где `n > m`, то по меньшей мере один контейнер должен содержать более одного предмета. Это гарантирует коллизию, когда количество людей превышает количество дней (например, 366 человек гарантируют совпадение дня рождения), но он не квантифицирует вероятность коллизий *до* этой точки, что и рассматривает парадокс дня рождения.

Парадокс дня рождения, хотя и кажется простой математической любопытственностью, тонко меняет наше понимание случая, демонстрируя, как скрытая сеть потенциальных связей может быстро повысить маловероятное до неизбежного.

23명만 모이면 이들 중 생일이 같은 두 사람이 있을 확률이 50%를 넘는다. 이 통계적 역설인 [[생일 역설]]은 직관을 뒤엎으며, 수업 명단에서 디지털 시스템의 보안에 이르기까지 다양한 분야에 영향을 미친다.

확률의 수학에서 흥미로운 진실이 드러난다. 23명의 사람을 모아놓으면, 그 중 두 사람이 같은 날 생일을 맞을 확률이 50% 이상이라는 것이다. 이 통계적 이상현상은 종종 birthday problem이라고 불리며, 보통 사람의 직관과는 달리 놀라움을 주는 경우가 많다.

우리의 직관은 이 문제를 잘못 파악하는 경향이 있다. 365일 중 하루를 고르는 경우가 많기 때문에, 같은 생일을 가진 사람이 나올 확률을 높이려면 훨씬 더 많은 인원이 필요하다고 생각한다. 하지만 실상은 질문을 어떻게 구성하느냐에 달려 있다. 여기서 우리가 찾는 것은 *나의* 생일과 같은 날을 가진 사람, 아니라 *어떤 두 사람*이 *어떤 날*을 공유하고 있는지를 찾는 것이다. 이 차이는 23명의 개인 비교에서 수많은 가능한 짝의 비교로 초점을 전환시킨다. 23명의 사람 사이에는 253개의 고유한 짝이 존재하며, 각각은 우연의 소용돌이가 될 수 있다. 이 짝의 수는 인원이 늘어날수록 급격히 증가하기 때문에, 같은 생일을 가질 확률은 예상보다 훨씬 빠르게 상승한다.

기본적인 계산은 보완적인 사건, 즉 *두 사람이 생일을 공유하지 않는* 확률에 기반한다. 첫 번째 사람의 경우, 생일이 고유할 확률은 365/365이다. 두 번째 사람은 첫 번째 사람의 생일을 피해야 하므로 364/365가 된다. 세 번째 사람은 두 개의 생일을 피해야 하므로 363/365가 되고, 이와 같은 방식으로 계속된다. 이러한 감소하는 분수를 곱하면 *공유되지 않는 생일*의 확률이 나온다. 이를 1에서 빼면, 최소한 한 쌍의 공유 생일이 존재할 확률이 된다. 23명이 되면 이 확률은 50% 기준선을 넘어서, 약 50.7%에 달한다. 그룹이 70명에 이르면, 공유 생일이 존재할 확률은 99.9%를 넘어서 거의 확실한 일이 된다.

교실을 넘어: 암호 공격

이 확률적 현상의 의미는 파티의 놀라움이나 교실의 인구 통계학을 넘어서는다. 특히 컴퓨터 과학 분야에서, cryptography의 핵심 개념인 birthday problembirthday attack이라는 중대한 취약점의 기반을 이룬다. 이 공격은 동일한 수학적 원리를 이용해 hash function의 출력에 충돌을 찾는다. 해시 함수는 입력(예: 메시지나 파일)을 받아 고정 크기의 문자열인 해시를 생성한다. 이 해시는 유일한 디지털 지문으로 사용된다. 이상적으로는 다른 입력이 다른 해시를 만들어야 한다.

그러나 생일 문제와 마찬가지로, 해시되는 입력이 충분히 많아지면, 가능한 짝의 수량이 많기 때문에 서로 다른 두 입력이 동일한 해시 값을 갖는 충돌이 발생할 확률이 급격히 증가한다. 공격자는 정상 메시지의 다양한 변형과 악의적인 메시지의 다양한 변형을 생성해, 정상 메시지 하나와 악의적인 메시지 하나가 동일한 해시 값을 갖는 짝이 나올 수 있도록 시도한다. 생일 역설 덕분에 이러한 충돌을 찾는 데에는 직관적으로 예상하는 것보다 훨씬 적은 시도가 필요하다. 일반적으로는 전체 가능한 해시 출력의 제곱근 만큼의 시도가 필요하다는 것이다. 이는 이론상 2^128개의 출력을 가진 128비트 해시 함수가 약 2^64개의 연산만으로 생일 공격에 취약할 수 있음을 의미한다. 이는 특정 알고리즘에 대해 계산적으로 실행 가능한 수준이다.

여전히 알 수 없는 것들

생일 역설의 핵심 수학적 원리는 잘 알려져 있지만, 실제 세계에서의 적용은 여전히 미묘한 차이를 보인다. 대부분의 계산은 연중 생일이 균일하게 분포한다고 가정하며, 계절별 출산률의 변화, 윤년, 혹은 의학적 개입으로 인해 특정 날짜가 더 많이 나타나는 현상은 무시한다. 이러한 요소들이 확률을 약간씩 바꾸지만, 대체로 역설의 기본 전제를 무효화하지는 않는다. 오히려 충돌이 일어날 확률이 더 빨리 도달할 수 있다.

또한, 이 역설을 고차원 충돌로 확장하는 것도 고려할 수 있다. 즉, 세 명, 네 명, 혹은 그 이상의 사람이 동일한 생일을 갖는 경우를 찾는 것이다. 두 명이 같은 생일을 갖는 확률이 23명에서 50%를 넘는 반면, 세 명이 같은 생일을 갖는 경우는 88명, 네 명이 같은 생일을 갖는 경우는 187명이 필요하다. 이러한 확률 간의 직관적 차이는 여전히 인지적 도전으로 남아 있으며, 역설의 지속적인 반직관적 성질을 드러낸다.

생일 문제와 혼동되기 쉬운 개념은 pigeonhole principle이다. 항목을 컨테이너에 분포시키는 문제와 관련된 이 원리는, `n`개의 항목이 `m`개의 컨테이너에 들어가며 `n > m`이라면, 적어도 하나의 컨테이너에는 두 개 이상의 항목이 들어가야 한다고 말한다. 이는 인원 수가 날짜 수를 초과할 때 충돌이 반드시 발생함을 보장하지만, 생일 역설이 다루는 것은 이 기준에 도달하기 *전*의 충돌 확률을 정량화하는 것이다.

생일 역설은 단순한 수학적 호기심처럼 보일 수 있지만, 잠재적인 연결망이 어떻게 불가능한 것을 불가피하게 만들 수 있는지를 보여주며, 우연에 대한 우리의 이해를 약간씩 바꾸어 놓는다.

Bei einer Versammlung von nur 23 Personen liegt die Wahrscheinlichkeit, dass zwei von ihnen am gleichen Tag Geburtstag haben, bereits über 50 %. Dieses statistische Phänomen, bekannt als Geburtstagsparadoxon, entbehrt der Intuition, doch seine Auswirkungen reichen von Schulklasse-Listen bis hin zur Sicherheit digitaler Systeme.

Ein faszinierendes Phänomen tritt aus der Mathematik der Wahrscheinlichkeit hervor: Versammeln sich 23 Personen, so beträgt die Wahrscheinlichkeit, dass zwei von ihnen am gleichen Tag Geburtstag feiern, mehr als 50 Prozent. Diese statistische Besonderheit, oftmals als birthday problem bezeichnet, überrascht häufig und widerspricht unseren alltäglichen Schätzungen von Wahrscheinlichkeit.

Unsere Intuition täuscht uns hier oft, indem sie suggeriert, dass bei 365 möglichen Tagen eine viel größere Gruppe erforderlich wäre, um eine Übereinstimmung zu finden. Der Fehler liegt in der Formulierung der Frage. Wir suchen nicht nach jemandem, der *uns* das Geburtsdatum teilt, sondern nach *zwei Personen* innerhalb der Gruppe, die *irgendwelches* gemeinsame Geburtsdatum haben. Diese Unterscheidung verschiebt den Fokus von 23 individuellen Vergleichen auf die Vielzahl möglicher Paarungen. Unter diesen 23 Personen gibt es 253 einzigartige Paare, jedes ein mögliches Zufallsereignis. Da sich die Anzahl dieser Paarungen mit jedem zusätzlichen Menschen rasch erhöht, steigt die Wahrscheinlichkeit eines gemeinsamen Datums viel schneller an, als erwartet.

Die zugrunde liegende Berechnung basiert auf dem komplementären Ereignis: der Wahrscheinlichkeit, dass *keine zwei* Personen ein gemeinsames Geburtsdatum haben. Für die erste Person beträgt die Wahrscheinlichkeit, ein einzigartiges Geburtsdatum zu haben, 365/365. Für die zweite Person ist es 364/365, da sie den Tag der ersten Person vermeiden muss. Die dritte Person muss zwei Tage vermeiden (363/365), und so weiter. Das Multiplizieren dieser abnehmenden Brüche ergibt die Wahrscheinlichkeit von *keinem gemeinsamen Geburtsdatum*. Subtrahiert man dies von eins, erhält man die Wahrscheinlichkeit, dass mindestens ein gemeinsames Geburtsdatum vorliegt. Bei 23 Personen überschreitet diese den 50-Prozent-Schwellenwert und erreicht etwa 50,7 Prozent. Wenn eine Gruppe 70 Personen umfasst, liegt die Wahrscheinlichkeit eines gemeinsamen Geburtsdatums bei über 99,9 Prozent, beinahe eine Sicherheit.

Jenseits des Unterrichts: Kryptografische Angriffe

Die Folgen dieses probabilistischen Phänomens erstrecken sich weit über Partys und Klassenzimmer hinaus. In der Informatik, insbesondere cryptography, untermauert die birthday problem eine bedeutende Schwachstelle, die als birthday attack bezeichnet wird. Dieser Angriff nutzt das gleiche mathematische Prinzip, um Kollisionen in den hash function-Ausgängen zu finden. Eine Hash-Funktion nimmt eine Eingabe (z. B. eine Nachricht oder eine Datei) und erzeugt eine Zeichenkette fester Länge, den sogenannten „Hash“, der als digitale Fingerabdruck dient. Idealerweise sollten unterschiedliche Eingaben unterschiedliche Hashes erzeugen.

Doch genauso wie bei Geburtstagen steigt die Wahrscheinlichkeit, dass zwei verschiedene Eingaben den gleichen Hashwert – eine Kollision – erzeugen, erheblich an, sobald genügend Eingaben gehasht werden, aufgrund der reinen Anzahl möglicher Paarungen. Ein Angreifer kann zahlreiche Varianten einer legitimen Nachricht und zahlreiche Varianten einer bösartigen Nachricht generieren und hofft, dass ein Paar (ein legales und ein bösartiges) den gleichen Hashwert erzeugt. Das Geburtstagsparadoxon sorgt dafür, dass das Auffinden einer solchen Kollision weit weniger Versuche erfordert, als man intuitiv erwarten würde, oft nur die Quadratwurzel der Gesamtanzahl möglicher Hash-Ausgaben, nicht die Hälfte. Das bedeutet, dass eine 128-Bit-Hash-Funktion, die theoretisch 2^128 mögliche Ausgaben hat, einem Geburtstagsangriff mit etwa 2^64 Operationen unterliegen kann, was für bestimmte Algorithmen rechentechnisch machbar ist.

Was wir immer noch nicht wissen

Obwohl das grundlegende mathematische Prinzip des Geburtstagsparadoxons gut verstanden ist, wirft seine reale Anwendung immer noch Nuancen auf. Die meisten Berechnungen setzen eine gleichmäßige Verteilung der Geburtstage im Jahr voraus, ignorieren dabei Faktoren wie saisonale Schwankungen der Geburtenrate, Schaltjahre oder die leicht höhere Häufigkeit einiger Geburtsdaten aufgrund medizinischer Eingriffe. Obwohl diese Faktoren die Wahrscheinlichkeiten subtil beeinflussen können, widerlegen sie selten das grundlegende Prinzip des Paradoxons, führen jedoch oft zu einer *früheren* Wahrscheinlichkeit einer Kollision.

Außerdem steigt die erforderliche Gruppengröße rasch an, wenn man das Paradoxon auf höhere Kollisionen ausweitet – also auf drei, vier oder mehr Personen mit dem gleichen Geburtstag. Während die Wahrscheinlichkeit, dass zwei Personen ein gemeinsames Geburtsdatum haben, bei 23 Personen über 50 Prozent liegt, benötigt man für drei Personen mit dem gleichen Geburtstag eine Gruppe von 88 und für vier Personen eine Gruppe von 187. Der intuitive Sprung zwischen diesen Wahrscheinlichkeiten bleibt eine kognitive Herausforderung und betont die anhaltend widersprüchliche Natur des Paradoxons.

Ein Konzept, das oft mit dem Geburtstagsproblem verwechselt wird, ist das pigeonhole principle. Obwohl es mit der Verteilung von Objekten in Behälter zusammenhängt, besagt das Schubfachprinzip, dass wenn `n` Objekte in `m` Behälter gelegt werden, wobei `n > m`, mindestens ein Behälter mehr als ein Objekt enthalten muss. Dies garantiert eine Kollision, sobald die Anzahl der Personen die Anzahl der Tage überschreitet (z. B. 366 Personen garantieren einen gemeinsamen Geburtstag), quantifiziert aber nicht die Wahrscheinlichkeit von Kollisionen *vor* diesem Punkt, was das Geburtstagsparadoxon adressiert.

Das Geburtstagsparadoxon, obwohl auf den ersten Blick eine einfache mathematische Kuriosität, verändert subtil unser Verständnis des Zufalls und zeigt, wie das verborgene Netz potenzieller Verbindungen das Unwahrscheinliche rasch zum Unvermeidlichen macht.

23 व्यक्तियों के समूह में, उनमें से दो के एक ही जन्मदिन रखने की संभावना 50% से अधिक हो जाती है। यह सांख्यिकीय अजबखाबर, जिसे जन्मदिन पराक्षिति [[Birthday Paradox]] कहा जाता है, सामान्य समझ को भ्रमित करता है, लेकिन इसके अर्थव्यवस्था के छात्रों की सूचियों से लेकर डिजिटल प्रणालियों की सुरक्षा तक के क्षेत्र में फैले हुए हैं।

संभाव्यता के गणित से एक अजीब सच्चाई उजागर होती है: 23 लोगों को एक साथ लाएं, और उनमें से दो के जन्म तिथि के समान होने की संभावना 50 प्रतिशत से अधिक होती है। इस सांख्यिकीय असामान्यता को अक्सर birthday problem कहा जाता है, जो अक्सर हमारे दैनिक संभावना के अनुमानों के खिलाफ चलता है और आश्चर्यजनक होता है।

हमारी अंतर्ज्ञान अक्सर यहां हमें गलती कराती है, जो बताती है कि 365 संभावित दिनों के साथ, एक मिलान खोजने के लिए बहुत बड़ा समूह चाहिए। गलती हमारे प्रश्न के रूप के अंदर है। हम अपने जन्मदिन के साथ किसी के साझा करने की तलाश नहीं कर रहे हैं, बल्कि समूह में किसी भी दो लोगों के किसी भी सामान्य जन्मदिन के साझा करने की तलाश कर रहे हैं। यह अंतर 23 व्यक्तिगत तुलनाओं के ध्यान को बदलकर संभावित जोड़ियों की बहुतायत पर ले आता है। उन 23 व्यक्तियों में, 253 अद्वितीय जोड़ियां होती हैं, प्रत्येक एक संयोग का संभावित बिंदु है। इन जोड़ियों की संख्या प्रत्येक अतिरिक्त व्यक्ति के साथ तेजी से बढ़ती है, जिससे साझा तिथि की संभावना अपेक्षा से बहुत तेजी से बढ़ जाती है।

मूल गणना एक विपरीत घटना पर निर्भर करती है: कोई भी दो लोग जन्मदिन साझा नहीं करते हैं। पहले व्यक्ति के लिए एक अद्वितीय जन्मदिन होने की संभावना 365/365 है। दूसरे के लिए, यह 364/365 है, क्योंकि उन्हें पहले व्यक्ति के दिन को बचाना होगा। तीसरे को दो दिन बचाने होंगे (363/365), आदि। इन घटती हुई अंशों को गुणा करने से *कोई साझा जन्मदिन नहीं* होने की संभावना मिलती है। एक से घटाने पर कम से कम एक साझा जन्मदिन की संभावना खुल जाती है। 23 लोगों के साथ, यह 50% के थ्रेशोल्ड को पार कर जाती है, लगभग 50.7% तक पहुंच जाती है। 70 लोगों के समूह तक पहुंचने पर, एक साझा जन्मदिन की संभावना 99.9% से अधिक हो जाती है, लगभग निश्चितता के करीब।

कक्षा से परे: शिफ्रोग्राफिक हमले

इस संभाव्यता घटना के निहितार्थ पार्टी ट्रिक्स और कक्षा जनसंख्या से आगे फैले हुए हैं। कंप्यूटर विज्ञान में, विशेष रूप से cryptography, birthday problem एक महत्वपूर्ण असुरक्षा के रूप में जाना जाने वाला birthday attack के आधार पर आधारित है। यह हमला समान गणितीय सिद्धांत का उपयोग करके hash function आउटपुट में संघर्ष खोजता है। एक हैश फंक्शन एक इनपुट (जैसे कि एक संदेश या एक फ़ाइल) लेता है और एक निश्चित आकार की वर्णों की एक स्ट्रिंग उत्पन्न करता है, जिसे इसका "हैश" कहा जाता है, जो एक अद्वितीय डिजिटल उंगली के निशान के रूप में कार्य करता है। आदर्श रूप से, अलग-अलग इनपुट अलग-अलग हैश उत्पन्न करने चाहिए।

हालांकि, जन्मदिन की तरह, यदि पर्याप्त इनपुट हैश होते हैं, तो एक संघर्ष की संभावना जिसमें दो अलग-अलग इनपुट समान हैश मान उत्पन्न करते हैं, संभावित जोड़ियों की बहुतायत के कारण तेजी से बढ़ जाती है। एक हमलावर एक वैध संदेश के बहुत सारे परिवर्तन उत्पन्न कर सकता है और एक खतरनाक संदेश के बहुत सारे परिवर्तन उत्पन्न कर सकता है, उम्मीद करता है कि एक जोड़ी (एक वैध, एक खतरनाक) समान मान के हैश होगी। जन्मदिन के पैराडॉक्स के कारण ऐसे एक संघर्ष को खोजने में आमतौर पर अपेक्षा से बहुत कम प्रयास लगते हैं, अक्सर कुल संभावित हैश आउटपुट के वर्गमूल के बराबर, बजाय आधे के। इसका मतलब यह है कि 128-बिट हैश फंक्शन, जिसके सैद्धांतिक रूप से 2^128 संभावित आउटपुट हैं, 2^64 ऑपरेशन के साथ जन्मदिन हमले के प्रति संवेदनशील हो सकता है, जो कुछ एल्गोरिदमों के लिए कंप्यूटेशनल रूप से संभव बनाता है।

हम अभी तक नहीं जानते

जबकि जन्मदिन पैराडॉक्स का मूल गणितीय सिद्धांत अच्छी तरह से समझा गया है, इसके वास्तविक अनुप्रयोग में अभी भी नुक्सान हैं। अधिकांश गणनाएं पूरे वर्ष में जन्मदिनों के समान वितरण के अनुमान करती हैं, मौसमी जन्म दर के विविधता, अधिवर्ष या चिकित्सा हस्तक्षेप के कारण कुछ जन्म तिथियों के थोड़ा अधिक प्रचलित होने को नजरअंदाज कर देती हैं। यद्यपि ये कारक संभावनाओं में धीमे-धीमे बदलाव कर सकते हैं, लेकिन अक्सर यह पैराडॉक्स के मूल सिद्धांत को अमान्य नहीं करते, अक्सर एक संघर्ष की संभावना को अधिक पहले ले आते हैं।

इसके अलावा, पैराडॉक्स को उच्च-क्रम के संघर्षों तक बढ़ाना—एक ही जन्मदिन वाले तीन, चार या अधिक लोगों की खोज करना—आवश्यक समूह के आकार को तेजी से बढ़ा देता है। जबकि दो लोगों के एक ही जन्मदिन की संभावना 23 व्यक्तियों में 50% के थ्रेशोल्ड को पार कर जाती है, तीन लोगों के एक ही जन्मदिन के लिए 88 लोगों की आवश्यकता होती है, और चार लोगों के लिए 187 लोगों की आवश्यकता होती है। इन संभावनाओं के बीच के अंतर्ज्ञानी कदम एक बुद्धिमुग्ध चुनौती बने रहते हैं, जो पैराडॉक्स की लगातार अंतर्ज्ञानी नकारात्मकता को उजागर करते हैं।

जन्मदिन समस्या के साथ अक्सर गलती करे जाने वाला एक अवधारणा pigeonhole principle है। वस्तुओं के बर्तनों में वितरण के साथ संबंधित होने के कारण, कबूतरखाना सिद्धांत कहता है कि यदि `n` वस्तुएं `m` बर्तनों में डाली जाती हैं, जहां `n > m`, तो कम से कम एक बर्तन में एक से अधिक वस्तुएं होनी चाहिए। यह तब निश्चित रूप से एक संघर्ष की गारंटी देता है जब लोगों की संख्या दिनों की संख्या से अधिक हो जाती है (जैसे 366 लोग एक साझा जन्मदिन की गारंटी देते हैं), लेकिन यह उस बिंदु से पहले संघर्ष की संभावना की मात्रा नहीं बताता, जिसे जन्मदिन पैराडॉक्स नियंत्रित करता है।

जन्मदिन पैराडॉक्स, जबकि स्पष्ट रूप से एक सरल गणितीय रोचकता लगता है, अविश्वसनीय को अपरिहार्य तक पहुंचाने वाले संभावित जोड़ों के छिपे नेटवर्क के माध्यम से हमारी भाग्य की समझ को धीरे-धीरे बदल देता है।

Mentioned in this article

Sources

  1. Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. 1. John Wiley & Sons.
  2. Stinson, D. R. (2006). Cryptography: Theory and Practice (3rd ed.). Chapman and Hall/CRC.
  3. Mises, R. von (1939). "Über Aufteilungs- und Besetzungswahrscheinlichkeiten." Revue de la Faculté des Sciences de l'Université d'Istanbul, Nouvelle Série, 4, 145-163.
  4. Grinstead, C. M., & Snell, J. L. (1997). Introduction to Probability. American Mathematical Society.
Production storyboard

The 90-second video script behind this article.

EN script

HI script

Ek room me sirf 23 logon ke sath, do logon ke birthdays ke match hone ke chances hai.

  1. 01

    A classroom gathering of twenty-three students around a plain cake with candles removed, two students reacting with delighted surprise as they discover a shared date through conversation.

  2. 02

    Twenty-three small clay figurines stand in a loose circle on a wooden tabletop, with fine threads physically connecting pairs until the web becomes dense near the center.

  3. 03

    A cryptography lab represented physically: two sealed metal capsules from a large batch have landed in the same receiving tray, their identical shape and position surprising a technician wearing cotton gloves.

  4. 04

    A wall of small blank calendar tiles has been turned into a physical cabinet of drawers, each drawer holding a colored bead for a person in the group.

  5. 05

    A security workshop uses a physical lock-and-key experiment to suggest birthday collisions: many smooth keys slide into a large tray of identical brass tumblers, and two keys unexpectedly fit the same plain cylinder.

  6. 06

    A row of simple wooden nesting boxes sits on a table, each box made for one marble, but one box holds two marbles touching side by side while nearby boxes remain single or empty.