OAI/Computability/QuantumFactoring/BinaryRoots.lean

GitHub source file

7 declarations, 0 contain sorry, 0 declared as axioms

Bounded binary-root search required by the appendix's perfect-power check. The search uses only comparisons and powers with exponent at most the input bit bound; no unbounded Nat.nthRoot primitive is used by the algorithm.

  1. def OAI.ExactQuantumFactoring.Primality.rootSearch line 14
  2. lemma OAI.ExactQuantumFactoring.Primality.rootSearch_spec line 20
  3. lemma OAI.ExactQuantumFactoring.Primality.rootSearch_eq line 36
  4. def OAI.ExactQuantumFactoring.Primality.boundedRoot line 46
  5. lemma OAI.ExactQuantumFactoring.Primality.boundedRoot_spec line 48
  6. lemma OAI.ExactQuantumFactoring.Primality.boundedRoot_pow_eq line 55
  7. lemma OAI.ExactQuantumFactoring.Primality.perfectPower_exponent_lt line 63