830 Fundamental

Euler's Totient Function

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Euler's Totient Function" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Euler's totient function phi(n) counts the integers from 1 to n that are coprime to n. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Euler's totient function phi(n) counts the integers from 1 to n that are coprime to n. It is fundamental to RSA key generation: the private key d satisfies e * d ≡ 1 (mod phi(n)) where n = p*q. By Euler's theorem, a^phi(n) ≡ 1 (mod n) for any a coprime to n, generalizing Fermat's little theorem. phi(n) also counts primitive roots, answers "how many fractions in lowest terms have denominator n," and appears in the analysis of the Stern-Brocot tree. For prime p, phi(p) = p-1; for prime power p^k, phi(p^k) = p^k - p^(k-1); these combine multiplicatively for general n.

🎯 Learning Outcomes

• Compute phi(n) from prime factorization: phi(n) = n * product of (1 - 1/p) for each prime factor p

• Implement the sieve-based batch computation of phi(1..n) in O(n log log n)

• Apply Euler's theorem: a^phi(n) ≡ 1 (mod n) for gcd(a,n) = 1

• Use phi for RSA private key derivation: d = e^(-1) mod phi(n)

• Understand multiplicativity: phi(ab) = phi(a)phi(b) when gcd(a,b) = 1

Code Example

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

(* Euler's Totient Function in OCaml *)

(* Single value: φ(n) = n × ∏(1 - 1/p) over distinct prime factors *)
let totient (n : int) : int =
  let result = ref n in
  let n' = ref n in
  let p = ref 2 in
  while !p * !p <= !n' do
    if !n' mod !p = 0 then begin
      (* p is a prime factor — multiply result by (p-1)/p *)
      while !n' mod !p = 0 do n' := !n' / !p done;
      result := !result - !result / !p
    end;
    incr p
  done;
  (* Remaining prime factor > sqrt(n) *)
  if !n' > 1 then
    result := !result - !result / !n';
  !result

(* Totient sieve: compute φ(i) for all i in [0, n] in O(n log log n) *)
let totient_sieve (n : int) : int array =
  let phi = Array.init (n + 1) (fun i -> i) in
  for i = 2 to n do
    (* phi[i] = i means i hasn't been processed as prime factor yet *)
    if phi.(i) = i then begin
      (* i is prime *)
      let j = ref i in
      while !j <= n do
        phi.(!j) <- phi.(!j) - phi.(!j) / i;
        j := !j + i
      done
    end
  done;
  phi

(* Sum of totients: ∑φ(k) for k=1..n = (n*(n+1)/2 + 1)/... — test property *)
(* Property: ∑_{d|n} φ(d) = n *)
let sum_divisor_totients (n : int) : int =
  let sieve = totient_sieve n in
  (* Divisors of n *)
  let total = ref 0 in
  for d = 1 to n do
    if n mod d = 0 then total := !total + sieve.(d)
  done;
  !total

let () =
  let values = [1; 2; 6; 9; 10; 12; 36; 100] in
  List.iter (fun n ->
    Printf.printf "φ(%d) = %d\n" n (totient n)
  ) values;

  Printf.printf "\nTotient sieve up to 12:\n";
  let phi = totient_sieve 12 in
  Array.iteri (fun i v -> if i > 0 then Printf.printf "  φ(%d) = %d\n" i v) phi;

  Printf.printf "\nProperty ∑_{d|n} φ(d) = n:\n";
  List.iter (fun n ->
    Printf.printf "  n=%d: sum = %d (should be %d)\n" n (sum_divisor_totients n) n
  ) [6; 12; 30]

Key Differences

Aspect	Rust	OCaml
Per-n computation	Trial division O(sqrt n)	Same approach
Batch 1..n	Sieve with `Vec<u64>`	`Array.init` + sieve loop
Factor application	`result -= result / d`	`r := !r - !r / d`
Multiplicativity	Explicit in algorithm	Same
Standard library	No built-in	No built-in
RSA integration	Used in key generation tests	Same theoretical role

OCaml Approach

OCaml's euler_totient n mirrors the Rust approach using mutable let r = ref n and let n = ref n. The sieve version initializes phi.(i) = i and iterates: for each i, if phi.(i) = i (i is prime), for each multiple j: phi.(j) <- phi.(j) / i * (i-1). OCaml's Array.init n (fun i -> i) creates the initial array. The product formula phi.(n) = n * fold primes (fun acc p -> acc * (p-1) / p) is idiomatic in functional style.

Full Source

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

(* Euler's Totient Function in OCaml *)

(* Single value: φ(n) = n × ∏(1 - 1/p) over distinct prime factors *)
let totient (n : int) : int =
  let result = ref n in
  let n' = ref n in
  let p = ref 2 in
  while !p * !p <= !n' do
    if !n' mod !p = 0 then begin
      (* p is a prime factor — multiply result by (p-1)/p *)
      while !n' mod !p = 0 do n' := !n' / !p done;
      result := !result - !result / !p
    end;
    incr p
  done;
  (* Remaining prime factor > sqrt(n) *)
  if !n' > 1 then
    result := !result - !result / !n';
  !result

(* Totient sieve: compute φ(i) for all i in [0, n] in O(n log log n) *)
let totient_sieve (n : int) : int array =
  let phi = Array.init (n + 1) (fun i -> i) in
  for i = 2 to n do
    (* phi[i] = i means i hasn't been processed as prime factor yet *)
    if phi.(i) = i then begin
      (* i is prime *)
      let j = ref i in
      while !j <= n do
        phi.(!j) <- phi.(!j) - phi.(!j) / i;
        j := !j + i
      done
    end
  done;
  phi

(* Sum of totients: ∑φ(k) for k=1..n = (n*(n+1)/2 + 1)/... — test property *)
(* Property: ∑_{d|n} φ(d) = n *)
let sum_divisor_totients (n : int) : int =
  let sieve = totient_sieve n in
  (* Divisors of n *)
  let total = ref 0 in
  for d = 1 to n do
    if n mod d = 0 then total := !total + sieve.(d)
  done;
  !total

let () =
  let values = [1; 2; 6; 9; 10; 12; 36; 100] in
  List.iter (fun n ->
    Printf.printf "φ(%d) = %d\n" n (totient n)
  ) values;

  Printf.printf "\nTotient sieve up to 12:\n";
  let phi = totient_sieve 12 in
  Array.iteri (fun i v -> if i > 0 then Printf.printf "  φ(%d) = %d\n" i v) phi;

  Printf.printf "\nProperty ∑_{d|n} φ(d) = n:\n";
  List.iter (fun n ->
    Printf.printf "  n=%d: sum = %d (should be %d)\n" n (sum_divisor_totients n) n
  ) [6; 12; 30]

Deep Comparison

OCaml vs Rust: Euler Totient

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

Compute the sum of phi(k) for k=1..n and verify it equals n*(n+1)/2 for prime n.

Implement the sieve for phi(1..n) in O(n log log n) and use it to answer sum(phi(k), k=1..n) queries.

Verify Euler's theorem: compute a^phi(n) mod n = 1 for several coprime (a,n) pairs.

Use phi to count the number of primitive roots modulo a prime p (answer: phi(p-1)).

Implement RSA key generation: choose primes p,q; compute phi=phi(pq)=(p-1)(q-1); find e, d=e^(-1) mod phi.

Open Source Repos

functional-rust

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

Rust