Algorithm dossier

  • Category: Math
  • Worst-case complexity: O(log n)
  • Approach: Randomised
  • Data structure: No DS
  • First formalised: 1970s

Why this snippet is Miller-Rabin Primality Test

Why Miller-Rabin. A probabilistic primality test based on Fermat's little theorem refined to reject *strong liars*. Factor n-1 = d · 2^s with d odd; then a^d ≡ 1 (mod n) *or* one of a^(d·2^r) ≡ -1 for some 0 ≤ r < s. Probabilistic. A single witness a is wrong with probability ≤ 1/4; running with several random witnesses drives error below 1/4^k. Industry-standard for big prime testing.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.