Math
Hasze i kubełki
Stół sortowniczy: klucze to papierowe przywieszki, wózek liczy hasz każdej i wrzuca ją do kubełka o numerze hasza, a kolizja to dwa różne klucze w jednym kubełku. Hasz to nazwana funkcja – suma kodów, wielomian o podstawie 31, FNV-1a – albo jednostajna wyrocznia stojąca za krzywą urodzin. Zmień klucz, obejrzyj jego hasz liczony znak po znaku, odwróć jeden bit i policz zmienione bity hasza; porównaj dwie funkcje na tych samych kluczach.
Co się dzieje
Dwadzieścia trzy osoby w pokoju częściej dzielą urodziny, niż nie, i ta sama arytmetyka wymiaruje tablicę haszującą. Tu klucze są prawdziwymi napisami, a hasz NAZWANĄ funkcją: sumą kodów znaków, wielomianem o podstawie 31, FNV-1a – albo jednostajną wyrocznią, która w ogóle nie ma klucza i jest modelem stojącym za krzywą. Wózek na szynie liczy hasz każdej przywieszki i wrzuca ją do kubełka o jej indeksie; przywieszka, która spada na inną, to kolizja, i oba klucze pozostają podświetlone. Arkusz liczy hasz klucza próbnego znak po znaku, odwraca jeden bit klucza i liczy zmienione bity hasza. Trzy pytania pozostają osobne: kolizje, jednostajność (χ² obciążeń względem n/m, oczekiwanie m − 1) i lawina; histogram równy na losowych słowach nie jest wyrokiem o funkcji – daj sumie liter listę anagramów, a każdy klucz wyląduje w jednym kubełku. Nic z tego nie jest siłą kryptograficzną.
Równania modułu
Równania n kluczy do m kubełków, jednostajnie P(co najmniej jedna kolizja) = 1 − iloczyn (1 − i/m), DOKŁADNIE: n = 23, m = 365 -> 0.50729723432398566; n = 50 -> 0.97037357957798842 oczekiwana liczba pustych kubełków = m·(1 − 1/m)^n DOKŁADNIE - a nie zwykłe m·e^(−n/m): przy n = m = 100 wynoszą one 36.603234127322921 i 36.787944, a różnica jest widoczna liczba kluczy do pierwszej kolizji, średnio: sqrt(pi·m/2) + 2/3 = 24.611199639354552 dla m = 365 (policzono 24.6767 w 20 000 uruchomień) maksymalne obciążenie przy n = m zachowuje się jak ln n / ln ln n - ASYMPTOTYKA, a nie wzór: zmierzony stosunek ROŚNIE, 1.32 przy m = 64, 1.49 przy 256, 1.55 przy 1024 dlatego sprawdza się go jako przedział i jako trend monotoniczny, a nigdy nie przypisuje się mu jednej liczby zmierzone wobec krzywej dokładnej (po 20 000 uruchomień): n = 10 -> 0.11605 wobec 0.11695; n = 23 -> 0.50800 wobec 0.50730; n = 70 -> 0.99920 wobec 0.99916 funkcje nazwane na kluczu k = c₁c₂…c_n (kody znaków), wszystkie modulo 2³²: suma: h = Σ c_i; podstawa 31: h ← 31·h + c_i; FNV-1a: h₀ = 2166136261, h ← (h xor c_i)·16777619 kubełek = h mod m; jednostajna wyrocznia losuje kubełek z ziarna i NUMERU klucza - nie ma żadnego klucza jednostajność: χ² = Σ (load_j − n/m)² / (n/m) po m kubełkach; jednostajny rozdział daje m − 1 ± √(2(m − 1)) efekt lawinowy: średnia po kluczach z Hamming(h(k), h(k′)) przy odwróceniu JEDNEGO bitu klucza k; funkcja idealna zmienia 16 z 32 zmierzone (ziarno 20260913, 40 losowych słów do 64 kubełków): FNV-1a 7 kolizji, χ² 46.4, efekt lawinowy 14.6; podstawa 31: 9, 52.8, 6.2; suma: 8, 52.8, 2.05; wyrocznia: 9, 59.2, brak bitów 40 anagramów jednego słowa przy sumie: 39 kolizji, jeden łańcuch długości 40, χ² = 2520 - suma nie rozróżnia kolejności liter
