Hledání cyklu

Hledání cyklu  je algoritmický úkol hledání cyklu v posloupnosti hodnot iterační funkce .

Pro libovolnou funkci f , která do sebe mapuje konečnou množinu S , a pro libovolnou počáteční hodnotu x 0 z S , posloupnost iteračních hodnot funkce:

musí nakonec použít stejnou hodnotu dvakrát, to znamená, že musí existovat dvojice indexů i a j taková, že x i = x j . Jakmile k tomu dojde, sekvence bude periodicky pokračovat a bude se opakovat stejná sekvence hodnot od x i do x j − 1 . Hledání cyklu je úkolem najít indexy i a j dané funkcí f a počáteční hodnotou x 0 .

Je známo několik algoritmů pro rychlé nalezení cyklu s malou pamětí. Floydův algoritmus „želva a zajíc“ pohybuje dvěma ukazateli různými rychlostmi po sekvencích hodnot, dokud nedostanou stejné hodnoty. Další algoritmus, Brentův algoritmus, je založen na myšlence exponenciálního vyhledávání . Jak Floydův, tak Brentův algoritmus používají pouze pevný počet paměťových buněk a počet vyhodnocení funkcí je úměrný vzdálenosti od počátečního bodu k prvnímu bodu opakování. Některé další algoritmy používají více paměti, aby získaly méně vyhodnocení funkčních hodnot.

Problém hledání cyklu se používá k testování kvality generátorů pseudonáhodných čísel a kryptografických hašovacích funkcí , v algoritmech výpočetní teorie čísel k určení nekonečných cyklů v počítačových programech a periodických konfiguracích celulárních automatů a k automatické analýze tvaru seznamů . .

Příklad

Obrázek ukazuje funkci f , která mapuje množinu S = {0,1,2,3,4,5,6,7,8 } na sebe. Pokud začneme z bodu x 0 = 2 a zopakujeme aplikaci funkce f na výsledné hodnoty, uvidíme posloupnost hodnot

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....

Cyklus v této sekvenci hodnot je 6, 3, 1 .

Definice

Nechť S  je konečná množina, f  nějaká funkce, která mapuje S na stejnou množinu, a x 0  libovolný prvek S . Pro libovolné i > 0 nechť x i = f ( x i − 1 ) . Nechť μ je  nejmenší index, pro který se hodnota x μ opakuje nekonečněkrát v posloupnosti hodnot x i , a nechť λ (délka cyklu) je nejmenší kladné celé číslo, takže x μ = x λ + μ . Problém hledání cyklu je problém hledání λ a μ [1] .

Tento problém můžete považovat za problém teorie grafů, pokud sestrojíte funkční graf (tedy orientovaný graf , ve kterém má každý vrchol jeden vycházející oblouk), jehož vrcholy jsou prvky množiny S a hrany odpovídají mapování prvků na odpovídající funkční hodnoty, jak je znázorněno na obrázku . Množina vrcholů dosažitelná z výchozího vrcholu x 0 tvoří podgraf ve tvaru podobném řeckému písmenu rho ( ρ ) — cestu délky μ od x 0 k cyklu λ vrcholů [2] .

Reprezentace v počítači

Typ f není specifikován jako tabulka hodnot, jak je znázorněno na obrázku výše. Algoritmus detekce smyčky může spíše přijmout jako vstup buď sekvenci hodnot x i , nebo výpočetní rutinu f . Problém je najít λ a μ kontrolou malého počtu hodnot posloupnosti, nebo co nejméně krát zavolat proceduru pro výpočet hodnoty. Obvykle je důležitá i kapacitní složitost algoritmu pro problém nalezení cyklu: je žádoucí použít paměť, která je mnohem menší ve srovnání s velikostí celé sekvence.

V některých aplikacích, a zejména v Pollardově rho algoritmu pro celočíselnou faktorizaci , má algoritmus velmi omezený přístup k S a f . V Pollardově ro-algoritmu je například S  množina čísel srovnatelných z hlediska neznámého prvočinitele, která musí být faktorizována, takže ani velikost množiny S pro algoritmus není známa. Aby algoritmus hledání cyklu fungoval v takto omezených podmínkách, musí být vyvinut na základě následujících možností. Zpočátku má algoritmus v paměti objekt, který představuje ukazatel na počáteční hodnotu x 0 . Algoritmus může v libovolném kroku provést jednu ze tří věcí: může zkopírovat jakýkoli ukazatel do jakéhokoli jiného paměťového objektu, může vypočítat hodnotu f a nahradit jakýkoli ukazatel na ukazatel nově vytvořeným objektem ze sekvence nebo může použít proceduru ke kontrole shody mezi hodnotami, na které ukazují dva ukazatele.

Test rovnosti může zahrnovat některé netriviální výpočty. Například v Pollardově ro-algoritmu tento test kontroluje, zda rozdíl dvou uložených hodnot má netriviálního největšího společného dělitele s faktorizovatelným číslem [2] . V tomto kontextu, analogicky s modelem výpočtu ukazatele , algoritmus, který používá pouze kopírování ukazatelů, pohyb v sekvencích a testování rovnosti, lze nazvat ukazatelovým algoritmem.

Algoritmy

Pokud je vstup zadán jako výpočetní rutina f , problém nalezení cyklu lze triviálně vyřešit provedením pouze volání funkcí λ + μ jednoduše výpočtem sekvence hodnot x i a použitím datové struktury , jako je hash tabulka . uložit tyto hodnoty a otestovat, že každá další hodnota ještě nebyla uložena. Kapacitní složitost tohoto algoritmu je však úměrná λ + μ a tato složitost je zbytečně velká. Také použití této metody pro algoritmus ukazatele by vyžadovalo test rovnosti pro každou dvojici hodnot, což by vedlo ke kvadratickému času. Výzkum v této oblasti má tedy dva cíle: použít méně prostoru než tento jednoduchý algoritmus a najít ukazatelový algoritmus, který používá méně testů rovnosti.

Želva a zajíc

Floydův cyklický vyhledávací  algoritmus je ukazatelový algoritmus, který používá pouze dva ukazatele, které se pohybují po sekvenci různými rychlostmi. Algoritmus se také nazývá algoritmus "želva a zajíc" s nádechem Ezopovy bajky "Želva a zajíc" .

Algoritmus je pojmenován po Robertu Floydovi , kterému se připisuje vynálezce metody Donalda Knutha [3] [4] . Algoritmus však nebyl publikován ve Floydových článcích, a to může být atribuční chyba: Floyd popisuje algoritmy pro výpis všech jednoduchých cyklů v orientovaném grafu v článku z roku 1967 [5] , ale tento článek nepopisuje problém nalezení cyklu ve funkčních grafech, které jsou předmětem úvahy v článku. Ve skutečnosti Knuthovo prohlášení z roku 1969, připisující algoritmus Floydovi bez citace, je první známou zmínkou o tomto algoritmu v tisku, a proto se algoritmus může ukázat jako matematický folklór , který nepatří konkrétní osobě. [6] .

Hlavní myšlenkou algoritmu je, že pro jakákoli celá čísla i ≥ μ a k ≥ 0 platí x i = x i + kλ , kde λ  je délka cyklu a μ  je index prvního prvku v cyklu. Konkrétně i = kλ ≥ μ právě tehdy, když x i = x 2i .

Aby tedy algoritmus našel periodu opakování ν , která je násobkem λ , potřebuje pouze zkontrolovat opakování hodnot tohoto speciálního druhu – jedna hodnota je dvakrát tak daleko od začátku než druhá.

Jakmile byla nalezena perioda ν , algoritmus se vrátí k posloupnosti od počátečního bodu, aby našel první opakovanou hodnotu x μ v posloupnosti, s využitím skutečnosti, že λ dělí ν a tedy x μ = x μ + v . Konečně, jakmile je známa hodnota μ , je snadné najít délku λ nejkratšího opakovacího cyklu nalezením první polohy μ + λ , pro kterou x μ + λ = x μ .

Algoritmus používá dva ukazatele v dané sekvenci: jeden (želva) prochází hodnotami x i a druhý (zajíc) prochází hodnotami x 2 i . V každém kroku algoritmu se index i zvýší o jednu, čímž se želva posune o jeden prvek dopředu a zajíc o dva prvky, načež se hodnoty v těchto bodech porovnají. Nejmenší hodnota i > 0 , pro kterou budou želva a zajíc ukazovat na stejnou hodnotu, je požadovaná hodnota ν .

Následující program Python ukazuje, jak lze nápad implementovat.

def floyd ( f , x0 ): # Hlavní část algoritmu: najít opakování x_i = x_2i. # Zajíc se pohybuje dvakrát rychleji než želva, # a vzdálenost mezi nimi se krok od kroku zvětšuje o jednu. # Jednoho dne budou uvnitř cyklu a pak vzdálenost mezi nimi # bude dělitelná λ. želva = f ( x0 ) # f(x0) je prvek následující za x0. zajíc = f ( f ( x0 )) , zatímco želva != zajíc : želva = f ( želva ) zajíc = f ( f ( zajíc )) # V tuto chvíli je poloha želvy ν, # která se rovná vzdálenosti mezi želvou a zajícem, # dělena periodou λ. Zajíc, pohybující se # po kruhu o jednu pozici, # a želva, počínaje znovu od výchozího bodu x0 a # přibližující se k kruhu, se setkají na začátku kruhu # Najděte polohu μ setkání . mu = 0 želva = x0 zatímco želva != zajíc : želva = f ( želva ) zajíc = f ( zajíc ) # Zajíc a želva se pohybují stejnou rychlostí mu += 1 # Najděte délku nejkratšího cyklu počínaje pozicí x_μ # Zajíc se posune o jednu pozici vpřed, # zatímco želva stojí na místě. lam = 1 zajíc = f ( želva ) zatímco želva ! = zajíc : zajíc = f ( zajíc ) lam += 1 vrátit lam , mu

Tento kód přistupuje k sekvenci pouze zapamatováním a kopírováním ukazatelů, vyhodnocením funkce a kontrolou rovnosti. Algoritmus je tedy ukazatelový algoritmus. Algoritmus používá O ( λ + μ ) operace těchto typů a O (1) paměť [7] .

Brentův algoritmus

Richard Brent popsal alternativní algoritmus hledání cyklu, který stejně jako želvový a zajícový algoritmus vyžaduje pouze dva ukazatele na sekvenci [8] . Je však založen na jiném principu - najít nejmenší mocninu 2 i čísla 2, která je větší než λ i μ .

Pro i = 0, 1, 2, ... algoritmus porovnává x 2 i −1 s hodnotami v posloupnosti až do další mocniny dvou, přičemž proces zastaví, když je nalezena shoda. Algoritmus má ve srovnání s algoritmem želvy a zajíce dvě výhody: za prvé najde správnou délku cyklu λ okamžitě a nepotřebuje k jejímu určení druhý krok, a za druhé, v každém kroku je funkce f volána pouze jednou a ne třikrát [9] .

Následující program Python ukazuje, jak tato technika funguje podrobněji.

def brent ( f , x0 ): # Hlavní fáze: hledejte mocninu dvou mocnin = lam = 1 želva = x0 zajíc = f ( x0 ) # f(x0) je prvek/uzel následující za x0. zatímco želva != zajíc : if power == lam : # čas začít novou sílu dvou? želva = síla zajíce *= 2 lam = 0 zajíc = f ( zajíc ) lam += 1 # Najděte pozici prvního opakování délky λ mu = 0 želva = zajíc = x0 pro i v rozsahu ( lam ): # range(lam) tvoří seznam s hodnotami 0, 1, ... , lam-1 zajíc = f ( zajíc ) # vzdálenost mezi želvou a zajícem je nyní λ. # Nyní se želva a zajíc pohybují stejnou rychlostí, dokud se nepotkají, zatímco želva != zajíc : želva = f ( želva ) zajíc = f ( zajíc ) mu += 1 vrátit lam , mu

Stejně jako algoritmus želvy a zajíce je tento algoritmus ukazatelovým algoritmem používajícím O ( λ + μ ) kontroly a volání funkcí a O (1) paměť . Je snadné ukázat, že počet volání funkcí nikdy nepřekročí počet volání ve Floydově algoritmu.

Brent tvrdí, že jeho algoritmus je v průměru asi o 36 % rychlejší než Floydův a že překonává Pollardův ro-algoritmus asi o 24 %. Provedl analýzu prostřední varianty pravděpodobnostní verze algoritmu, ve které posloupnost indexů procházejících pomalým ukazatelem není mocninou dvou, ale je mocninou dvou násobenou náhodným faktorem. Ačkoli hlavním cílem jeho algoritmu bylo faktorizovat číslo, Brent také diskutuje o aplikaci algoritmu pro testování pseudonáhodných generátorů [8] .

Čas na paměť

Mnoho autorů studovalo techniky vyhledávání smyček, které využívají více paměti než metody Floyd a Brent, ale jsou rychlejší. Obecně si tyto metody pamatují některé dříve vypočítané sekvenční hodnoty a kontrolují, zda nová hodnota odpovídá jedné z naučených hodnot. Aby toho dosáhli rychle, obvykle používají hashovací tabulky nebo podobné datové struktury, a proto takové algoritmy nejsou ukazatelovými algoritmy (zejména je obvykle nelze přizpůsobit Pollardovu rho algoritmu). Kde se tyto metody liší, je způsob, jakým určují, které hodnoty si zapamatovat. V návaznosti na Nivash [10] si tyto techniky stručně zopakujeme.

Brent [8] již popsal varianty své techniky, ve které jsou indexy uložených sekvenčních hodnot mocniny R jiné než dvě. Volbou R blíže jedné a uložením sekvenčních hodnot s indexy blízkými po sobě jdoucím mocninám R může algoritmus hledání cyklu využít počet volání funkcí, který nepřekročí libovolně malý faktor optimální hodnoty λ + μ [11 ] [12] .

Sedgwick, Szymanski a Yao [13] navrhli metodu, která využívá M paměťových míst a vyžaduje v nejhorším případě pouze volání funkcí s nějakou konstantou c , pro kterou se ukázalo jako optimální. Technika využívá číselný parametr d , přičemž do tabulky ukládá pouze ty pozice sekvence, které jsou násobky d . Pokud je počet uložených hodnot příliš velký , tabulka se vymaže a hodnota d se zdvojnásobí.

Někteří autoři popsali metody označených bodů , které ukládají funkční hodnoty do tabulky na základě kritérií, která používají hodnoty spíše než indexy (jako v metodě Sedgwick et al.). Například lze uložit hodnoty modulo z nějakého čísla d [14] [15] . Jednodušeji, Nivasch [10] připisuje Woodroofovi návrh zapamatovat si náhodně vybranou předchozí hodnotu tím, že v každém kroku provede vhodnou náhodnou volbu.

Nivash [10] popisuje algoritmus, který nepoužívá pevné množství paměti, ale u kterého očekávané množství použité paměti (za předpokladu, že vstupní funkce je náhodná) závisí logaritmicky na délce sekvence. Pomocí této techniky se prvek zapíše do tabulky, pokud žádný předchozí prvek nemá nižší hodnotu. Jak ukázal Nivasch, prvky v této technice lze umístit na hromádku a každou následující hodnotu je třeba porovnat pouze s prvkem v horní části stohu. Algoritmus se zastaví, když je nalezeno opakování prvku s menší hodnotou. Pokud použijeme několik zásobníků a náhodnou permutaci hodnot v každém zásobníku, získáme nárůst rychlosti na úkor paměti, podobně jako u předchozích algoritmů. Ani jednovrstvá verze algoritmu však není ukazatelovým algoritmem, protože potřebuje vědět, která z hodnot je menší.

Jakýkoli algoritmus pro vyhledávání smyček, který si pamatuje maximálně M hodnot ze vstupní sekvence, musí provádět alespoň volání funkcí [16] [17] .

Aplikace

Hledání cyklů se používá v mnoha aplikacích.

Určení délky cyklu generátoru pseudonáhodných čísel je jedním z měřítek jeho síly. Tuto aplikaci zmínil Knuth při popisu Floydovy metody [3] . Brent [8] popsal výsledek testování lineárního kongruenciálního generátoru . Období generátoru se ukázalo být výrazně kratší, než bylo inzerováno. U složitějších generátorů nemusí sekvence hodnot, ve kterých se cyklus nachází, představovat výstup generátoru, ale pouze jeho vnitřní stav.

Několik algoritmů teorie čísel se spoléhá na nalezení cyklu, včetně Pollardova ro-algoritmu pro faktorizaci celého čísla [18] a souvisejícího klokaního algoritmu pro problém diskrétního logaritmu [19] .

V kryptografii může schopnost najít dvě různé hodnoty x μ−1 a x λ+μ−1 , mapované nějakou kryptografickou funkcí ƒ na stejnou hodnotu x μ , indikovat slabost ƒ. Například Quiscatre a Delessaille [15] aplikovali cyklické vyhledávací algoritmy k nalezení zprávy a páru klíčů DES , který mapuje tuto zprávu na stejnou zašifrovanou hodnotu. Kaliski , Rivest a Sherman [20] také použili algoritmy pro vyhledávání cyklů k útoku na DES. Technika může být použita k nalezení kolizí v kryptografické hashovací funkci [21] .

Hledání smyček může být užitečné jako způsob detekce nekonečných smyček v některých typech počítačových programů [22] .

Periodické konfigurace v modelování celulárních automatů lze nalézt aplikací algoritmů pro vyhledávání cyklů na sekvenci stavů automatu [10] .

Analýza tvaru seznamu je technika pro kontrolu správnosti algoritmu, který tyto struktury používá. Pokud uzel v seznamu nesprávně odkazuje na dřívější uzel ve stejném seznamu, struktura vytvoří cyklus, který lze nalézt pomocí takových algoritmů [23] . V Common Lisp tiskárnaproměnných S-expression*print-circle* detekuje struktury seznamu ve smyčce a kompaktně je vytiskne.

Teske [12] popisuje aplikaci ve výpočetní teorii grup pro výpočet struktury abelovské grupy dané její sadou generátorů. Kryptografické algoritmy Kalisky et al [20] lze také chápat jako pokus o odhalení struktury neznámé skupiny.

Fitch [24] krátce zmínila aplikaci pro počítačové modelování nebeské mechaniky , kterou připisuje Kahanovi . V této aplikaci lze nalezení cyklu ve fázovém prostoru systému drah použít k určení, zda je systém periodický vzhledem k přesnosti modelu [16] .

Poznámky

  1. ↑ Joux, 2009 , str. 223.
  2. ↑ 12 Joux , 2009 , str. 224.
  3. ↑ 1 2 Knuth, 1969 , s. 7, ex. 6, 7.
  4. ↑ Menezes, van Oorschot, Vanstone, 1996 , s. 125.
  5. ↑ Floyd, 1967 , str. 636-644.
  6. ↑ Aumasson, Meier, Phan, Henzen, 2015 , str. 21, poznámka pod čarou 8.
  7. ↑ Joux, 2009 , str. 225-226, oddíl 7.1.1, Floydův algoritmus pro vyhledávání cyklu.
  8. ↑ 1 2 3 4 Brent, 1980 , str. 176-184.
  9. ↑ Joux, 2009 , str. 226-227, oddíl 7.1.2, Brentův algoritmus pro vyhledávání cyklu.
  10. ↑ 1 2 3 4 Nivasch, 2004 , str. 135-140.
  11. ↑ Schnorr, Lenstra, 1984 , str. 289-311.
  12. ↑ 12 Teske , 1998 , str. 1637-1663.
  13. ↑ Sedgewick, Szymanski, Yao, 1982 , str. 376-390.
  14. ↑ van Oorschot, Wiener 1999 , s. 1-28.
  15. ↑ 1 2 Quisquater, Delescaille, 1989 , str. 429-434.
  16. ↑ 12 Fich , 1981 , s. 96-105.
  17. ↑ Allender a Klawe 1985 , s. 231-237.
  18. ↑ Pollard, 1975 , s. 331-334.
  19. ↑ Pollard, 1978 , s. 918-924.
  20. ↑ 1 2 Kaliski, Rivest & Sherman, 1988 , s. 3-36.
  21. ↑ Joux, 2009 , str. 242-245, oddíl 7.5, Kolize v hašovacích funkcích.
  22. ↑ Van Gelder, 1987 , s. 23-31.
  23. ↑ Auguston, Hon, 1997 , s. 37-42.
  24. ↑ Fich, 1981 .

Literatura

  • Allender, Eric W.; Klawe, Maria M.  Vylepšené dolní meze pro problém detekce cyklu // Teoretická informatika . - 1985. - Sv. 36, č. 2–3. - doi : 10.1016/0304-3975(85)90044-1 .  - S. 231-237.
  • Auguston, Michael; Dobrý den, Miu Har. . Assertions for Dynamic Shape Analysis of List Data Structures // AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging . - Linköping University , 1997. - (Linköping Electronic Articles in Computer and Information Science).  - S. 37-42.
  • Aumasson, Jean-Philippe; Meier, Willie; Phan, Raphael C.-W.; Henzen, Luca. . Hashovací funkce BLAKE . - Heidelberg, New York, Dordrecht, Londýn: Springer, 2015. - (Informační bezpečnost a kryptografie). — ISBN 978-3-662-44756-7 .
  • Brent R. P.  Vylepšený faktorizační algoritmus Monte Carlo  // BIT Numerical Mathematics . - 1980. - Sv. 20, č. 2. - S. 176-184. - doi : 10.1007/BF01933190 .
  • Fich, Faith Ellen. . Dolní hranice pro problém detekce cyklu // Proc. 13. sympozium ACM o teorii výpočetní techniky . - 1981. - doi : 10.1145/800076.802462 .  - S. 96-105.
  • Floyd R. W.  Nedeterministické algoritmy  // Journal of ACM. - 1967. - Sv. 14, č. 4. - S. 636-644. - doi : 10.1145/321420.321422 .
  • Joux, Antoine. . Algoritmická kryptoanalýza . - CRC Press, 2009. - S. 223. - ISBN 9781420070033 .
  • Kaliski, Burton S. Jr.; Rivest, Ronald L .; Sherman Alan T.  Je standard šifrování dat skupinou? (Výsledky cyklistických experimentů na DES) // Journal of Cryptology . - 1988. - Sv. 1, č. 1. - S. 3-36. - doi : 10.1007/BF00206323 .
  • Knuth, Donald  E. The Art of Computer Programming, sv. II: Seminumerické algoritmy. - Addison-Wesley, 1969. - S. 7, cvičení 6 a 7.
    • Ruský překlad: D. E. Knut  . Umění programování. 3. vyd. V. 2. Získané algoritmy. - Williams, 2005. - ISBN 5-8459-0081-6 .
  • Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. Příručka aplikované kryptografie . - CRC Press, 1996. - ISBN 0-8493-8523-7 .
  • Nivasch, Gabriel. Detekce cyklu pomocí zásobníku // Information Processing Letters . - 2004. - Sv. 90, č. 3. - S. 135-140. - doi : 10.1016/j.ipl.2004.01.016 .
  • Pollard J. M.  Metoda Monte Carlo pro faktorizaci // BIT. - 1975. - Sv. 15, č. 3. - S. 331-334. - doi : 10.1007/BF01933667 .
  • Metody Pollard J. M.  Monte Carlo pro výpočet indexu (mod p ) // Matematika počítání . - Americká matematická společnost, 1978. - Sv. 32, č. 143. - S. 918-924. - doi : 10.2307/2006496 . — .
  • Quisquater J.-J., Delescaille J.-P. . Jak snadné je vyhledávání kolize? Aplikace na DES // Pokroky v kryptologii - EUROCRYPT '89, Workshop o teorii a aplikaci kryptografických technik . - Springer-Verlag, 1989. - S. 429-434. - (Lecture Notes in Computer Science, sv. 434).  (nedostupný odkaz)
  • Schnorr, Claus P.; Lenstra, Hendrik W.  Faktorizační algoritmus Monte Carlo s lineárním úložištěm // Matematika výpočtu . - 1984. - Sv. 43, č.p. 167. - S. 289-311. - doi : 10.2307/2007414 . — .
  • Sedgewick, Robert; Szymanski, Thomas G.; Yao, Andrew C.-C. Složitost hledání cyklů v periodických funkcích // SIAM Journal on Computing . - 1982. - Sv. 11, č. 2. - S. 376-390. - doi : 10.1137/0211030 .
  • Teske, Edlyn. Prostorově efektivní algoritmus pro výpočet skupinové struktury // Matematika počítání . - 1998. - Sv. 67, č.p. 224. - S. 1637-1663. - doi : 10.1090/S0025-5718-98-00968-5 .
  • Van Gelder, Allen. Efektivní detekce smyčky v Prologu pomocí techniky želvy a zajíce // Journal of Logic Programming. - 1987. - Sv. 4, č. 1. - S. 23-31. - doi : 10.1016/0743-1066(87)90020-3 .
  • van Oorschot, Paul C.; Wiener, Michael J.  Paralelní vyhledávání kolizí s kryptoanalytickými aplikacemi // Journal of Cryptology . - 1999. - Sv. 12, č. 1. - S. 1-28. - doi : 10.1007/PL00003816 .

Odkazy