Dawno temu kupiłem książkę struktur danych z okazyjnej tabeli za 1,25 USD. Wyjaśnienie w nim funkcji haszującej mówi, że powinna ona ostatecznie zostać zmieniona liczbą pierwszą ze względu na „naturę matematyki”.

Czego oczekujesz od książki za 1,25 USD?

W każdym razie miałem lata na przemyślenie natury matematyki i wciąż nie mogę jej rozgryźć.

Czy rozkład liczb jest naprawdę większy, nawet jeśli istnieje duża liczba segmentów? Czy jest to opowieść starego programisty, którą wszyscy akceptują, ponieważ wszyscy inni ją akceptują?

Zwykle prosta funkcja skrótu działa poprzez pobranie „części składowych” danych wejściowych (znaków w przypadku ciągu znaków) i pomnożenie ich przez potęgę pewnej stałej i dodanie ich razem do pewnego rodzaju liczb całkowitych. Na przykład typowy (choć niezbyt dobry) skrót łańcucha może być:

(first char) + k * (second char) + k^2 * (third char) + ...

Następnie, jeśli zostanie wprowadzonych kilka ciągów znaków o tym samym pierwszym znaku, wówczas wszystkie wyniki będą tego samego modulo k, przynajmniej do momentu przepełnienia typu liczby całkowitej.

[Na przykład łańcuch hashCode Javy jest niesamowicie podobny do tego - robi odwrotną kolejność znaków, przy k = 31. Otrzymujesz więc uderzające relacje modulo 31 między ciągami, które kończą się w ten sam sposób, i uderzające relacje modulo 2 ^ 32 między ciągami, które są takie same, z wyjątkiem końca. Nie powoduje to poważnego bałaganu przy zachowaniu hashtable.]

Tablica skrótów działa, przyjmując moduł skrótu względem liczby segmentów.

W tablicy mieszającej ważne jest, aby nie wywoływać kolizji w prawdopodobnych przypadkach, ponieważ kolizje zmniejszają wydajność tablicy mieszającej.

Załóżmy teraz, że ktoś umieszcza całą masę wartości w tablicy mieszającej, która ma pewien związek między przedmiotami, na przykład wszystkie mają tę samą pierwszą postać. Jest to dość przewidywalny wzorzec użytkowania, powiedziałbym, więc nie chcemy, aby powodował zbyt wiele kolizji.

Okazuje się, że „ze względu na naturę matematyki”, jeśli stała używana w haszu i liczba segmentów są chronione prawem autorskim , to w niektórych typowych przypadkach kolizje są minimalizowane. Jeśli nie są chronione prawem autorskim, istnieją pewne dość proste relacje między danymi wejściowymi, dla których kolizje nie są minimalizowane. Wszystkie skróty wychodzą równe modulo wspólny czynnik, co oznacza, że ​​wszystkie wpadną do 1 / nth segmentów, które mają tę wartość modulo wspólny czynnik. Otrzymujesz n razy więcej kolizji, gdzie n jest wspólnym czynnikiem. Ponieważ n wynosi co najmniej 2, powiedziałbym, że niedopuszczalne jest, aby dość prosty przypadek użycia generował co najmniej dwa razy więcej kolizji niż normalnie. Jeśli jakiś użytkownik podzieli naszą dystrybucję na segmenty, chcemy, aby był to dziwny wypadek, a nie jakieś proste, przewidywalne użycie.

Teraz implementacje hashtable oczywiście nie mają kontroli nad umieszczonymi w nich elementami. Nie mogą zapobiec ich powiązaniu. Należy więc upewnić się, że stała i liczba segmentów są pierwszymi. W ten sposób nie polegasz na samym „ostatnim” elemencie, aby określić moduł kubła w odniesieniu do jakiegoś małego wspólnego czynnika. O ile wiem, nie muszą być najważniejsze, aby to osiągnąć, po prostu coprime.

Ale jeśli funkcja skrótu i ​​tablica skrótów są zapisywane niezależnie, to tablica skrótów nie wie, jak działa funkcja skrótu. Może używać stałej z małymi czynnikami. Jeśli masz szczęście, może działać zupełnie inaczej i być nieliniowy. Jeśli skrót jest wystarczająco dobry, każda liczba łyżek jest w porządku. Ale paranoiczna tablica haszująca nie może przyjąć dobrej funkcji haszującej, dlatego powinna używać największej liczby segmentów. Podobnie paranoiczna funkcja skrótu powinna używać dużej stałej podstawowej, aby zmniejszyć prawdopodobieństwo, że ktoś użyje wielu segmentów, które mają wspólny czynnik ze stałą.

W praktyce myślę, że dość normalne jest użycie siły 2 jako liczby segmentów. Jest to wygodne i pozwala uniknąć konieczności wyszukiwania lub wstępnego wyboru liczby pierwszej o odpowiedniej wielkości. Dlatego polegasz na funkcji skrótu, aby nie używać nawet mnożników, co jest ogólnie bezpiecznym założeniem. Ale nadal można od czasu do czasu zachowywać się przy złym haszowaniu na podstawie funkcji haszujących, takich jak powyższa, a liczba głównych segmentów może pomóc dalej.

Wprowadzenie zasady, że „wszystko musi być liczbą pierwszą” jest, o ile wiem, wystarczającym, ale nie koniecznym warunkiem dobrego podziału na tablice skrótów. Pozwala to wszystkim współpracować bez konieczności zakładania, że ​​inni przestrzegali tej samej zasady.

[Edycja: istnieje inny, bardziej wyspecjalizowany powód, aby korzystać z największej liczby segmentów, np. W przypadku kolizji z sondowaniem liniowym. Następnie obliczasz krok na podstawie kodu skrótu, a jeśli ten krok okaże się czynnikiem liczenia segmentu, możesz wykonać tylko (bucket_count / stride) sondy, zanim wrócisz do miejsca, w którym zacząłeś. Przypadek, którego najbardziej chcesz uniknąć, to stride = 0, oczywiście, które musi być w specjalnej obudowie, ale aby uniknąć także specjalnej obudowy bucket_count / stride równej małej liczbie całkowitej, możesz po prostu ustawić wartość bucket_count jako pierwszą i nie dbając o to, co krok jest pod warunkiem, że nie jest to 0.]

Pierwszą rzeczą, którą robisz przy wstawianiu / wycofywaniu z tablicy skrótów, jest obliczenie kodu skrótu dla danego klucza, a następnie znalezienie poprawnego segmentu poprzez przycięcie kodu skrótu do rozmiaru tablicy skrótów poprzez wykonanie hashCode% table_length. Oto 2 „stwierdzenia”, które najprawdopodobniej gdzieś przeczytałeś

1. Jeśli użyjesz potęgi 2 dla table_length, znalezienie (hashCode (klucz)% 2 ^ n) jest tak proste i szybkie jak (hashCode (klucz) i (2 ^ n -1)). Ale jeśli twoja funkcja obliczania kodu skrótu dla danego klucza nie jest dobra, na pewno cierpisz na grupowanie wielu kluczy w kilku zbiorach skrótów.
2. Ale jeśli użyjesz liczb pierwszych dla table_length, obliczone kody skrótu mogą odwzorować różne kubły skrótu, nawet jeśli masz nieco głupią funkcję skrótu.

A oto dowód.

Jeśli załóżmy, że funkcja hashCode powoduje między innymi następujące kody skrótu {x, 2x, 3x, 4x, 5x, 6x ...}, wówczas wszystkie one zostaną pogrupowane w tylko m liczbę segmentów, gdzie m = długość_tabeli / GreatestCommonFactor (table_length, x). (To jest trywialne, aby to zweryfikować / wyprowadzić). Teraz możesz wykonać jedną z następujących czynności, aby uniknąć tworzenia klastrów

Upewnij się, że nie generujesz zbyt wielu kodów skrótu, które są wielokrotnościami innego kodu skrótu, jak w {x, 2x, 3x, 4x, 5x, 6x ...}. Ale może to być trochę trudne, jeśli twój hashTable ma mieć miliony wpisów. Lub po prostu zrównaj m z wartością table_length, ustawiając GreatestCommonFactor (table_length, x) na 1, tj. Robiąc table_length coprime z x. A jeśli x może być dowolną liczbą, upewnij się, że table_length jest liczbą pierwszą.

Od - http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Całkiem jasne wyjaśnienie, również ze zdjęciami.

Edycja: Podsumowując, liczby pierwsze są używane, ponieważ masz największą szansę na uzyskanie unikalnej wartości, mnożąc wartości przez wybraną liczbę pierwszą i sumując je wszystkie. Na przykład biorąc pod uwagę ciąg, pomnożenie każdej wartości litery przez liczbę pierwszą, a następnie dodanie ich wszystkich da ci wartość skrótu.

Lepszym pytaniem byłoby, dlaczego dokładnie liczba 31?

tl; dr

index[hash(input)%2]spowodowałoby kolizję dla połowy wszystkich możliwych skrótów i zakresu wartości. index[hash(input)%prime]powoduje kolizję <2 wszystkich możliwych skrótów. Mocowanie dzielnika do rozmiaru tabeli zapewnia również, że liczba nie może być większa niż tabela.

Liczby pierwsze są używane, ponieważ masz duże szanse na uzyskanie unikalnej wartości dla typowej funkcji skrótu, która używa wielomianów modulo P. Powiedzmy, że używasz takiej funkcji skrótu dla ciągów o długości <= N, i masz kolizję. Oznacza to, że 2 różne wielomiany wytwarzają tę samą wartość modulo P. Różnica tych wielomianów jest znowu wielomianem o tym samym stopniu N (lub mniejszym). Ma nie więcej niż N pierwiastków (to jest tutaj natura matematyki, ponieważ twierdzenie to jest prawdziwe tylko dla wielomianu nad polem => liczba pierwsza). Więc jeśli N jest znacznie mniejsze niż P, prawdopodobnie nie dojdzie do kolizji. Następnie eksperyment może prawdopodobnie wykazać, że 37 jest wystarczająco duże, aby uniknąć kolizji dla tablicy mieszającej ciągów, które mają długość 5-10, i jest wystarczająco małe, aby użyć go do obliczeń.

Aby zapewnić alternatywny punkt widzenia, jest ta strona:

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

Co oznacza, że ​​należy używać możliwie największej liczby segmentów, a nie zaokrąglać do pierwszej liczby segmentów. Wydaje się to rozsądną możliwością. Intuicyjnie z pewnością widzę, jak lepsza byłaby większa liczba wiader, ale nie jestem w stanie przedstawić matematycznego argumentu na ten temat.

Liczby pierwsze to unikalne liczby. Są wyjątkowe pod tym względem, że iloczyn liczb pierwszych z dowolną inną liczbą ma największą szansę na bycie wyjątkowym (nie tak wyjątkowym jak sama liczba pierwsza) z uwagi na fakt, że liczba pierwsza jest używana. Ta właściwość jest używana w funkcjach mieszających.

Biorąc pod uwagę ciąg „Samuel”, możesz wygenerować unikalny skrót, mnożąc każdą z cyfr lub liter przez liczbę pierwszą i dodając je. Dlatego używane są liczby pierwsze.

Jednak używanie liczb pierwszych jest starą techniką. Kluczem tutaj jest zrozumienie, że dopóki możesz wygenerować wystarczająco unikalny klucz, możesz przejść do innych technik mieszania. Przejdź tutaj, aby uzyskać więcej informacji na ten temat na temat http://www.azillionmonkeys.com/qed/hash.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

To zależy od wyboru funkcji skrótu.

Wiele funkcji mieszających łączy różne elementy w danych, mnożąc je przez niektóre czynniki modulo potęgi dwóch odpowiadających wielkości słowa maszyny (moduł ten jest wolny po prostu pozwalając na przelanie obliczeń).

Nie chcesz żadnego wspólnego czynnika między mnożnikiem dla elementu danych a rozmiarem tablicy mieszającej, ponieważ wtedy może się zdarzyć, że zmiana elementu danych nie rozłoży danych na całą tabelę. Jeśli wybierzesz liczbę pierwszą dla wielkości stołu, taki wspólny czynnik jest bardzo mało prawdopodobny.

Z drugiej strony czynniki te są zwykle tworzone z nieparzystych liczb pierwszych, więc powinieneś być bezpieczny, używając potęgi dwóch do tabeli skrótów (np. Eclipse używa 31, gdy generuje metodę hashCode () Java).

Załóżmy, że Twój rozmiar tabeli (lub liczba modulo) to T = (B * C). Teraz, jeśli skrót dla twojego wejścia jest jak (N * A * B), gdzie N może być dowolną liczbą całkowitą, wtedy twoje wyjście nie będzie dobrze rozłożone. Ponieważ za każdym razem, gdy n staje się C, 2C, 3C itp., Dane wyjściowe zaczną się powtarzać. tzn. twoja produkcja będzie dystrybuowana tylko w pozycjach C. Zauważ, że C jest tutaj (T / HCF (rozmiar tabeli, skrót)).

Problem ten można wyeliminować, tworząc HCF 1. Liczby pierwsze są do tego bardzo dobre.

Kolejną interesującą rzeczą jest, gdy T wynosi 2 ^ N. Dadzą one wynik dokładnie taki sam, jak wszystkie niższe N ​​bitów hash wejściowych. Ponieważ każda liczba może być reprezentowana potęgami 2, kiedy weźmiemy modulo dowolnej liczby za pomocą T, odejmujemy wszystkie potęgi 2 liczby liczbowej, które są> = N, stąd zawsze podajemy liczbę określonego wzorca, zależnie od danych wejściowych . To także zły wybór.

Podobnie T jako 10 ^ N jest również zły z podobnych powodów (wzór w notacji dziesiętnej liczb zamiast binarnej).

Tak więc liczby pierwsze dają zwykle lepsze wyniki, dlatego są dobrym wyborem dla wielkości tabeli.

Kopiowanie z mojej innej odpowiedzi https://stackoverflow.com/a/43126969/917428 . Zobacz więcej szczegółów i przykładów.

Uważam, że ma to związek z faktem, że komputery działają w bazie 2. Pomyśl tylko, jak to samo działa w przypadku bazy 10:

• 8% 10 = 8
• 18% 10 = 8
• 87865378% 10 = 8

Nie ma znaczenia, jaka jest liczba: tak długo, jak kończy się na 8, jego moduł 10 będzie wynosił 8.

Wybranie wystarczająco dużej liczby, która nie jest potęgą dwóch, sprawi, że funkcja skrótu rzeczywiście będzie funkcją wszystkich bitów wejściowych, a nie ich podzbioru.

Chciałbym dodać coś do odpowiedzi Steve'a Jessopa (nie mogę tego komentować, ponieważ nie mam wystarczającej reputacji). Ale znalazłem pomocny materiał. Jego odpowiedź jest bardzo pomocna, ale popełnił błąd: rozmiar wiadra nie powinien być potęgą 2. Cytuję po prostu z książki „Wprowadzenie do algorytmu” Thomasa Cormena, Charlesa Leisersena i innych na stronie 263:

Stosując metodę podziału, zwykle unikamy pewnych wartości m. Na przykład m nie powinno być potęgą 2, ponieważ jeśli m = 2 ^ p, to h (k) jest tylko p bitów k najniższego rzędu. O ile nie wiemy, że wszystkie wzorce p-bitów niskiego rzędu są jednakowo prawdopodobne, lepiej zaprojektować funkcję skrótu w taki sposób, aby zależała od wszystkich bitów klucza. Jak pokazuje ćwiczenie 11.3-3, wybranie m = 2 ^ p-1, gdy k jest łańcuchem znaków interpretowanym w podstawce 2 ^ p, może być złym wyborem, ponieważ permutacja znaków k nie zmienia wartości skrótu.

Mam nadzieję, że to pomoże.

W przypadku funkcji skrótu ważne jest nie tylko ogólne minimalizowanie kolizji, ale także uniemożliwienie pozostania przy tym samym haszu przy zmianie kilku bajtów.

Powiedz, że masz równanie: (x + y*z) % key = xz 0<x<keyi 0<z<key. Jeśli klucz jest numerem podstawowym, n * y = klucz jest prawdziwy dla każdego n w N, a fałsz dla każdej innej liczby.

Przykład, w którym klucz nie jest najlepszym przykładem: x = 1, z = 2 i klucz = 8 Ponieważ klucz / z = 4 wciąż jest liczbą naturalną, 4 staje się rozwiązaniem dla naszego równania iw tym przypadku (n / 2) * y = klucz jest prawdziwy dla każdego n w N. Liczba rozwiązań równania praktycznie podwoiła się, ponieważ 8 nie jest liczbą pierwszą.

Jeśli nasz atakujący wie już, że 8 jest możliwym rozwiązaniem równania, może zmienić plik z produkowania 8 na 4 i nadal otrzymuje ten sam skrót.

Przeczytałem popularną witrynę Wordpress połączoną z niektórymi z powyższych popularnych odpowiedzi u góry. Z tego, co zrozumiałem, chciałbym podzielić się prostą obserwacją, którą poczyniłem.

Możesz znaleźć wszystkie szczegóły w tym artykule tutaj , ale załóż, że spełnione są następujące warunki:

• Użycie liczby pierwszej daje nam „najlepszą szansę” na unikalną wartość

Ogólna implementacja mapy skrótów chce, aby 2 rzeczy były unikalne.

• Unikalny kod skrótu dla klucza
• Unikalny indeks do przechowywania rzeczywistej wartości

Jak uzyskać unikalny indeks? Dzięki temu, że początkowy rozmiar wewnętrznego pojemnika również jest najważniejszy. Zasadniczo więc liczba pierwsza jest zaangażowana, ponieważ posiada tę unikalną cechę polegającą na wytwarzaniu unikalnych liczb, których używamy do identyfikowania obiektów i znajdowania indeksów w wewnętrznym kontenerze.

Przykład:

klucz = „klucz”

wartość = „wartość” uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

mapuje na unikalny identyfikator

Teraz chcemy wyjątkowej lokalizacji dla naszej wartości - więc my

uniqueId % internalContainerSize == uniqueLocationForValue, zakładając, że internalContainerSizejest także liczbą pierwszą.

Wiem, że jest to uproszczone, ale mam nadzieję, że uda się zrealizować ogólny pomysł.

„Natura matematyki” dotycząca modułów mocy pierwotnej polega na tym, że są one jednym z elementów składowych pola skończonego . Pozostałe dwa bloki konstrukcyjne to operacja dodawania i mnożenia. Specjalną właściwością modułów pierwszych jest to, że tworzą one pole skończone z „regularnymi” operacjami dodawania i mnożenia, właśnie wziętymi do modułu. Oznacza to, że każde zwielokrotnienie odwzorowuje na liczbę pierwszą modulo liczby całkowitej, podobnie jak każde dodanie.

Moduły Prime są korzystne, ponieważ:

• Dają największą swobodę przy wyborze wtórnego mnożnika w haszowaniu wtórnym, wszystkie mnożniki oprócz 0 ostatecznie odwiedzą wszystkie elementy dokładnie raz
• Jeśli wszystkie wartości skrótu są mniejsze niż moduł, nie będzie żadnych kolizji
• Losowe liczby pierwsze mieszają się lepiej niż moc dwóch modułów i kompresują informacje o wszystkich bitach, a nie tylko podzbiorze

Mają jednak duży minus, wymagają podziału na liczby całkowite, co zajmuje wiele (~ 15-40) cykli, nawet na nowoczesnym procesorze. Przy około połowie obliczeń można się upewnić, że skrót jest dobrze wymieszany. Dwie multiplikacje i operacje xorshift zmieszają się lepiej niż główny moudulus. Następnie możemy użyć dowolnego rozmiaru tablicy skrótu, a redukcja skrótu jest najszybsza, dając w sumie 7 operacji dla mocy 2 rozmiarów tabeli i około 9 operacji dla dowolnych rozmiarów.

Niedawno przyjrzałem się wielu najszybszym implementacjom tabeli skrótów i większość z nich nie używa modułów głównych.

To pytanie zostało połączone z bardziej odpowiednim pytaniem, dlaczego tabele skrótów powinny używać tablic o największej wielkości, a nie potęga 2. W przypadku samych funkcji skrótu jest tutaj wiele dobrych odpowiedzi, ale w przypadku pokrewnego pytania, dlaczego niektóre tabele skrótów o kluczowym znaczeniu dla bezpieczeństwa , podobnie jak glibc, używaj tablic pierwszej wielkości, jeszcze ich nie ma.

Ogólnie moc 2 tabel jest znacznie szybsza. Jest to droga h % n => h & bitmask, w której maskę bitową można obliczyć za pomocą clz(„zera wiodących zer”) o rozmiarze n. Funkcja modulo musi wykonywać dzielenie liczb całkowitych, które jest około 50 razy wolniejsze niż logiczne and. Istnieje kilka sztuczek, aby uniknąć modulo, takich jak użycie https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ Lemire , ale ogólnie szybkie tabele skrótów używają mocy z 2, a bezpieczne tabele skrótów używają liczb pierwszych.

Dlaczego tak?

Bezpieczeństwo w tym przypadku jest definiowane przez ataki na strategię rozwiązywania kolizji, która polega na tym, że większość tabel skrótów jest po prostu liniowym wyszukiwaniem na połączonej liście kolizji. Lub dzięki szybszym tabelom z otwartym adresowaniem wyszukiwanie liniowe bezpośrednio w tabeli. Zatem dzięki potędze 2 tabel i pewnej wewnętrznej wiedzy o tabeli, np. Wielkości lub kolejności listy kluczy dostarczanej przez interfejs JSON, otrzymujesz liczbę użytych odpowiednich bitów. Liczba jedynek na masce bitowej. Zazwyczaj jest to mniej niż 10 bitów. A dla 5-10 bitów trywialne jest brutalne zderzanie siłą nawet przy najsilniejszych i najwolniejszych funkcjach skrótu. Nie masz już pełnego bezpieczeństwa swoich 32-bitowych lub 64-bitowych funkcji skrótu. Chodzi o to, aby korzystać z szybkich małych funkcji haszujących, a nie potworów, takich jak szmer, a nawet syfon.

Jeśli więc udostępniasz zewnętrzny interfejs do tabeli skrótów, taki jak DNS resolver, język programowania, ... chcesz dbać o nadużycia ludzi, którzy lubią DOS takie usługi. Zwykle takim ludziom łatwiej jest zamknąć usługę publiczną przy użyciu znacznie łatwiejszych metod, ale tak się stało. Ludzie się tym przejmowali.

Zatem najlepsze opcje zapobiegania takim atakom kolizyjnym to:

1) użyć tabel głównych, ponieważ wtedy

• wszystkie 32 lub 64 bity są odpowiednie do znalezienia wiadra, a nie tylko kilka.
• funkcja zmiany rozmiaru tabeli skrótów jest bardziej naturalna niż tylko podwójna. Najlepszą funkcją wzrostu jest sekwencja fibonacciego, a liczby pierwsze są do niej bliższe niż podwajanie.

2) zastosuj lepsze środki przeciwko rzeczywistemu atakowi, wraz z szybką siłą 2 rozmiarów.

• policz kolizje i przerywaj lub śpij w przypadku wykrytych ataków, czyli liczby kolizji z prawdopodobieństwem <1%. Jak 100 z 32-bitowymi tabelami skrótów. Tak właśnie działa np. Dnsb resolver djb.
• przekonwertuj połączoną listę kolizji na drzewa za pomocą O (log n) wyszukiwania, a nie O (n) po wykryciu ataku kolizyjnego. Tak właśnie działa np. Java.

Istnieje szeroko rozpowszechniony mit, że bezpieczniejsze funkcje skrótu pomagają zapobiegać takim atakom, co jest błędne, jak wyjaśniłem. Nie ma bezpieczeństwa tylko przy niskich bitach. Działa to tylko z tabelami o podstawowych rozmiarach, ale użyłby kombinacji dwóch najwolniejszych metod, powolnego mieszania i powolnego modulo.

Funkcje skrótu w tabelach skrótów muszą być przede wszystkim małe (aby były nieuniknione) i szybkie. Bezpieczeństwo może pochodzić tylko z zapobiegania liniowemu wyszukiwaniu w zderzeniach. I nie należy używać trywialnie złych funkcji skrótu, takich jak te niewrażliwe na niektóre wartości (np. \ 0 przy użyciu mnożenia).

Korzystanie z losowych nasion jest również dobrą opcją, ludzie zaczęli od tego pierwszego, ale przy wystarczającej informacji o tabeli nawet losowe ziarno nie pomaga wiele, a dynamiczne języki zazwyczaj sprawiają, że uzyskanie ziarna za pomocą innych metod jest banalne, ponieważ jest ono przechowywane w znane lokalizacje pamięci.

function eratosthenes(n) {

    function getPrime(x) {
        var middle = (x-(x%2))/2;
        var arr_rest = [];
        for(var j=2 ; j<=middle;j++){
            arr_rest.push(x%j);
        }

        if(arr_rest.indexOf(0) == -1) {
            return true
        }else {
            return false
        }

    }
    if(n<2)  {
        return []
    }else if(n==2){
        return [2]
    }else {
        var arr = [2]
        for(var i=3;i<n;i++) {
            if(getPrime(i)){
                arr.push(i)
            }
        }
    }

    return arr;
}