• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Paradoks dnia urodzin

    Przeczytaj także...
    Celem ataku urodzinowego jest znalezienie kolizji funkcji haszującej. Jest to atak siłowy. U jego podstaw leży jednak paradoks dnia urodzin, który pozwala oczekiwać, że kolizja zostanie znaleziona znacznie szybciej niż sugerowałby to rozmiar przeciwdziedziny funkcji haszującej. Liczba potrzebnych do tego sprawdzeń rośnie bowiem proporcjonalnie do pierwiastka z liczby wszystkich możliwych wyników funkcji haszującej.Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.
    Funkcja skrótu, inaczej: funkcja mieszająca lub funkcja haszująca – jest to funkcja, która przyporządkowuje dowolnie dużej liczbie krótką, zwykle posiadającą stały rozmiar, nie specyficzną, quasi-losową wartość, tzw. skrót nieodwracalny.
    Prawdopodobieństwo, że dwie osoby w grupie n ludzi będą miały urodziny tego samego dnia w roku

    Paradoks dnia urodzinparadoks powstający przy rozwiązaniu następującego problemu: Ile minimalnie osób należy wybrać, żeby prawdopodobieństwo znalezienia wśród nich co najmniej dwóch osób obchodzących urodziny tego samego dnia było większe od 0,5.

    Rozwiązaniem problemu jest liczba 23. Ta zaskakująco mała liczba osób jest przyczyną określenia „Paradoks dnia urodzin”.

    Prawdopodobieństwo – ogólne określenie jednego z wielu pojęć służących modelowaniu doświadczenia losowego poprzez przypisanie poszczególnym zdarzeniom losowym liczb, zwykle z przedziału jednostkowego (w zastosowaniach często wyrażanych procentowo), wskazujących szanse ich zajścia. W rozumieniu potocznym wyraz „prawdopodobieństwo” odnosi się do oczekiwania względem rezultatu zdarzenia, którego wynik nie jest znany (niezależnie od tego, czy jest ono w jakimś sensie zdeterminowane, miało miejsce w przeszłości, czy dopiero się wydarzy); w ogólności należy je rozumieć jako pewną miarę nieprzewidywalności.Kolizja funkcji skrótu H to taka para różnych wiadomości m1, m2, że mają one taką samą wartość skrótu, tj. H(m1) = H(m2).

    Rozwiązanie nie uwzględnia osób urodzonych 29 lutego i rodzeństw bliźniaczych, które zaburzają statystyczną niezależność dat urodzeń oraz sezonowości rocznej urodzin. Uwzględnienie tych (stosunkowo nieistotnych dla rozwiązania) zjawisk nie zmienia znacząco podanego wyniku.

    Analiza problemu[ | edytuj kod]

    Prawdopodobieństwo tego, że po losowym przyporządkowaniu każdemu z obiektów jednej z etykietek każda etykietka będzie inna, wynosi:

    Wartość oczekiwana (wartość średnia, przeciętna, dawniej nadzieja matematyczna) – w rachunku prawdopodobieństwa wartość określająca spodziewany wynik doświadczenia losowego. Wartość oczekiwana to inaczej pierwszy moment zwykły. Estymatorem wartości oczekiwanej rozkładu cechy w populacji jest średnia arytmetyczna.29 lutego jest 60. (tylko w latach przestępnych) dniem w kalendarzu gregoriańskim. Do końca roku pozostaje 306 dni. Data ta występuje w większości lat, które są podzielne przez 4, takich jak 2008, 2012, 2016, 2020, 2024. W kalendarzu chińskim rok dzień ten występuje tylko w latach małpy, smoka i szczura. 29 lutego obchodzony jest co 4 lata.

    dodatkowo

    Stąd prawdopodobieństwo tego, że istnieją co najmniej dwa obiekty spośród mające tę samą etykietkę, wynosi:

    Jądro (zazwyczaj oznaczane k e r ( f ) {displaystyle mathrm {ker} (f)} ) - dla dowolnego przekształcenia f {displaystyle f} jest to relacja równoważności zadana przez warunek:Paradoks (gr. parádoksos – nieoczekiwany, nieprawdopodobny) – twierdzenie logiczne prowadzące do zaskakujących lub sprzecznych wniosków. Sprzeczność ta może być wynikiem błędów w sformułowaniu twierdzenia, przyjęcia błędnych założeń, a może też być sprzecznością pozorną, sprzecznością z tzw. zdrowym rozsądkiem, np. paradoks hydrostatyczny, czy paradoks bliźniąt.

    Dla ustalonego tak zdefiniowana funkcja ma własności:

    Bit (w ang. kawałek, skrót od binary digit, czyli cyfra dwójkowa) – najmniejsza ilość informacji potrzebna do określenia, który z dwóch równie prawdopodobnych stanów przyjął układ. Jednostka logiczna.
  • jest ściśle rosnąca dla
  • (są to zdarzenia pewne, patrz zasada szufladkowa Dirichleta).
  • Przedmiotem problemu jest ustalenie dla danego najmniejszej liczby dla której zachodzi:

    Oczywiście nierówności

    są równoważne.

    Rozwiązanie[ | edytuj kod]

    Aby rozwiązać problem dla wystarczy, korzystając ze wzoru (1), bezpośrednio obliczyć:

    Ponieważ jest niemalejąca, więc

    Oznacza to, że spełnia warunki postawione w zadaniu i że jest to najmniejsza liczba o tej własności

    Metoda analityczna[ | edytuj kod]

    Rozwiązanie problemu polegało między innymi na wykazaniu, że wszystkie liczby naturalne od począwszy są rozwiązaniami problemu. Ustalenie tej liczby można także przeprowadzić metodą analityczną. Wprawdzie metoda ta nie wykazuje, że jest najmniejszą liczbą o tej własności, ale pozwala podejść do problemu znacznie ogólniej.

    Funkcję można oszacować od góry następująco:

    wykorzystano tu nierówność prawdziwą dla każdej liczby rzeczywistej

    Aby ustalić, dla jakich zachodzi wystarczy ustalić, dla jakich zachodzi nierówność

    która jest równoważna nierówności kwadratowej zmiennej

    Rozwiązując ją dla otrzymuje się warunek wystarczający na

    Podstawienie daje

    skąd statystycznie wystarczą 23 osoby.

    Ogólnie dla zadanego minimalnego prawdopodobieństwa z prawej strony nierówności (2) jest

    Dlatego potrzebna liczba obiektów rośnie w przybliżeniu proporcjonalnie do pierwiastka liczby etykietek

    Zastosowanie w kryptografii[ | edytuj kod]

    Paradoks dnia urodzin ma znaczenie w kryptografii i jest podstawą działania tzw. ataku urodzinowego. Niech dana będzie funkcja skrótu która zwraca kod o bitach, czyli daje możliwych odpowiedzi (jest to moc jej przeciwdziedziny). Jej jakość można ocenić, badając jej jądro, a więc jej kolizje (kolizję tworzą każde dwie znane wiadomości i o których wiadomo, że ).

    Każdy kwantyl rozkładu liczby prób potrzebnych do znalezienia kolizji wśród kodów, spełnia zależność (5), gdzie to rząd kwantyla. Średni czas łamania funkcji skrótu (tj. znalezienia kolizji) rośnie więc w przybliżeniu proporcjonalnie do pierwiastka liczby wszystkich możliwych odpowiedzi tej funkcji.





    Reklama

    Czas generowania strony: 0.079 sek.