CRT transfer.
ProvedSingularModuli.card_range_filter_crtaether-catalogcryptography
CRT transfer. Counting j ∈ [0, pq) by the pair of its residues is the
same as counting in ZMod p × ZMod q.
theorem SingularModuli.card_range_filter_crt{p q : ℕ} [NeZero p] [NeZero q] (hcop : Nat.Coprime p q)
(R : ZMod p → ZMod q → Prop) [∀ a b, Decidable (R a b)] :
((Finset.range (p * q)).filter (fun j : ℕ => R (j : ZMod p) (j : ZMod q))).card
= (Finset.univ.filter (fun z : ZMod p × ZMod q => R z.1 z.2)).card := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Cryptography/SingularModuli/RootCount.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Cryptography/SingularModuli/RootCount.lean import Mathlib import Definitions.Def_Cryptography_SingularModuli_GcdCriterion import Definitions.Def_Cryptography_SingularModuli_RootCount /-! # Singular Moduli Factoring, Step 2: exactly how many evaluation points work Fix a monic `H ∈ ℤ[X]` (think: the Hilbert class polynomial `H_D`, which is monic of degree the class number `h(D)`) and a semiprime `N = p q`. By the criterion of `GcdCriterion.lean`, an evaluation point `j₀` succeeds iff `j₀` is a root of `H` mod exactly one of `p`, `q`. Since that condition only depends on `j₀ mod p` and `j₀ mod q`, the Chinese remainder theorem turns the count of successful `j₀ ∈ [0, N)` into a product count. Main results: * `card_filter_xor_prod` — the pure product-counting identity; * `card_range_filter_crt` — CRT transfer from `[0, pq)` to `ZMod p × ZMod q`; * `successCount_eq` — **the exact success count** `S = r_p (q - r_q) + (p - r_p) r_q`, where `r_m` is the number of roots of `H` mod `m`; * `rootCount_le_natDegree` — `r_m ≤ deg H` (`= h` for a Hilbert class polynomial); * `successCount_le` — hence `S ≤ h (p + q)`: only an `O(h(p+q))`-sized subset of the `pq` residues is useful. The last bound is the combinatorial source of the `√N` barrier proved in `SqrtBarrier.lean`. -/ open SingularModuli open Polynomial Finset FactoringBarriers /-! ## The product count -/ /-! ## Chinese remainder transfer -/
Formal statement
theorem SingularModuli.card_range_filter_crt{p q : ℕ} [NeZero p] [NeZero q] (hcop : Nat.Coprime p q)
(R : ZMod p → ZMod q → Prop) [∀ a b, Decidable (R a b)] :
((Finset.range (p * q)).filter (fun j : ℕ => R (j : ZMod p) (j : ZMod q))).card
= (Finset.univ.filter (fun z : ZMod p × ZMod q => R z.1 z.2)).card := by sorrySource