miller_rabin_composite
ProvedMiller-Rabin composite witnesses: For every odd composite n, at least 3/4 of all a ∈ {2,...,n-1} are Miller-Rabin witnesses. Finding explicit witnesses without GRH and determining the smallest guaranteed witness are open.
Preamble
import Mathlib
Formal statement
import Mathlib
theorem miller_rabin_composite (n : ℕ) (hn : 3 ≤ n) (hodd : ¬ 2 ∣ n)
(hcomp : ¬ Nat.Prime n) :
∃ a : ℕ, 2 ≤ a ∧ a < n ∧
∀ k s : ℕ, n - 1 = 2 ^ s * k →
(a ^ k % n ≠ 1) ∧ ∀ r : Fin s, a ^ (2 ^ r.val * k) % n ≠ n - 1 := by
sorrySource