<p>Consider the problem:
Given an array <span class="math-container">$a[0..n]$</span> where <span class="math-container">$n\ge 1$</span> and <span class="math-container">$a[i]\in [n]$</span> for all <span class="math-container">$i=0,\ldots,n$</span> find two indices <span class="math-container">$s\neq t$</span> so that <span class="math-container">$a[s] = a[t]$</span>.</p>

<p>This problem has a <em>stunning</em> solution running in <span class="math-container">$O(n)$</span> time and using 2 words of space only, attributed to Bob Floyd (at least by Knuth). The crux is to see this as a cycle finding problem (even though there is zero mention of a cycle let alone a graph), and employ the so called Tortoise and Hare algorithm (again, by Floyd).</p>

<p>This Tortoise and Hare algorithm was later used by Pollard in his factoring algorithm and somewhat recently extended <a href="https://arxiv.org/abs/1309.3690" rel="noreferrer">here</a> to solve the element distinctness problem using small space.</p>

<p>What are some other uses of this algorithm or extensions of it in TCS?</p>

CC BY-SA 4.0
2019-07-11T23:11:04.413Z
Pollard used for dlog. Do you have references for factoring?
Turbo
CC BY-SA 4.0
2019-07-12T00:01:51.913Z
@Turbo https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
boinkboink
CC BY-SA 4.0
2019-07-17T06:22:10.277Z
Maybe not in TCS, but it can be used to find collisions in Hash Functions with $O(2^{n/2})$ time and just a bit of memory.
Fractalic
<ds.algorithms><soft-question>
Tortoise and hare algorithms
boinkboink
# Tortoise and hare algorithms

(Asked by: username_0 on 2019-07-11)

Consider the problem:
Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$.

This problem has a *stunning* solution running in $O(n)$ time and using 2 words of space only, attributed to Bob Floyd (at least by Knuth). The crux is to see this as a cycle finding problem (even though there is zero mention of a cycle let alone a graph), and employ the so called Tortoise and Hare algorithm (again, by Floyd).

This Tortoise and Hare algorithm was later used by Pollard in his factoring algorithm and somewhat recently extended [here](https://arxiv.org/abs/1309.3690) to solve the element distinctness problem using small space.

What are some other uses of this algorithm or extensions of it in TCS?

**Tags:** ds.algorithms, soft-question
> **Comments:**
> **username_1**: Pollard used for dlog. Do you have references for factoring?  
> **username_0**: @Turbo https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm  
> **username_2**: Maybe not in TCS, but it can be used to find collisions in Hash Functions with $O(2^{n/2})$ time and just a bit of memory.  

---

## 0 answers

