833 Fundamental

Discrete Logarithm — Baby-Step Giant-Step

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Discrete Logarithm — Baby-Step Giant-Step" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Given g, h, and prime p, the discrete logarithm problem asks: find x such that `g^x ≡ h (mod p)`. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Given g, h, and prime p, the discrete logarithm problem asks: find x such that g^x ≡ h (mod p). This is computationally hard for large p (the Discrete Log Problem, DLP), which is the security foundation of Diffie-Hellman key exchange, ElGamal encryption, DSA signatures, and elliptic curve cryptography. Baby-step Giant-step (BSGS) solves the DLP in O(sqrt(p)) time and O(sqrt(p)) space — much faster than brute force O(p) but still infeasible for cryptographic p (256+ bit). Understanding BSGS is essential for cryptanalysis, CTF competitions, and understanding why large primes are necessary.

🎯 Learning Outcomes

• Understand the meet-in-the-middle decomposition: write x = i*m - j where m = ceil(sqrt(p))

• Baby steps: precompute h * g^j mod p for j = 0..m into a hash map

• Giant steps: for i = 1..m, compute g^(i*m) mod p and look up in the baby-step table

• Recognize the time-space tradeoff: O(sqrt(p)) in both time and memory

• Understand why BSGS only works for small p and why index calculus is needed for large p

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Discrete Logarithm: Baby-Step Giant-Step in OCaml *)

let mulmod a b m =
  Int64.(to_int (rem (mul (of_int a) (of_int b)) (of_int m)))

let rec pow_mod base exp m =
  if exp = 0 then 1 mod m
  else if exp land 1 = 1 then mulmod base (pow_mod base (exp-1) m) m
  else let h = pow_mod base (exp/2) m in mulmod h h m

(* Baby-step giant-step: find x s.t. a^x ≡ b (mod p), 0 ≤ x < p *)
(* Returns Some x or None if no solution *)
let bsgs (a : int) (b : int) (p : int) : int option =
  let m = int_of_float (ceil (sqrt (float_of_int p))) in

  (* Baby steps: table[a^j mod p] = j, for j = 0..m-1 *)
  let table = Hashtbl.create m in
  let aj = ref 1 in
  for j = 0 to m - 1 do
    Hashtbl.replace table !aj j;
    aj := mulmod !aj a p
  done;

  (* Giant steps: check b * (a^m)^i mod p, for i = 1..m *)
  let am = pow_mod a m p in
  let giant = ref b in
  let result = ref None in
  let i = ref 1 in
  while !i <= m && !result = None do
    giant := mulmod !giant am p;
    (match Hashtbl.find_opt table !giant with
     | Some j ->
       let x = !i * m - j in
       if x >= 0 then result := Some x
     | None -> ());
    incr i
  done;
  !result

(* Brute-force for verification *)
let discrete_log_brute (a : int) (b : int) (p : int) : int option =
  let x = ref 0 and cur = ref 1 in
  let found = ref None in
  while !x < p && !found = None do
    if !cur = b then found := Some !x;
    cur := mulmod !cur a p;
    incr x
  done;
  !found

let () =
  let cases = [
    (2, 22, 29);    (* 2^x ≡ 22 (mod 29) *)
    (3, 1, 7);      (* 3^x ≡ 1 (mod 7), x=6 *)
    (5, 3, 23);     (* 5^x ≡ 3 (mod 23) *)
    (2, 3, 7);      (* 2^x ≡ 3 (mod 7) *)
  ] in
  List.iter (fun (a, b, p) ->
    let bsgs_result = bsgs a b p in
    let brute_result = discrete_log_brute a b p in
    Printf.printf "%d^x ≡ %d (mod %d): bsgs=%s, brute=%s\n"
      a b p
      (match bsgs_result with Some x -> string_of_int x | None -> "None")
      (match brute_result with Some x -> string_of_int x | None -> "None")
  ) cases

Key Differences

Aspect	Rust	OCaml
Baby step table	`HashMap<u64, u64>`	`Hashtbl` (int, int)
m computation	`(p as f64).sqrt().ceil()`	`float_of_int \|> sqrt \|> ceil`
Giant step iteration	Multiply by precomputed `gm`	Same approach
No solution	Returns `None`	Returns `None`
Large p support	Limited to u64	`Zarith` for large p
Complexity	O(sqrt(p)) time+space	Same

OCaml Approach

OCaml implements BSGS with Hashtbl.t for baby steps: Hashtbl.add table val j. The giant step loop uses for i = 1 to m do ... done. OCaml's float_of_int |> sqrt |> ceil |> int_of_float computes m. The Hashtbl.find_opt table giant returns int option. OCaml's Zarith handles large moduli beyond 63-bit integers. The baby-step table uses Hashtbl.replace to handle collisions where multiple j values give the same baby step (take the smallest j).

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Discrete Logarithm: Baby-Step Giant-Step in OCaml *)

let mulmod a b m =
  Int64.(to_int (rem (mul (of_int a) (of_int b)) (of_int m)))

let rec pow_mod base exp m =
  if exp = 0 then 1 mod m
  else if exp land 1 = 1 then mulmod base (pow_mod base (exp-1) m) m
  else let h = pow_mod base (exp/2) m in mulmod h h m

(* Baby-step giant-step: find x s.t. a^x ≡ b (mod p), 0 ≤ x < p *)
(* Returns Some x or None if no solution *)
let bsgs (a : int) (b : int) (p : int) : int option =
  let m = int_of_float (ceil (sqrt (float_of_int p))) in

  (* Baby steps: table[a^j mod p] = j, for j = 0..m-1 *)
  let table = Hashtbl.create m in
  let aj = ref 1 in
  for j = 0 to m - 1 do
    Hashtbl.replace table !aj j;
    aj := mulmod !aj a p
  done;

  (* Giant steps: check b * (a^m)^i mod p, for i = 1..m *)
  let am = pow_mod a m p in
  let giant = ref b in
  let result = ref None in
  let i = ref 1 in
  while !i <= m && !result = None do
    giant := mulmod !giant am p;
    (match Hashtbl.find_opt table !giant with
     | Some j ->
       let x = !i * m - j in
       if x >= 0 then result := Some x
     | None -> ());
    incr i
  done;
  !result

(* Brute-force for verification *)
let discrete_log_brute (a : int) (b : int) (p : int) : int option =
  let x = ref 0 and cur = ref 1 in
  let found = ref None in
  while !x < p && !found = None do
    if !cur = b then found := Some !x;
    cur := mulmod !cur a p;
    incr x
  done;
  !found

let () =
  let cases = [
    (2, 22, 29);    (* 2^x ≡ 22 (mod 29) *)
    (3, 1, 7);      (* 3^x ≡ 1 (mod 7), x=6 *)
    (5, 3, 23);     (* 5^x ≡ 3 (mod 23) *)
    (2, 3, 7);      (* 2^x ≡ 3 (mod 7) *)
  ] in
  List.iter (fun (a, b, p) ->
    let bsgs_result = bsgs a b p in
    let brute_result = discrete_log_brute a b p in
    Printf.printf "%d^x ≡ %d (mod %d): bsgs=%s, brute=%s\n"
      a b p
      (match bsgs_result with Some x -> string_of_int x | None -> "None")
      (match brute_result with Some x -> string_of_int x | None -> "None")
  ) cases

Deep Comparison

OCaml vs Rust: Discrete Log Bsgs

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement BSGS for a general group order n (not just prime p) using n instead of p-1 in the result.

Optimize memory by using a sorted array + binary search instead of a HashMap for baby steps.

Implement Pohlig-Hellman which reduces DLP over Z/pZ to smaller DLPs over prime-order subgroups.

Test BSGS on small primes p < 10^6 and verify by computing g^result mod p == h.

Measure the practical limit: what is the largest p for which BSGS completes in under 1 second on your machine?

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust