Виявлення циклу

В інформатиці виявлення циклу — це алгоритмічна задача пошуку циклу в послідовності ітераційних значень функції.

Для будь-якої функції Шаблон:Mvar, яка відображає скінченну множину Шаблон:Mvar на саму себе, і будь-якого початкового значення Шаблон:Math з Шаблон:Mvar, послідовність ітераційних значень функції

x_{0}, x_{1} = f (x_{0}), x_{2} = f (x_{1}), \dots, x_{i} = f (x_{i - 1}), \dots

зрештою буде двічі використовувати одне й те ж значення, тобто знайдеться пара різних індексів Шаблон:Mvar та Шаблон:Mvar таких, що Шаблон:Math. Як тільки це трапиться, послідовність буде періодично продовжуватися, повторюючи ту саму послідовність значень від Шаблон:Math до Шаблон:Math. Виявлення циклу — це задача пошуку Шаблон:Mvar та Шаблон:Mvar для заданих Шаблон:Mvar та Шаблон:Math.

Відомо кілька алгоритмів швидкого знаходження циклів з незначним використанням пам'яті. Алгоритм черепахи та зайця Роберта У. Флойда переміщує два вказівника з різною швидкістю по послідовності значень, поки обидва не вкажуть на рівні значення. Алгоритм Брента базується на ідеї Шаблон:Не перекладено. Алгоритми Флойда і Брента використовують сталий об'єм пам'яті, а кількість разів обчислення значеннь функції пропорційна відстані від початку послідовності до першого повторення. Кілька інших алгоритмів використовують більший об'єм пам'яті для меншої кількості обчислень значень функції.

Серед застосунків виявлення циклів є перевірка якості генераторів псевдовипадкових чисел та криптографічних хеш-функцій, алгоритмів обчислювальної теорії чисел, виявлення нескінченних циклів у комп'ютерних програмах та періодичних конфігурацій у клітинних автоматах, автоматизований Шаблон:Не перекладено в таких структурах даних, як зв'язаний список, взаємне блокування при обробці транзакцій в СУБД.

Приклад

На малюнку показана функція Шаблон:Mvar, яка відображає множину Шаблон:Math} саму до себе. Якщо починати з Шаблон:Math і послідовно знаходити Шаблон:Mvar, отримаємо послідовність значень функції: Шаблон:Math

Циклом у цій послідовності буде підпослідовність Шаблон:Math.

Визначення

Нехай Шаблон:Mvar — будь-яка скінченна множина, Шаблон:Mvar — будь-яка функція, що відображає Шаблон:Mvar на саму себе, $x_{0}$ — будь-який елемент з Шаблон:Mvar. Для будь-якого $i > 0$ нехай $x_{i} = f (x_{i - 1})$ . Нехай Шаблон:Mvar — найменший індекс, для якого значення Шаблон:Math знову з'являється нескінченно часто в межах послідовності значень Шаблон:Math, а Шаблон:Mvar (довжина петлі) — це найменше натуральне число, що Шаблон:Math. Проблема виявлення циклу — це задача пошуку Шаблон:Mvar і Шаблон:Mvar.^[1]

Цю ж задачу розглянемо с точки зору теорії графів: побудуємо орієнтований граф (у якому кожна вершина має єдине вихідне ребро), якому відповідає граф функції нашої задачі, та вершинами якого є елементи множини Шаблон:Mvar, а ребра якого відображають елемент на відповідне значення функції, як показано на малюнку. Набір вершин доступних від початкової вершини Шаблон:Math утворюють підграф форми, що нагадує грецьку букву rho (Шаблон:Mvar): шлях довжини Шаблон:Mvar від Шаблон:Math до цикла, який складається з Шаблон:Mvar вершин.^[2]

Комп'ютерне представлення

Як правило, Шаблон:Mvar не буде вказано таблицею значень, як це показано на малюнку вище. Швидше за все, алгоритму виявлення циклу може бути наданий доступ або до послідовності значень Шаблон:Math, або до підпрограми для обчислення Шаблон:Mvar. Завдання полягає в тому, щоб знайти Шаблон:Mvar і Шаблон:Mvar, перевіряючи якомога менше значень з послідовності або виконуючи якомога менше викликів підпрограм. Як правило, також важлива просторова складність алгоритму для проблеми виявлення циклу: бажано вирішити цю проблему, використовуючи обсяг пам'яті, значно менший, ніж потрібно для збереження всієї послідовності.

У деяких додатках, і зокрема в ρ-алгоритм Полларда для факторізації цілих чисел, алгоритм має набагато обмежений доступ до Шаблон:Mvar та Шаблон:Mvar. Наприклад, в ρ-алгоритмі Полларда Шаблон:Mvar — це набір цілих чисел за модулем невідомого простого множника числа, що підлягає факторизації, тому навіть розмір Шаблон:Mvar невідомий алгоритму. Щоб дозволити алгоритмам виявлення циклу використовувати такі обмежені знання, вони можуть бути розроблені на основі наступних можливостей. Спочатку передбачається, що алгоритм має у своїй пам'яті об'єкт, що представляє вказівник на початкове значення Шаблон:Math. На будь-якому етапі він може виконати одну з трьох дій: він може скопіювати будь-який вказівник, який він має, на інший об'єкт у пам'яті, він може застосувати Шаблон:Mvar і замінити будь-який з його покажчиків на вказівник на наступний об'єкт у послідовності, або він може застосувати підпрограма для визначення того, чи є два її покажчики рівними значеннями в послідовності. Дія тестування рівності може включати деякі нетривіальні обчислення: наприклад, в ρ-алгоритмі Полларда це реалізується шляхом перевірки того, чи має різниця між двома збереженими значеннями нетривіальний найбільший спільний дільник з числом, яке потрібно врахувати.^[2] У цьому контексті, за аналогією до моделі обчислень Шаблон:Не перекладено, алгоритм, який використовує лише копіювання покажчика, просування в межах послідовності та тести рівності, можна назвати алгоритмом покажчика.

Алгоритми

Якщо вхід подається як підпрограма для обчислення Шаблон:Mvar, задачу виявлення циклу можна тривіально вирішити, використовуючи лише Шаблон:Math, просто обчисливши послідовність значень Шаблон:Math та використовуючи структуру даних, таку як хеш-таблицю для їх зберігання значення та перевірити, чи кожне наступне значення вже збережено. Проте просторова складність цього алгоритму пропорційна Шаблон:Math, надмірно велика. Крім того, для реалізації цього методу як Шаблон:Не перекладено знадобиться застосувати тест рівності до кожної пари значень, що призведе до загального квадратичного часу. Таким чином, дослідження в цій галузі зосереджені на двох цілях: використати менше місця, ніж цей наївний алгоритм, і знайти алгоритми покажчиків, які використовують менше тестів рівності.

Черепаха і заєць Флойда

Алгоритм пошуку циклу Флойда — це алгоритм покажчиків, який використовує лише два покажчики, які рухаються по послідовності з різною швидкістю. Його також називають «алгоритмом черепахи та зайця», натякаючи на байку Езопа про «Черепаху та зайця».

Алгоритм названий на честь Роберта У. Флойда, якому його винахід приписував Дональд Кнут.^[3]^[4] Однак алгоритм не з'являється у опублікованій роботі Флойда, і це може бути хибним віднесенням: Флойд описує алгоритми перерахування всіх простих циклів в орієнтованому графі у роботі 1967 року^[5] але ця робота не описує проблему пошуку циклу у графах функцій, що є темою цієї статті. Насправді, твердження Кнута (1969 року), яке він приписує Флойду без цитування, є першим відомим згадуванням у друкованому вигляді, і, отже, він може належати до Шаблон:Не перекладено і не належати окремій особі.^[6]

Ключове розуміння алгоритму наступне. Якщо існує цикл, то для будь-яких цілих чисел Шаблон:Math і Шаблон:Math, Шаблон:Math, де Шаблон:Mvar — довжина петлі, яку потрібно знайти, а Шаблон:Mvar — індекс першого елемента циклу. Виходячи з цього, тоді можна показати, що Шаблон:Math для деякого Шаблон:Math тоді і тільки тоді, коли Шаблон:Math.

Таким чином, алгоритму потрібно лише перевірити наявність повторюваних значень цієї спеціальної форми, одна вдвічі далі від початку послідовності, ніж інша, щоб знайти період Шаблон:Mvar повторення, кратний Шаблон:Mvar. Як тільки Шаблон:Mvar буде знайдено, алгоритм відновлює послідовність від її початку, щоб знайти перше повторене значення Шаблон:Math у послідовності, використовуючи той факт, що Шаблон:Mvar ділить Шаблон:Mvar і, отже, Шаблон:Math. Нарешті, як тільки значення Шаблон:Mvar стало відомим, тривіально знайти довжину Шаблон:Mvar найкоротшого повторюваного циклу шляхом пошуку першого положення Шаблон:Math для якого Шаблон:Math.

Таким чином, алгоритм утримує два вказівники у даній послідовності: один (черепаха) у точці Шаблон:Math, а інший (заєць) у точці Шаблон:Math. На кожному кроці алгоритму він збільшується Шаблон:Mvar на один, рухаючи черепаху на один крок вперед, а зайця на два кроки вперед у послідовності, а потім порівнює значення послідовності за цими двома вказівниками. Найменше значення Шаблон:Math для якого черепаха та заєць вказують на рівні значення, є бажаним значенням Шаблон:Mvar.

Наступний код Python показує, як ця ідея може бути реалізована як алгоритм.

def floyd(f, x0):
# Основна фаза алгоритму: пошук повторень x_i = x_2i.
   # Заєць рухається вдвічі швидше черепахи та
   # відстань між ними збільшується на 1 на кожному кроці.
   # Врешті -решт вони обидва опиняться всередині циклу, а потім,
   # в певний момент відстань між ними буде
   # ділиться на крапку λ.
  tortoise = f(x0) # f (x0) - елемент/вузол поруч із x0.
   hare = f (f (x0))
  while tortoise != hare:
    tortoise = f(tortoise)
    hare = f(f(hare))
 
  # На цьому місці розташування черепахи ν, що також дорівнює
   # на відстань між зайцем і черепахою ділиться на
   # період λ. Тож зайці рухаються по колу крок за кроком,
   # і черепаха (скинути на x0) рухаються до кола, буде
   # перетинаються на початку кола. Тому що
   # відстань між ними є постійною на 2ν, кратною λ,
   # вони погодяться, як тільки черепаха досягне індексу μ.
   # Знайдіть позицію μ першого повторення.

  mu = 0
  tortoise = x0
  while tortoise != hare:
    tortoise = f(tortoise)
    hare = f(hare)  # Заєць і черепаха рухаються з однаковою швидкістюd
    mu += 1
 
# Знайдіть довжину найкоротшого циклу, починаючи з x_μ
     # Заєць рухається крок за кроком, поки черепаха нерухома.
     # lam збільшується, поки не знайдеться λ.
     
  lam = 1
  hare = f(tortoise)
  while tortoise != hare:
    hare = f(hare)
    lam += 1
 
  return lam, mu

Цей код звертається лише до послідовності шляхом зберігання та копіювання покажчиків, оцінок функцій та тестів рівності; тому він кваліфікується як алгоритм вказівників. Алгоритм використовує Шаблон:Math цих типів та Шаблон:Math простір для зберігання.^[7]

Алгоритм Брента

Шаблон:Не перекладено описав альтернативний алгоритм виявлення циклу, який, як і алгоритм черепахи та зайця, вимагає лише двох вказівників у послідовності.^[8] Однак він базується на іншому принципі: пошук найменшої потужності з двох Шаблон:Math, більшої як за Шаблон:Mvar і за Шаблон:Mvar.

Для Шаблон:Math, алгоритм порівнює Шаблон:Math з кожним наступним значенням послідовності до наступного степеня двох, зупиняючись, коли знаходить відповідність. Він має дві переваги порівняно з алгоритмом черепахи та зайця: він безпосередньо знаходить правильну довжину Шаблон:Mvar циклу, замість того, щоб шукати його на наступному етапі, а його кроки передбачають лише одну оцінку Шаблон:Mvar, а не три.^[9]

Наступний код Python більш детально показує, як працює ця техніка.

def brent(f, x0):
 
  # основний етап: пошук степеня двійки
  power = lam = 1
  tortoise = x0
  hare = f(x0) # f (x0) - елемент/вузол поруч із x0.
  while tortoise != hare:
    if power == lam: # час почати нову степінь двійки?
      tortoise = hare
      power *= 2
      lam = 0
    hare = f(hare)
    lam += 1

 # Знайдіть позицію першого повторення довжини λ
  tortoise = hare = x0
  for i in range(lam):
# range(lam) створює список зі значеннями 0, 1, ..., lam-1
    hare = f(hare)
  # Відстань між зайцем і черепахою тепер λ.

  # Далі заєць і черепаха рухаються з однаковою швидкістю, поки вони не домовляться
  mu = 0
  while tortoise != hare:
    tortoise = f(tortoise)
    hare = f(hare)
    mu += 1
 
  return lam, mu

Як і алгоритм черепахи та зайця, це алгоритм вказівників, який використовує Шаблон:Math та оцінки функцій та Шаблон:Math простір для зберігання. Не важко показати, що кількість оцінок функцій ніколи не може бути вище, ніж для алгоритму Флойда. Брент стверджує, що в середньому його алгоритм пошуку циклу працює приблизно на 36 % швидше, ніж алгоритм Флойда, і що він швидше ρ-алгоритма Полларда приблизно на 24 %. Він також виконує Шаблон:Не перекладено для рандомізованої версії алгоритму, в якому послідовність індексів, відстежена повільнішим із двох покажчиків, — це не повноваження двох самих, а скоріше рандомізоване кратне ступеням двох. Хоча його основне призначення — алгоритми цілочисельної факторизації, Брент також обговорює застосування для тестування генераторів псевдовипадкових чисел.^[8]

Алгоритм Госпера

Алгоритм Шаблон:Не перекладено^[10]^[11] знаходить період $λ$ і нижню $μ_{l}$ і верхню $μ_{u}$ межу вихідної точки першого циклу. Різниця між нижньою та верхньою межею має той самий порядок, що й період, наприклад. $μ_{l} + λ \sim μ_{h}$ .

Головною особливістю алгоритму Госпера є те, що він ніколи не створює резервних копій для переоцінки функції генератора, і є економічним як у просторі, так і в часі. Його можна приблизно охарактеризувати як паралельну версію алгоритму Брента. У той час як алгоритм Брента поступово збільшує розрив між черепахою та зайцем, алгоритм Госпера використовує кілька черепах (збережено кілька попередніх значень), які приблизно експоненціально рознесені. Відповідно до примітки в пункті 132 HAKMEM Шаблон:Webarchive, цей алгоритм буде виявляти повторення до третього входження будь-якого значення, наприклад. цикл повторюватиметься максимум двічі. У цій примітці також зазначено, що її достатньо для зберігання $Θ (\log λ)$ попередні значення; однак, передбачена реалізація^[10] зберігає $Θ (\log (μ + λ))$ цінності. Наприклад: значення функції-це 32-розрядні цілі числа, і апріорі відомо, що друга ітерація циклу закінчується після щонайменше 2³² оцінок функції з початку, тобто. $μ + 2 λ \leq 2^{32}$ . Тоді достатньо зберегти 33 32-розрядні цілі числа.

На $i$ -го оцінювання функції генератора, алгоритм порівнює отримане значення з $O (\log i)$ попередні значення; зауважте це $i$ піднімається принаймні $μ + λ$ і максимум $μ + 2 λ$ . Тому складність цього алгоритму у часі дорівнює $O ((μ + λ) \cdot \log (μ + λ))$ . Так як він зберігається $Θ (\log (μ + λ))$ цінностей, її просторова складність становить $Θ (\log (μ + λ))$ . Це за звичайного припущення, наявного у цій статті, що розмір значень функції постійний. Без цього припущення складність простору така $Ω (\log^{2} (μ + λ))$ оскільки нам принаймні потрібно $μ + λ$ різні значення, а отже, розмір кожного значення $Ω (\log (μ + λ))$ .

Компроміси між часом і простором

Ряд авторів вивчали методи виявлення циклів, які використовують більше пам'яті, ніж методи Флойда та Брента, але виявляють цикли швидше. Загалом ці методи зберігають декілька попередньо обчислених значень послідовності та перевіряють, чи кожне нове значення дорівнює одному з попередньо обчислених значень. Для того, щоб зробити це швидко, вони зазвичай використовують хеш-таблицю або подібну структуру даних для зберігання попередньо обчислених значень, і тому не є алгоритмами покажчиків: зокрема, вони зазвичай не можуть бути застосовані до ρ-алгоритма Полларда. Ці методи відрізняються тим, як вони визначають, які значення зберігати. Слідом за Нівашем^[12] ми коротко оглядаємо ці методи.

Брент^[8] вже описував варіанти його методу, в яких індекси збережених значень послідовностей є степенями числа Шаблон:Mvar відмінними від двох. Вибираючи Шаблон:Mvar як число, близьке до одиниці, і зберігаючи значення послідовностей в індексах, які знаходяться поблизу послідовності послідовних повноважень Шаблон:Mvar, алгоритм виявлення циклу може використовувати ряд оцінок функцій, які знаходяться в межах довільно малого коефіцієнта оптимуму Шаблон:Math.^[13]^[14]
Шаблон:Не перекладено, Шиманьский и Яо^[15] надають метод, який використовує Шаблон:Mvar комірок пам'яті і вимагає лише в найгіршому випадку $(λ + μ) (1 + c M^{- 1 / 2})$ оцінки функцій для деякої сталої Шаблон:Mvar, яку вони показують як оптимальну. Методика передбачає збереження числового параметра Шаблон:Mvar, зберігання в таблиці лише тих позицій у послідовності, кратних Шаблон:Mvar, а також очищення таблиці та подвоєння Шаблон:Mvar коли зберігається занадто багато значень.
Кілька авторів описали методи виділених точок, які зберігають значення функцій у таблиці на основі критерію, що включає значення, а не індекси (як у методі Седжвіка та ін.).^[16]^[17] Простіше кажучи, Ніваш^[12] приписує Д. П. Вудраффу пропозицію зберегти випадкову вибірку раніше побачених значень, зробивши відповідний випадковий вибір на кожному кроці, щоб вибірка залишалася випадковою.
Ніваш^[12] описує алгоритм, який не використовує фіксований обсяг пам'яті, але для якого очікуваний обсяг використовуваної пам'яті (за припущення, що функція введення є випадковою) є логарифмічним по довжині послідовності. Елемент зберігається в таблиці пам'яті за допомогою цієї техніки, коли попередній елемент не має меншого значення. Як показує Ніваш, елементи з цією технікою можна підтримувати за допомогою стека, і кожне наступне значення послідовності потрібно порівнювати лише з верхньою частиною стека. Алгоритм завершується, коли знайдено повторюваний елемент послідовності з найменшим значенням. Запуск одного і того ж алгоритму з кількома стеками, з використанням випадкових перестановок значень для впорядкування значень у кожному стеку, дозволяє знайти компроміс у просторі часу, подібний до попередніх алгоритмів. Однак навіть версія цього алгоритму з одним стеком не є вказівним алгоритмом через порівняння, необхідні для визначення того, яке з двох значень менше.

Будь-який алгоритм виявлення циклу, який зберігає не більше Шаблон:Mvar значень із вхідної послідовності, повинен виконувати принаймні $(λ + μ) (1 + \frac{1}{M - 1})$ оцінки функцій.^[18]^[19]

Застосування

Виявлення циклів має багато застосувань.

Визначення довжини циклу генератора псевдовипадкових чисел є одним із показників його сили. Це додаток, наведене Кнутом при описі методу Флойда.^[3] Брент^[8] описує результати тестування лінійного конгруенціального генератора таким чином; його період виявився значно меншим за рекламований. Для більш складних генераторів послідовність значень, у яких слід знайти цикл, може відображати не вихід генератора, а його внутрішній стан.
Кілька теоретично численних алгоритмів ґрунтуються на виявленні циклу, включаючи ρ-алгоритма Полларда для цілочисельної факторизації^[20] та пов'язаний з ним алгоритм кенгуру для задачі дискретного логарифма.^[21]
У криптографії можливість знайти два різних значення x_μ−-1 і х _λ+μ−-1 відображається з допомогою деяких криптографічного функції ƒ до того ж значення х_μ може вказувати на слабкість в ƒ. Наприклад, Quisquater та Delescaille^[17] застосовують алгоритми виявлення циклу у пошуку повідомлення та пару стандартних ключів шифрування даних, які відображають це повідомлення на одне й те саме зашифроване значення; Каліскі, Рівест та Шерман^[22] також використовують алгоритми виявлення циклу для атаки на DES. Цей метод також може бути використаний для пошуку колізій у криптографічній хеш-функціях.^[23]
Виявлення циклу може бути корисним як спосіб виявлення нескінченних циклів у певних типах комп'ютерних програм.^[24]
Періодичні конфігурації в моделюванні клітинних автоматів можна знайти, застосувавши алгоритми виявлення циклу до послідовності станів автоматів.^[12]
Шаблон:Не перекладено зв'язаних списків — це метод перевірки правильності алгоритму, що використовує ці структури. Якщо вузол у списку неправильно вказує на попередній вузол у цьому ж списку, структура сформує цикл, який може бути виявлений цими алгоритмами.^[25] У мові Common Lisp принтер S-виразів при змінній *print-circle* виявляє зациклені спискові структури і друкує їх компактно.
Шаблон:Нпні^[14] описує застосування в обчислювальній теорії груп: визначення структури абелевої групи з набору її твірних. Криптографічні алгоритми Каліського та ін.^[22] також можна розглядати як спробу зробити висновок про структуру невідомої групи.
Шаблон:Нпні коротко згадує додаток для комп'ютерного моделювання небесної механіки, яке вона приписує Вільяму Кехену. У цьому додатку виявлення циклу у фазовому просторі орбітальної системи може бути використано для визначення того, чи є система періодичною з точністю до моделювання.^[18]
У фрактальній генерації множини Мандельброта використовуються деякі техніки виконання для прискорення генерації зображення. Одна з них називається «перевірка періоду», яка полягає у знаходженні циклів на точковій орбіті. У цій статті описано техніку «перевірки періоду». Ви можете знайти інше пояснення тут Шаблон:Webarchive. Деякі алгоритми виявлення циклу повинні бути реалізовані для реалізації цієї техніки.

Примітки

Шаблон:Примітки

Посилання

Габріель Ніваш, Проблема виявлення циклу та алгоритм стека Шаблон:Webarchive
Черепаха і заєць Шаблон:Webarchive, Портлендське сховище візерунків
Алгоритм виявлення циклу Флойда (Черепаха і заєць)
Алгоритм виявлення циклу Брента (Телепортуюча черепаха)

↑ Шаблон:Citation.
↑ ^2,0 ^2,1 Шаблон:Harvtxt.
↑ ^3,0 ^3,1 Шаблон:TAOCP.v2
↑ Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125 Шаблон:Webarchive, describes this algorithm and others
↑ Шаблон:Citation
↑ The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21 Шаблон:Webarchive, footnote 8
↑ Шаблон:Harvtxt, Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225—226.
↑ ^8,0 ^8,1 ^8,2 ^8,3 Шаблон:Citation.
↑ Шаблон:Harvtxt, Section 7.1.2, Brent's cycle-finding algorithm, pp. 226—227.
↑ ^10,0 ^10,1 Шаблон:Cite web
↑ Шаблон:Cite web
↑ ^12,0 ^12,1 ^12,2 ^12,3 Шаблон:Citation.
↑ Шаблон:Citation.
↑ ^14,0 ^14,1 Шаблон:Citation.
↑ Шаблон:Citation.
↑ Шаблон:Citation.
↑ ^17,0 ^17,1 Шаблон:Citation.
↑ ^18,0 ^18,1 Шаблон:Citation.
↑ Шаблон:Citation.
↑ Шаблон:Citation.
↑ Шаблон:Citation.
↑ ^22,0 ^22,1 Шаблон:Citation.
↑ Шаблон:Harvtxt, Section 7.5, Collisions in hash functions, pp. 242—245.
↑ Шаблон:Citation.
↑ Шаблон:Citation.

[1] Шаблон:Citation.

[j224-2] 2,0 ^2,1 Шаблон:Harvtxt.

[knuth-3] 3,0 ^3,1 Шаблон:TAOCP.v2

[4] Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125 Шаблон:Webarchive, describes this algorithm and others

[5] Шаблон:Citation

[6] The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21 Шаблон:Webarchive, footnote 8

[7] Шаблон:Harvtxt, Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225—226.

[brent-8] 8,0 ^8,1 ^8,2 ^8,3 Шаблон:Citation.

[9] Шаблон:Harvtxt, Section 7.1.2, Brent's cycle-finding algorithm, pp. 226—227.

[gosper-impl-10] 10,0 ^10,1 Шаблон:Cite web

[11] Шаблон:Cite web

[nivasch-12] 12,0 ^12,1 ^12,2 ^12,3 Шаблон:Citation.

[13] Шаблон:Citation.

[teske-14] 14,0 ^14,1 Шаблон:Citation.

[15] Шаблон:Citation.

[16] Шаблон:Citation.

[qd-17] 17,0 ^17,1 Шаблон:Citation.

[fich-18] 18,0 ^18,1 Шаблон:Citation.

[19] Шаблон:Citation.

[20] Шаблон:Citation.

[21] Шаблон:Citation.

[krs-22] 22,0 ^22,1 Шаблон:Citation.

[23] Шаблон:Harvtxt, Section 7.5, Collisions in hash functions, pp. 242—245.

[24] Шаблон:Citation.

[25] Шаблон:Citation.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

Виявлення циклу

Зміст

Приклад

Визначення

Комп'ютерне представлення

Алгоритми

Черепаха і заєць Флойда

Алгоритм Брента

Алгоритм Госпера

Компроміси між часом і простором

Застосування

Примітки

Посилання

Навігаційне меню

Виявлення циклу

Приклад

Визначення

Комп'ютерне представлення

Алгоритми

Черепаха і заєць Флойда

Алгоритм Брента

Алгоритм Госпера

Компроміси між часом і простором

Застосування

Примітки

Посилання

Навігаційне меню

Пошук