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

Miller-Rabin Primality Test

Decompose n-1 into an odd part and powers of two, then test modular witnesses for compositeness.

Core idea

For odd n, write n minus one as d times a power of two. A prime must make each witness produce one immediately or reach minus one while repeatedly squaring.

Read the visualization

The decomposition fixes d and the squaring count. Each witness row begins with modular exponentiation, then follows residues until it passes or proves n composite.

a^dsquare ¹square ²square ³
41( true prime)
561( probable prime)

Choose the next witness base for this odd primality candidate.

1function millerRabin(n: number, a: number): boolean {
2 let d = n - 1, s = 0;
3 while (d % 2 === 0) { d /= 2; s++; } // n−1 = 2^s·d
4 let x = powMod(a, d, n); // x = a^d
5 if (x === 1 || x === n - 1) return true;
6 for (let i = 1; i < s; i++) {
7 x = (x * x) % n; // square one step
8 if (x === n - 1) return true; // verdict to −1 → verdict
9 if (x === 1) return false; // nontrivial square root → verdict number
10 }
11 return false; // from done to −1 → done number
12}
basea = 2
1 / 12

Complexity and tradeoffs

Time: O(k log^3 n). Space: O(1). A fixed witness set is deterministic for bounded machine integers; random witnesses give tiny error probability.

Invariant: A witness is accepted only when its residue chain satisfies the strong probable-prime condition required of every prime.

Where it fits

Miller-Rabin is the standard fast primality screen for cryptography and factorization. Fixed witness sets make it deterministic over common 64-bit ranges.