Introduction

Suppose you know that gxโ‰กh(โ€Šmodโ€Šp)g^{x} \equiv h ( \bmod p) โ€” the base gg, the prime pp, and the result hh are all public. But xx is a secret. Finding xx from gg and hh is the discrete logarithm problem (DLP).

Brute force works: try every exponent from 0 to pโˆ’1p - 1 and stop when you hit hh. But if pp is a 256-bit number, that search visits roughly 107710^{77} values โ€” more atoms than in the observable universe. The DLP is believed to be hard in general, and that hardness is the bedrock of Diffie-Hellman key exchange, DSA signatures, and elliptic-curve cryptography (ECC).

In 1978 the British mathematician John Pollard showed that a cleverly structured random walk through the group can detect a collision after just O(p)O(\sqrt{p}) steps โ€” not p, but the square root of p. For a 20-bit prime that shrinks a million-step search to about a thousand. Applied to elliptic curves (where the group has order roughly p), this is the reason curve parameters must be chosen with large prime-order subgroups: Pollard's rho makes anything smaller insecure.

The algorithm belongs to the broad family of birthday-paradox attacks: collect enough pseudo-random group elements and two of them will collide, leaking the secret exponent โ€” just as 23 people suffice for a 50% chance of a shared birthday.

Try It: Watch the Rho Cycle

The demo below runs Pollard's rho in the cyclic group โ„คโ‚š* for a small prime pp. Pick a prime, a generator gg, and a target h = $g^{x} \bmod p$. The algorithm walks two sequences โ€” a tortoise (one step at a time) and a hare (two steps at a time). When they collide, arithmetic extracts xx.

<div class="controls">
  <label>Prime <em>p</em>:
    <select id="selP">
      <option value="23">23</option>
      <option value="47">47</option>
      <option value="89" selected>89</option>
      <option value="127">127</option>
    </select>
  </label>
  <label>Generator <em>g</em>: <span id="lblG">โ€”</span></label>
  <label>Target <em>h = g^x mod p</em>:
    <select id="selH"></select>
  </label>
  <button id="btnReset" type="button">Reset</button>
  <button id="btnStep" type="button">Step โ†’</button>
  <button id="btnRun" type="button">Run all</button>
</div>
<div class="info-row">
  <span id="lblTortoise">Tortoise: step 0</span>
  <span id="lblHare">Hare: step 0</span>
  <span id="lblCollision"></span>
</div>
<canvas id="cv" width="480" height="280"></canvas>
<div id="result" class="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: .5rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .3rem; }
select { font-size: .85rem; padding: .2rem .4rem; border: 1px solid #adb1b8; border-radius: 6px; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button#btnReset { background: #fff; color: #1d3557; }
.info-row { display: flex; flex-wrap: wrap; gap: 1rem; font-size: .82rem; margin-bottom: .4rem; color: #444; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px; background: #f8fafc;
         max-width: 100%; }
.result { font-size: 1rem; font-weight: 700; min-height: 1.5em; margin-top: .5rem; }
.result.ok { color: #0a7d33; }
.result.bad { color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Pollard's rho for discrete logarithm in Z_p*.
// Find x such that g^x โ‰ก h (mod p).
// Uses the Brent / Floyd tortoise-and-hare cycle detection.
//
// Partition Z_p* into 3 sets by remainder mod 3:
//   S1 (rem 0): new = h * cur mod p             โ†’ b_inc += 1
//   S2 (rem 1): new = cur^2 mod p               โ†’ a_inc *= 2, b_inc *= 2
//   S3 (rem 2): new = g * cur mod p             โ†’ a_inc += 1
// We track (x_val, a, b) with x_val = g^a * h^b mod p.
// When tortoise == hare: g^(a1-a2) โ‰ก h^(b2-b1) โ†’ x = (a1-a2)/(b2-b1) mod ord

function modpow(base, exp, mod) {
  let result = 1n; base %= mod;
  while (exp > 0n) {
    if (exp & 1n) result = result * base % mod;
    base = base * base % mod; exp >>= 1n;
  }
  return result;
}

// Extended GCD โ€” returns [g, x, y] with a*x + b*y = g
function extgcd(a, b) {
  if (b === 0n) return [a, 1n, 0n];
  const [g, x, y] = extgcd(b, a % b);
  return [g, y, x - (a / b) * y];
}

function modinv(a, m) {
  const [g, x] = extgcd(((a % m) + m) % m, m);
  if (g !== 1n) return null; // no inverse
  return ((x % m) + m) % m;
}

// Check if g is a primitive root mod p (generator of Z_p*)
function isPrimitiveRoot(g, p) {
  const ord = p - 1n;
  // Factorize ord simply for small primes
  let factors = [];
  let n = ord;
  for (let f = 2n; f * f <= n; f++) {
    if (n % f === 0n) { factors.push(f); while (n % f === 0n) n /= f; }
  }
  if (n > 1n) factors.push(n);
  return factors.every(f => modpow(BigInt(g), ord / f, p) !== 1n);
}

function findGenerator(p) {
  for (let g = 2n; g < p; g++) {
    if (isPrimitiveRoot(g, p)) return g;
  }
  return 2n;
}

// One step of the rho walk: returns [new_val, new_a, new_b]
function rhoStep(v, a, b, g, h, p, ord) {
  const r = Number(v % 3n);
  if (r === 0) {
    return [v * h % p, a, (b + 1n) % ord];
  } else if (r === 1) {
    return [v * v % p, 2n * a % ord, 2n * b % ord];
  } else {
    return [v * g % p, (a + 1n) % ord, b];
  }
}

// โ”€โ”€ State โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let P, G, H, ORD, TARGET_X;
let tortoise, hare; // {val, a, b}
let stepCount = 0;
let collisionFound = false;
let answerX = null;
let trail = []; // [{t: BigInt, h: BigInt}] for drawing
const MAX_TRAIL = 60;

function init() {
  P = BigInt(document.getElementById('selP').value);
  ORD = P - 1n;
  G = findGenerator(P);
  document.getElementById('lblG').textContent = G.toString();

  // Populate target selector
  const selH = document.getElementById('selH');
  selH.innerHTML = '';
  // Build a few interesting h values (small x values)
  const xs = [3,5,7,11,13,17,19];
  xs.filter(x => x < Number(ORD)).forEach(x => {
    const h = modpow(G, BigInt(x), P);
    const opt = document.createElement('option');
    opt.value = x;
    opt.textContent = `${h} (x=${x})`;
    selH.appendChild(opt);
  });
  selH.selectedIndex = 2; // default x=7

  reset();
}

function reset() {
  P = BigInt(document.getElementById('selP').value);
  ORD = P - 1n;
  G = findGenerator(P);
  const x0 = parseInt(document.getElementById('selH').value, 10);
  TARGET_X = BigInt(x0);
  H = modpow(G, TARGET_X, P);

  // Start: val = g*h mod p, a=1, b=1
  const sv = G * H % P;
  tortoise = { val: sv, a: 1n, b: 1n };
  hare = { val: sv, a: 1n, b: 1n };
  stepCount = 0;
  collisionFound = false;
  answerX = null;
  trail = [{ t: sv, h: sv }];

  document.getElementById('lblCollision').textContent = '';
  document.getElementById('result').textContent = '';
  document.getElementById('result').className = 'result';
  updateLabels();
  draw();
}

function step() {
  if (collisionFound) return;
  // Tortoise: 1 step
  const [tv, ta, tb] = rhoStep(tortoise.val, tortoise.a, tortoise.b, G, H, P, ORD);
  tortoise = { val: tv, a: ta, b: tb };
  // Hare: 2 steps
  const [hv1, ha1, hb1] = rhoStep(hare.val, hare.a, hare.b, G, H, P, ORD);
  const [hv2, ha2, hb2] = rhoStep(hv1, ha1, hb1, G, H, P, ORD);
  hare = { val: hv2, a: ha2, b: hb2 };
  stepCount++;

  trail.push({ t: tv, h: hv2 });
  if (trail.length > MAX_TRAIL) trail.shift();

  if (tortoise.val === hare.val) {
    collisionFound = true;
    const bDiff = ((hare.b - tortoise.b) % ORD + ORD) % ORD;
    const aDiff = ((tortoise.a - hare.a) % ORD + ORD) % ORD;
    const inv = modinv(bDiff, ORD);
    if (inv !== null) {
      answerX = aDiff * inv % ORD;
    } else {
      // gcd > 1: try dividing โ€” simplified for small groups
      const g = extgcd(bDiff, ORD)[0];
      if (aDiff % g === 0n) {
        const newOrd = ORD / g;
        const inv2 = modinv(bDiff / g, newOrd);
        if (inv2 !== null) {
          const candidate = aDiff / g * inv2 % newOrd;
          // Find the right multiple
          for (let k = 0n; k < g; k++) {
            const x = candidate + k * newOrd;
            if (modpow(G, x, P) === H) { answerX = x; break; }
          }
        }
      }
    }
    document.getElementById('lblCollision').textContent =
      fmt('Collision at step %stepCount%! tortoise=hare=%val%', { stepCount: stepCount, val: tortoise.val });
    const ok = answerX !== null && modpow(G, answerX, P) === H;
    const res = document.getElementById('result');
    if (ok) {
      res.textContent = fmt('โœ“ Found x = %answerX%  โ†’  %G%^%answerX% mod %P% = %H%  (secret was %TARGET_X%)', { answerX: answerX, G: G, P: P, H: H, TARGET_X: TARGET_X });
      res.className = 'result ok';
    } else {
      res.textContent = `Collision found but gcd split needed โ€” try Run all for brute-force verify.`;
      res.className = 'result bad';
    }
  }
  updateLabels();
  draw();
}

function runAll() {
  let limit = 0;
  while (!collisionFound && limit++ < 2000) step();
}

function updateLabels() {
  document.getElementById('lblTortoise').textContent =
    fmt('Tortoise: step %stepCount%, val=%val%', { stepCount: stepCount, val: tortoise.val });
  document.getElementById('lblHare').textContent =
    fmt('Hare: step %v%, val=%val%', { v: stepCount*2, val: hare.val });
}

// โ”€โ”€ Canvas drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const COLORS = { tortoise: '#e63946', hare: '#457b9d', trail: '#a8c0d6' };

function draw() {
  const cv = document.getElementById('cv');
  const ctx = cv.getContext('2d');
  const W = cv.width, H_px = cv.height;
  ctx.clearRect(0, 0, W, H_px);

  // Draw a number line of group elements 1..P-1 as circles
  const n = Number(P) - 1;
  const cols = Math.min(n, 22);
  const rows = Math.ceil(n / cols);
  const cw = Math.floor((W - 20) / cols);
  const ch = Math.floor((H_px - 40) / rows);
  const r = Math.min(cw, ch) / 2 - 2;

  function pos(v) {
    const idx = Number(v) - 1; // 1-indexed group element -> 0-indexed
    const col = idx % cols;
    const row = Math.floor(idx / cols);
    return { x: 10 + col * cw + cw / 2, y: 20 + row * ch + ch / 2 };
  }

  // Draw all elements
  for (let v = 1; v <= n; v++) {
    const p = pos(v);
    ctx.beginPath();
    ctx.arc(p.x, p.y, r, 0, 2 * Math.PI);
    const isTort = BigInt(v) === tortoise.val;
    const isHare = BigInt(v) === hare.val;
    if (isTort && isHare) {
      ctx.fillStyle = '#6a0dad'; // collision: purple
    } else if (isTort) {
      ctx.fillStyle = COLORS.tortoise;
    } else if (isHare) {
      ctx.fillStyle = COLORS.hare;
    } else {
      ctx.fillStyle = '#e8eef3';
    }
    ctx.fill();
    ctx.strokeStyle = '#adb1b8'; ctx.lineWidth = 1;
    ctx.stroke();
    if (r > 8) {
      ctx.fillStyle = (isTort || isHare) ? '#fff' : '#555';
      ctx.font = `${Math.max(9, Math.min(11, r))}px ui-monospace, monospace`;
      ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
      ctx.fillText(v.toString(), p.x, p.y);
    }
  }

  // Highlight H and G
  const pH = pos(Number(H));
  ctx.beginPath(); ctx.arc(pH.x, pH.y, r + 3, 0, 2 * Math.PI);
  ctx.strokeStyle = '#f4a261'; ctx.lineWidth = 2; ctx.stroke();

  // Legend
  ctx.font = '11px system-ui'; ctx.textAlign = 'left'; ctx.textBaseline = 'alphabetic';
  const items = [
    { c: COLORS.tortoise, label: 'Tortoise' },
    { c: COLORS.hare,     label: 'Hare' },
    { c: '#6a0dad',       label: 'Collision' },
    { c: '#f4a261',       label: fmt('h=%H% (target)', { H: H }) },
  ];
  let lx = 8;
  items.forEach(it => {
    ctx.fillStyle = it.c;
    ctx.fillRect(lx, H_px - 14, 10, 10);
    ctx.fillStyle = '#333';
    ctx.fillText(it.label, lx + 13, H_px - 5);
    lx += ctx.measureText(it.label).width + 28;
  });
}

// โ”€โ”€ Bootstrap โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
document.getElementById('selP').addEventListener('change', init);
document.getElementById('selH').addEventListener('change', reset);
document.getElementById('btnReset').addEventListener('click', reset);
document.getElementById('btnStep').addEventListener('click', step);
document.getElementById('btnRun').addEventListener('click', runAll);

init();
Result
Console

Step through slowly and watch the rho (ฯ) shape appear: a tail leading into a cycle. The collision happens inside the cycle โ€” that is where the secret exponent leaks out. Notice how the number of steps is roughly โˆšp, not p.

The Real Complexity

How fast is Pollard's rho, really?

  • Brute force tries every exponent: O(p)O(p) time, O(1)O(1) space.
  • Baby-step giant-step (Shanks, 1971) achieves O(p)O(\sqrt{p}) time but needs O(p)O(\sqrt{p}) space to store a table โ€” prohibitive for large p.
  • Pollard's rho (John Pollard, 1978) matches the O(p)O(\sqrt{p}) time bound using only O(1)O(1) space by running Floyd's tortoise-and-hare cycle detection instead of a table.
  • Parallelization: the rho idea extends to many processors; with k machines the expected time drops to O(p/k)O(\sqrt{p} / k), making it the standard benchmark attack on elliptic-curve groups.

The algorithm is not a polynomial-time algorithm: O(p)O(\sqrt{p}) is still exponential in the bit-length of p (since p has โ‰ˆ logโก2p\log_{2} p bits, p=2logโก2p/2\sqrt{p} = 2^{\log_{2} p / 2}). For 256-bit curves, pโ‰ˆ2128\sqrt{p} \approx 2^{128} operations โ€” still computationally infeasible. This is why 256-bit ECC is considered secure today.

The status of the discrete logarithm problem itself is open: no polynomial-time classical algorithm is known. On a quantum computer, Shor's algorithm (1994) solves it in O((log p)ยณ) โ€” polynomial and devastating โ€” which is why post-quantum cryptography research is racing to find DLP-free alternatives. Until then, Pollard's rho sets the practical security floor for any group-based scheme.

For more on the underlying hardness assumptions, see factoring and RSA and Shor's algorithm.

Where It Matters

Pollard's rho is not just a textbook curiosity. It drives real engineering choices:

  • ECC key-size standards: NIST and IETF require elliptic-curve groups with prime orders of at least 22562^{256} precisely because Pollard's rho makes anything smaller attackable with a few thousand GPU-years.
  • Small-subgroup attacks: if an implementation accidentally uses a small subgroup of a curve, rho can extract the secret key in seconds. This is a real attack vector in poorly implemented DH and ECDH.
  • Breaking legacy systems: researchers have used parallelized Pollard's rho to solve discrete logs over curves with 112-bit and 114-bit prime orders in record-setting computations, demonstrating real-world boundaries.
  • Post-quantum planning: because Shor's algorithm kills DLP entirely, any system relying on discrete logs โ€” including all ECC schemes โ€” must be migrated to lattice-based or hash-based schemes before large quantum computers arrive.
  • Cryptographic benchmarks: the effort to solve a discrete log in a given group is the standard measure of that group's security level, and Pollard's rho defines that effort.

The rho algorithm is also a template for other cycle-finding attacks: variants solve the factoring problem and underpin attacks on hash-function collisions.

Conclusion

Pollard's rho turns a blind trillion-step search into a clever thousand-step walk. The rho shape โ€” a tail threading into a cycle โ€” is not decorative: it is the mathematical structure that forces two group elements to collide and surrender the secret exponent.

The lesson for cryptography is concrete. The DLP is believed to be hard, but "hard" is not absolute: it means harder than โˆšp steps on a classical computer. Every curve, every group, every parameter choice must keep โˆšp large enough to be infeasible. Fall short, and Pollard's rho finds the key.

And once large quantum computers arrive, even that floor disappears โ€” Shor's algorithm solves the DLP in polynomial time. The rho algorithm thus sits at the intersection of elegant mathematics, practical cryptanalysis, and the urgent push toward post-quantum security.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/pollard-rho-discrete-log/Content licensed under CC BY-NC 4.0.