III.P22 — CRT Witness Decomposition

Witness space at primorial depth k factors: W(x, Prim(k)) ≅ ∏ W(x, p_i). Each prime contributes independent 1D search. CRT guarantees reconstruction. Product of costs becomes sum of costs.