V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Pollard's Rho Factorization

Race two iterates through a modular pseudo-random sequence until a gcd reveals a nontrivial factor.

Core idea

Iterate a pseudo-random polynomial modulo n with tortoise and hare speeds. When the two values collide modulo an unknown factor, the gcd of their difference with n reveals that factor.

Read the visualization

The graph tracks both sequence positions and the gcd at each race step. A later factor-colored view shows why the sequence forms a tail and cycle modulo the hidden divisor.

2526677747428398711848

Begin with a composite integer whose useful factor is too large for short trial division.

1function pollardRho(n: bigint): bigint {
2 if (n % 2n === 0n) return 2n;
3 const f = (x: bigint): bigint => (x * x + 1n) % n; // seed step seed
4 let slow = 2n;
5 let fast = 2n;
6 let d = 1n;
7 while (d === 1n) {
8 slow = f(slow); // tortoise: 1 step
9 fast = f(f(fast)); // hare: 2 step
10 d = gcd(slow > fast ? slow - fast: fast - slow, n); // reveal
11 }
12 return d === n ? retryWithNewC(n): d; // hit factor (hit cycle hit c duplicate hit)
13}
14// done prime done Miller-Rabin -done; done number done Rho done half done recursion, done decompose
n8051( actually = 83 × 97, hide the known factor)
targetfind one nontrivial factor
1 / 7

Complexity and tradeoffs

Time: Expected O(n^1/4). Space: O(1). Random restarts handle unlucky cycles; primality testing separates terminal factors.

Invariant: Every gcd divides n, and a value strictly between one and n is therefore a valid nontrivial factor.

Where it fits

Pollard's Rho is effective for composites with moderately small factors and pairs naturally with Miller-Rabin, recursive splitting, and random restarts.