Att hitta en cykel

Att hitta en cykel  är en algoritmisk uppgift att hitta en cykel i en sekvens av värden av en iterativ funktion .

För vilken funktion f som helst som mappar en ändlig mängd S in i sig själv, och för varje initialvärde x 0 från S , sekvensen av iterativa värden för funktionen:

måste så småningom använda samma värde två gånger, det vill säga det måste finnas ett par index i och j så att x i = x j . När detta händer kommer sekvensen att fortsätta med jämna mellanrum och upprepa samma sekvens av värden från x i till x j − 1 . Att hitta en cykel är uppgiften att hitta index i och j givet en funktion f och ett initialt värde x 0 .

Flera algoritmer för att hitta en cykel snabbt och med lite minne är kända. Floyds "sköldpadda och hare"-algoritm flyttar två pekare i olika hastigheter genom en sekvens av värden tills de får samma värden. En annan algoritm, Brents algoritm, är baserad på idén om exponentiell sökning . Både Floyds och Brents algoritmer använder endast ett fast antal minnesceller, och antalet funktionsutvärderingar är proportionellt mot avståndet från startpunkten till den första repetitionspunkten. Vissa andra algoritmer använder mer minne för att få färre utvärderingar av funktionsvärdena.

Cykelsökningsproblemet används för att testa kvaliteten på pseudo-slumptalsgeneratorer och kryptografiska hashfunktioner , i beräkningsalgoritmer för talteori för att bestämma oändliga cykler i datorprogram och periodiska konfigurationer av cellulära automater , och för att automatiskt analysera formen på listor. .

Exempel

Figuren visar en funktion f som mappar mängden S = {0,1,2,3,4,5,6,7,8 } på sig själv. Om vi ​​börjar från punkten x 0 = 2 och upprepar tillämpningen av funktionen f på de resulterande värdena, kommer vi att se en sekvens av värden

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

Cykeln i denna värdesekvens är 6, 3, 1 .

Definitioner

Låt S  vara en finit mängd, f  någon funktion som mappar S till samma mängd, och x 0  vilket element som helst av S . För valfritt i > 0 låt x i = f ( x i − 1 ) . Låt μ vara det  minsta index för vilket värdet x μ upprepas ett oändligt antal gånger i värdeföljden x i , och låt λ (cykellängd) vara det minsta positiva heltal så att x μ = x λ + μ . Problemet med att hitta en cykel är problemet med att hitta λ och μ [1] .

Du kan betrakta detta problem som ett grafteoretiskt problem om du konstruerar en funktionell graf (det vill säga en riktad graf där varje vertex har en enda utgående båge), vars hörn är element i mängden S , och kanterna motsvarar mappningen av element till motsvarande funktionsvärden, som visas i figuren. Uppsättningen av hörn som kan nås från startpunkten x 0 bildar en subgraf i form som liknar den grekiska bokstaven rho ( ρ ) — en väg med längden μ från x 0 till en cykel av λ - hörn [2] .

Representation i en dator

Vanligtvis anges inte f som en värdetabell, som visas i figuren ovan. Snarare kan loopdetekteringsalgoritmen ta som indata antingen en sekvens av värden x i eller en beräkningsrutin f . Problemet är att hitta λ och μ genom att kontrollera ett litet antal värden i sekvensen, eller genom att anropa proceduren för att beräkna värdet så få gånger som möjligt. Vanligtvis är kapacitetskomplexiteten för algoritmen för problemet med att hitta en cykel också viktig: det är önskvärt att använda minne som är mycket mindre jämfört med storleken på hela sekvensen.

I vissa applikationer, och i synnerhet Pollards rho-algoritm för heltalsfaktorisering , har algoritmen mycket begränsad tillgång till S och f . I Pollards ro-algoritm, till exempel, är S  en uppsättning tal som är jämförbara i termer av en okänd primtalsfaktor, som måste faktoriseras, så att även storleken på mängden S för algoritmen är okänd. För att cykelsökningsalgoritmen ska fungera under sådana begränsade förhållanden måste den utvecklas utifrån följande möjligheter. Inledningsvis har algoritmen ett objekt i minnet som representerar en pekare till det initiala värdet x 0 . I vilket steg som helst kan algoritmen göra en av tre saker: den kan kopiera vilken pekare som helst till vilket annat minnesobjekt som helst, den kan beräkna värdet på f och ersätta valfri pekare till pekare med ett nybildat objekt från sekvensen, eller kan använda en procedur för att kontrollera om det finns en överensstämmelse mellan värdena som pekas på av två pekare.

Likhetsprövningen kan innebära vissa icke-triviala beräkningar. Till exempel, i Pollards ro-algoritm, kontrollerar detta test om skillnaden mellan två lagrade värden har en icke-trivial största gemensamma divisor med ett faktoriserbart tal [2] . I detta sammanhang, i analogi med pekarmaskinens beräkningsmodell , kan en algoritm som endast använder kopiering av pekare, förflyttning i sekvenser och testning av likhet kallas en pekalgoritm.

Algoritmer

Om indata ges som en beräkningsrutin f , kan problemet med att hitta en cykel trivialt lösas genom att endast göra λ + μ funktionsanrop helt enkelt genom att beräkna en sekvens av x i -värden och använda en datastruktur som en hashtabell för att lagra dessa värden och testa att varje efterföljande värde ännu inte har lagrats. Kapacitetskomplexiteten för denna algoritm är dock proportionell mot λ + μ , och denna komplexitet är onödigt stor. För att använda denna metod för pekaralgoritmen skulle det också krävas ett likhetstest för varje värdepar, vilket resulterar i kvadratisk tid. Forskning inom detta område har alltså två mål: att använda mindre utrymme än denna enkla algoritm, och att hitta en pekaralgoritm som använder färre likhetstester.

Sköldpaddan och haren

Floyds cykelsökningsalgoritm  är en pekaralgoritm som bara använder två pekare som rör sig längs sekvensen med olika hastigheter. Algoritmen kallas också "sköldpaddan och haren"-algoritmen, med en antydan om Aesops fabel "Sköldpaddan och haren" .

Algoritmen är uppkallad efter Robert Floyd , som är krediterad för att ha uppfunnit metoden av Donald Knuth [3] [4] . Algoritmen publicerades dock inte i Floyds tidningar, och detta kan vara ett tillskrivningsfel: Floyd beskriver algoritmer för att lista alla enkla cykler i en riktad graf i en tidning från 1967 [5] , men den artikeln beskriver inte problemet med att hitta en cykla i funktionella grafer som är föremål för övervägande av artikeln. Faktum är att Knuths uttalande, som gjordes 1969, där algoritmen tillskrivs Floyd utan hänvisning, är det första kända omnämnandet av denna algoritm i tryck, och därför kan algoritmen visa sig vara matematisk folklore , som inte tillhör en specifik person [6] .

Huvudidén med algoritmen är att för alla heltal i ≥ μ och k ≥ 0 , x i = x i + kλ , där λ  är cykellängden och μ  är indexet för det första elementet i cykeln. I synnerhet i = kλ ≥ μ om och endast om x i = x 2 i .

Således, för att hitta en upprepningsperiod ν som är en multipel av λ , behöver algoritmen bara kontrollera efter upprepning av värden av detta speciella slag - ett värde är dubbelt så långt från början som det andra.

När perioden ν har hittats återvänder algoritmen till sekvensen från startpunkten för att hitta det första upprepade värdet x μ i sekvensen, med hjälp av det faktum att λ delar ν och därför x μ = x μ + v . Slutligen, när värdet på μ väl är känt, är det lätt att hitta längden λ för den kortaste repetitionscykeln genom att hitta den första positionen μ + λ för vilken x μ + λ = x μ .

Algoritmen använder två pekare i en given sekvens: en (sköldpadda) går igenom x i värden och den andra (hare) går igenom x 2 i värden . I varje steg i algoritmen ökas index i med ett, vilket flyttar sköldpaddan ett element framåt och haren två element, varefter värdena vid dessa punkter jämförs. Det minsta värdet i > 0 för vilket sköldpaddan och haren kommer att peka på samma värde är det önskade värdet ν .

Följande Python -program visar hur en idé kan implementeras.

def floyd ( f , x0 ): # Huvuddelen av algoritmen: hitta upprepning x_i = x_2i. # Haren rör sig dubbelt så snabbt som sköldpaddan, # och avståndet mellan dem ökar med ett från steg till steg. # En dag kommer de att vara inne i cykeln, och då kommer avståndet mellan dem # att vara delbart med λ. sköldpadda = f ( x0 ) # f(x0) är elementet efter x0. hare = f ( f ( x0 )) medan sköldpadda != hare : sköldpadda = f ( sköldpadda ) hare = f ( f ( hare )) # I detta ögonblick divideras sköldpaddans position ν, # som är lika med avståndet mellan sköldpaddan och haren # med perioden λ. Således kommer haren, som rör sig # runt ringen en position i taget, # och sköldpaddan, med start igen från startpunkten x0 och # närmar sig ringen, möts i början av ringen # Hitta positionen μ för mötet . mu = 0 sköldpadda = x0 medan sköldpadda != hare : sköldpadda = f ( sköldpadda ) hare = f ( hare ) # Hare och sköldpadda rör sig i samma hastighet mu += 1 # Hitta längden på den kortaste cykeln med start vid position x_μ # Haren rör sig en position framåt, # medan sköldpaddan står stilla. lam = 1 hare = f ( sköldpadda ) medan sköldpadda != hare : hare = f ( hare ) lam += 1 återvända lam , mu

Den här koden kommer bara åt sekvensen genom att komma ihåg och kopiera pekare, utvärdera funktionen och kontrollera jämställdhet. Algoritmen är alltså en pekaralgoritm. Algoritmen använder O ( λ + μ ) operationer av dessa typer och O (1) minne [7] .

Brents algoritm

Richard Brent har beskrivit en alternativ cykelsökningsalgoritm som, liksom sköldpadda- och harealgoritmen, bara kräver två pekare till sekvensen [8] . Det bygger dock på en annan princip - att hitta den minsta potensen 2 i av talet 2 som är större än både λ och μ .

För i = 0, 1, 2, ... jämför algoritmen x 2 i −1 med värdena i sekvensen upp till nästa potens av två, vilket stoppar processen när en matchning hittas. Algoritmen har två fördelar jämfört med algoritmen för sköldpadda och hare: för det första hittar den korrekt cykellängd λ omedelbart och kräver inte ett andra steg för att bestämma den, och för det andra, vid varje steg, anropas funktionen f endast en gång, och inte tre gånger [9] .

Följande Python -program visar mer detaljerat hur denna teknik fungerar.

def brent ( f , x0 ): # Huvudfas: leta efter en potens av två potens = lam = 1 sköldpadda = x0 hare = f ( x0 ) # f(x0) är elementet/noden efter x0. medan sköldpadda != hare : om makt == lam : # dags att starta en ny tvåkraft? sköldpadda = harkraft * = 2 lam = 0 hare = f ( hare ) lam += 1 # Hitta positionen för den första upprepningen av längden λ mu = 0 sköldpadda = hare = x0 för i i intervallet ( lam ): # range(lam) bildar en lista med värden 0, 1, ... , lam-1 hare = f ( hare ) # avståndet mellan sköldpaddan och haren är nu λ. # Nu rör sig sköldpaddan och haren i samma hastighet tills de möts medan sköldpadda != hare : sköldpadda = f ( sköldpadda ) hare = f ( hare ) mu += 1 återvända lam , mu

Liksom algoritmen för sköldpadda och hare är denna algoritm en pekalgoritm som använder O ( λ + μ ) kontroller och funktionsanrop och O (1) minne . Det är lätt att visa att antalet funktionsanrop aldrig kommer att överstiga antalet anrop i Floyds algoritm.

Brent hävdar att hans algoritm i genomsnitt är cirka 36 % snabbare än Floyds, och att den överträffar Pollards ro-algoritm med cirka 24 %. Han genomförde en analys av mellanvarianten en probabilistisk version av algoritmen, där sekvensen av index som korsas av en långsam pekare inte är en potens av två, utan är en potens av två multiplicerad med en slumpmässig faktor. Även om huvudmålet med hans algoritm var att faktorisera ett tal, diskuterar Brent också tillämpningen av algoritmen för att testa pseudo-slumpgeneratorer [8] .

Dags för minne

Många författare har studerat loop-finding-tekniker som använder mer minne än Floyd- och Brent-metoderna, men som är snabbare. I allmänhet kommer dessa metoder ihåg några tidigare beräknade sekvensvärden och kontrollera om det nya värdet matchar ett av de inlärda. För att göra detta snabbt använder de vanligtvis hash-tabeller eller liknande datastrukturer, och därför är sådana algoritmer inte pekaralgoritmer (i synnerhet kan de vanligtvis inte anpassas till Pollards rho-algoritm). Där dessa metoder skiljer sig är hur de avgör vilka värden som ska komma ihåg. Efter Nivash [10] kommer vi kortfattat att gå igenom dessa tekniker.

Brent [8] har redan beskrivit varianter av sin teknik där indexen för de lagrade sekvensvärdena är andra potenser av R än två. Genom att välja R närmare ett och genom att lagra sekvensvärden med index nära successiva potenser av R , kan cykelsökningsalgoritmen använda antalet funktionsanrop som inte överstiger en godtyckligt liten faktor av det optimala värdet λ + μ [11 ] [12] .

Sedgwick, Szymanski och Yao [13] föreslog en metod som använder M minnesplatser och kräver i värsta fall endast funktionsanrop med någon konstant c som den har visat sig vara optimal för. Tekniken använder den numeriska parametern d , och lagrar i tabellen endast de positioner i sekvensen som är multiplar av d . Tabellen rensas och värdet på d fördubblas om antalet lagrade värden är för stort.

Vissa författare har beskrivit markerade punktmetoder som lagrar funktionsvärden i en tabell baserat på kriterier som använder värden snarare än index (som i Sedgwick et al.-metoden). Till exempel kan modulovärden från något nummer d [14] [15] lagras . Mer enkelt, Nivasch [10] tillskriver Woodroof förslaget att komma ihåg ett slumpmässigt valt tidigare värde genom att göra ett lämpligt slumpmässigt val vid varje steg.

Nivash [10] beskriver en algoritm som inte använder en fast mängd minne, men för vilken den förväntade mängden minne som används (förutsatt att ingångsfunktionen är slumpmässig) beror logaritmiskt på sekvensens längd. Med denna teknik skrivs ett element till tabellen om inget tidigare element har ett lägre värde. Som Nivasch visade kan element i denna teknik placeras på en stack och varje efterföljande värde behöver endast jämföras med elementet överst i stacken. Algoritmen stannar när en upprepning av ett element med ett mindre värde hittas. Om vi ​​använder flera stackar och slumpmässig permutation av värden inom varje stack får vi en hastighetsökning på bekostnad av minnet, liknande de tidigare algoritmerna. Men även enstackversionen av algoritmen är inte en pekalgoritm eftersom den behöver veta vilket av värdena som är mindre.

Varje loop-hittande algoritm som minns högst M - värden från inmatningssekvensen måste göra åtminstone funktionsanrop [16] [17] .

Applikationer

Cykelsökning används i många applikationer.

Att bestämma cykellängden för en pseudo-slumptalsgenerator är ett mått på dess styrka. Denna applikation nämndes av Knuth när han beskrev Floyds metod [3] . Brent [8] beskrev resultatet av att testa den linjära kongruentialgeneratorn . Generatorns period visade sig vara betydligt mindre än vad som annonserades. För mer komplexa generatorer kanske sekvensen av värden där cykeln hittas inte representerar utsignalen från generatorn, utan bara dess interna tillstånd.

Flera talteoretiska algoritmer förlitar sig på cykelfynd, inklusive Pollards ro-algoritm för heltalsfaktorisering [18] och den relaterade kängurualgoritmen för det diskreta logaritmproblemet [ 19] .

I kryptografi kan förmågan att hitta två olika värden x μ−1 och x λ+μ−1 , mappade av någon kryptografisk funktion ƒ till samma värde x μ , indikera svagheten hos ƒ. Till exempel har Quiscatre och Delessaille [15] använt cykelsökningsalgoritmer för att hitta ett meddelande och ett DES- nyckelpar som mappar det meddelandet till samma krypterade värde. Kaliski , Rivest och Sherman [20] använde också cykelsökningsalgoritmer för att attackera DES. Tekniken kan användas för att hitta kollisioner i en kryptografisk hashfunktion [21] .

Att hitta loopar kan vara användbart som ett sätt att upptäcka oändliga loopar i vissa typer av datorprogram [22] .

Periodiska konfigurationer i cellulär automatmodellering kan hittas genom att tillämpa cykelsökningsalgoritmer på en sekvens av automattillstånd [10] .

listformanalys är en teknik för att kontrollera riktigheten av en algoritm som använder dessa strukturer. Om en nod i en lista felaktigt refererar till en tidigare nod i samma lista, bildar strukturen en cykel som kan hittas med hjälp av sådana algoritmer [23] . I Common Lisp upptäcker den variabla S-uttrycksskrivaren loopade liststrukturer*print-circle*och skriver ut dem kompakt.

Teske [12] beskriver en tillämpning inom beräkningsgruppteori för att beräkna strukturen för en Abelisk grupp givet dess uppsättning generatorer. De kryptografiska algoritmerna av Kaliska et al [20] kan också ses som ett försök att avslöja strukturen hos en okänd grupp.

Fitch [24] nämnde kort en applikation för datormodellering av celestial mekanik , som hon tillskriver Kahan . I den här applikationen kan hitta en cykel i fasrummet för ett system av omloppsbanor användas för att avgöra om systemet är periodiskt med modellens noggrannhet [16] .

Anteckningar

  1. ↑ Joux, 2009 , sid. 223.
  2. ↑ 12 Joux , 2009 , sid. 224.
  3. ↑ 1 2 Knuth, 1969 , sid. 7, ex. 6, 7.
  4. ↑ Menezes, van Oorschot, Vanstone, 1996 , sid. 125.
  5. ↑ Floyd, 1967 , sid. 636-644.
  6. ↑ Aumasson, Meier, Phan, Henzen, 2015 , sid. 21, fotnot 8.
  7. ↑ Joux, 2009 , sid. 225-226, avsnitt 7.1.1, Floyds cykelsökningsalgoritm.
  8. ↑ 1 2 3 4 Brent, 1980 , sid. 176-184.
  9. ↑ Joux, 2009 , sid. 226-227, avsnitt 7.1.2, Brents cykelsökningsalgoritm.
  10. ↑ 1 2 3 4 Nivasch, 2004 , sid. 135-140.
  11. ↑ Schnorr, Lenstra, 1984 , sid. 289-311.
  12. ↑ 12 Teske , 1998 , sid. 1637-1663.
  13. ↑ Sedgewick, Szymanski, Yao, 1982 , sid. 376-390.
  14. ↑ van Oorschot, Wiener 1999 , sid. 1-28.
  15. ↑ 1 2 Quisquater, Delescaille, 1989 , sid. 429-434.
  16. ↑ 12 Fich , 1981 , sid. 96-105.
  17. ↑ Allender och Klawe 1985 , sid. 231-237.
  18. ↑ Pollard, 1975 , sid. 331-334.
  19. ↑ Pollard, 1978 , sid. 918-924.
  20. ↑ 1 2 Kaliski, Rivest & Sherman, 1988 , sid. 3-36.
  21. ↑ Joux, 2009 , sid. 242-245, Avsnitt 7.5, Kollisioner i hashfunktioner.
  22. ↑ Van Gelder, 1987 , sid. 23-31.
  23. ↑ Auguston, Hon, 1997 , sid. 37-42.
  24. ↑ Fich, 1981 .

Litteratur

  • Allender, Eric W.; Klawe, Maria M.  Förbättrade nedre gränser för cykeldetektionsproblemet // Teoretisk datavetenskap . - 1985. - Vol. 36, nr. 2–3. - doi : 10.1016/0304-3975(85)90044-1 .  - S. 231-237.
  • Auguston, Michael; Hej, Miu Har. . Påståenden för dynamisk formanalys av listdatastrukturer // AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging . - Linköpings universitet , 1997. - (Linköpings elektroniska artiklar i data- och informationsvetenskap).  - S. 37-42.
  • Aumasson, Jean-Philippe; Meier, Willie; Phan, Raphael C.-W.; Henzen, Luca. . Hash-funktionen BLAKE . - Heidelberg, New York, Dordrecht, London: Springer, 2015. - (Informationssäkerhet och kryptografi). — ISBN 978-3-662-44756-7 .
  • Brent R. P.  En förbättrad Monte Carlo-faktoriseringsalgoritm  // BIT Numerical Mathematics . - 1980. - Vol. 20, nej. 2. - S. 176-184. - doi : 10.1007/BF01933190 .
  • Fich, Faith Ellen. . Nedre gränser för cykeldetekteringsproblemet // Proc. 13:e ACM Symposium on Theory of Computing . - 1981. - doi : 10.1145/800076.802462 .  - S. 96-105.
  • Floyd R. W.  Non-deterministic  Algorithms // Journal of ACM. - 1967. - Vol. 14, nr. 4. - P. 636-644. - doi : 10.1145/321420.321422 .
  • Joux, Antoine. . Algoritmisk kryptoanalys . - CRC Press, 2009. - P. 223. - ISBN 9781420070033 .
  • Kaliski, Burton S. Jr.; Rivest, Ronald L .; Sherman Alan T.  Är Data Encryption Standard en grupp? (Resultat av cykelexperiment på DES) // Journal of Cryptology . - 1988. - Vol. 1, nr. 1. - S. 3-36. - doi : 10.1007/BF00206323 .
  • Knuth, Donald E.  . The Art of Computer Programming, vol. II: Seminumeriska algoritmer. - Addison-Wesley, 1969. - S. 7, övning 6 och 7.
    • Ryska översättning: D. E. Knut  . Konsten att programmera. 3:e uppl. V. 2. Erhållna algoritmer. - Williams, 2005. - ISBN 5-8459-0081-6 .
  • Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. Handbok för tillämpad kryptografi . - CRC Press, 1996. - ISBN 0-8493-8523-7 .
  • Nivasch, Gabriel. Cykeldetektering med hjälp av en stack // Information Processing Letters . - 2004. - Vol. 90, nr. 3. - S. 135-140. - doi : 10.1016/j.ipl.2004.01.016 .
  • Pollard J. M.  En Monte Carlo-metod för faktorisering // BIT. - 1975. - Vol. 15, nr. 3. - s. 331-334. - doi : 10.1007/BF01933667 .
  • Pollard J. M.  Monte Carlo metoder för indexberäkning (mod p ) // Mathematics of Computation . - American Mathematical Society, 1978. - Vol. 32, nr. 143. - P. 918-924. - doi : 10.2307/2006496 . — .
  • Quisquater J.-J., Delescaille J.-P. . Hur lätt är kollisionssökning? Ansökan till DES // Advances in Cryptology - EUROCRYPT '89, Workshop om teorin och tillämpningen av kryptografiska tekniker . - Springer-Verlag, 1989. - P. 429-434. - (Lecture Notes in Computer Science, vol. 434).  (inte tillgänglig länk)
  • Schnorr, Claus P.; Lenstra, Hendrik W.  A Monte Carlo factoring-algoritm med linjär lagring // Mathematics of Computation . - 1984. - Vol. 43, nr. 167. - S. 289-311. - doi : 10.2307/2007414 . — .
  • Sedgewick, Robert; Szymanski, Thomas G.; Yao, Andrew C.-C. Komplexiteten i att hitta cykler i periodiska funktioner // SIAM Journal on Computing . - 1982. - Vol. 11, nr. 2. - P. 376-390. - doi : 10.1137/0211030 .
  • Teske, Edlyn. En utrymmeseffektiv algoritm för beräkning av gruppstruktur // Mathematics of Computation . - 1998. - Vol. 67, nr. 224. - P. 1637-1663. - doi : 10.1090/S0025-5718-98-00968-5 .
  • Van Gelder, Allen. Effektiv loopdetektering i Prolog med sköldpadda-och-hare-tekniken // Journal of Logic Programming. - 1987. - Vol. 4, nr. 1. - S. 23-31. - doi : 10.1016/0743-1066(87)90020-3 .
  • van Oorschot, Paul C.; Wiener, Michael J.  Parallell kollisionssökning med kryptoanalytiska applikationer // Journal of Cryptology . - 1999. - Vol. 12, nr. 1. - S. 1-28. - doi : 10.1007/PL00003816 .

Länkar