PP002F

prime_field_polynomial_normalized_horner_iff

After actual coefficient reduction, the genuine modular execution exists with exactly—and every—canonical residue of the original natural T12 evaluation.

Alpha v34 checked-use · first admitted v31 · independently kernel and Lean verified; not Stable

Current library: Alpha v34, 4,223 checked-use theorems; Stable remains 432. Historical first admissions, original proof editions, and non-admitted aliases are preserved.

Length is representation length, not polynomial degree. Leading zeros and the empty zero polynomial are allowed; the canonical argument guard x<p also applies to the empty case. Evaluation is defined by actual field-operation steps, not an assumed residue invariant. Polynomial division, gcd, irreducibles and general prime-power extension fields remain open; this does not close G091.

Exact theorem in conservative defined notation

∀ p. ∀ b. ∀ c. ∀ d. ∀ e. ∀ t. ∀ l. ∀ n. ∀ r. Prime(p)FpCoefficientReduction(p,b,c,d,e,l)Lt(t,p)Horner(b,c,t,l,n) → (FpHorner(p,d,e,t,l,r)CanonicalModularResidue(p,n,r)) ∧ (CanonicalModularResidue(p,n,r)FpHorner(p,d,e,t,l,r))

Every linked abbreviation expands hygienically to the identical original native formula.

Definition DAG

Actual proof prerequisites

Original expanded first-order statement
forall p b c d e t l n r. (~((p) = 1) /\ forall pfa_factor_left_iff_prime pfa_factor_right_iff_prime. (p) = pfa_factor_left_iff_prime * pfa_factor_right_iff_prime -> pfa_factor_left_iff_prime = 1 \/ pfa_factor_right_iff_prime = 1) -> (forall pfp_index_iff_reduction. (exists pfa_gap_iff_reductionindex. pfa_gap_iff_reductionindex + S (pfp_index_iff_reduction) = (l)) -> exists pfp_source_iff_reduction pfp_residue_iff_reduction. ((((exists ff_h_pfp_iff_reductionsource. ff_h_pfp_iff_reductionsource + S (pfp_source_iff_reduction) = S ((S (pfp_index_iff_reduction)) * c)) /\ exists ff_q_pfp_iff_reductionsource. b = ff_q_pfp_iff_reductionsource * S ((S (pfp_index_iff_reduction)) * c) + (pfp_source_iff_reduction))) /\ (((((exists ff_h_pfp_iff_reductiontarget. ff_h_pfp_iff_reductiontarget + S (pfp_residue_iff_reduction) = S ((S (pfp_index_iff_reduction)) * e)) /\ exists ff_q_pfp_iff_reductiontarget. d = ff_q_pfp_iff_reductiontarget * S ((S (pfp_index_iff_reduction)) * e) + (pfp_residue_iff_reduction))) /\ ((((exists pfa_gap_iff_reductionresiduebound. pfa_gap_iff_reductionresiduebound + S (pfp_residue_iff_reduction) = (p)) /\ ((exists pfa_offset_left_iff_reductionresiduecongruence pfa_offset_right_iff_reductionresiduecongruence. (pfp_source_iff_reduction) + (p) * pfa_offset_left_iff_reductionresiduecongruence = (pfp_residue_iff_reduction) + (p) * pfa_offset_right_iff_reductionresiduecongruence))))))))) -> (exists pfa_gap_iff_base. pfa_gap_iff_base + S (t) = (p)) -> (exists ff_u_ph_pfh_iff_natural ff_v_ph_pfh_iff_natural. ((((exists fs_h_ph_pfh_iff_natural_body_start. fs_h_ph_pfh_iff_natural_body_start + S (0) = S ((S (0)) * ff_v_ph_pfh_iff_natural)) /\ exists fs_q_ph_pfh_iff_natural_body_start. ff_u_ph_pfh_iff_natural = fs_q_ph_pfh_iff_natural_body_start * S ((S (0)) * ff_v_ph_pfh_iff_natural) + (0))) /\ ((((exists fs_h_ph_pfh_iff_natural_body_terminal. fs_h_ph_pfh_iff_natural_body_terminal + S (n) = S ((S (l)) * ff_v_ph_pfh_iff_natural)) /\ exists fs_q_ph_pfh_iff_natural_body_terminal. ff_u_ph_pfh_iff_natural = fs_q_ph_pfh_iff_natural_body_terminal * S ((S (l)) * ff_v_ph_pfh_iff_natural) + (n))) /\ forall ff_i_ph_pfh_iff_natural_body_steps. (exists ph_bound_pfh_iff_natural_body_steps. ph_bound_pfh_iff_natural_body_steps + S ff_i_ph_pfh_iff_natural_body_steps = l) -> exists ff_coefficient_ph_pfh_iff_natural_body_steps ff_previous_ph_pfh_iff_natural_body_steps ff_current_ph_pfh_iff_natural_body_steps. ((((exists fs_h_ph_pfh_iff_natural_body_steps_coefficient. fs_h_ph_pfh_iff_natural_body_steps_coefficient + S (ff_coefficient_ph_pfh_iff_natural_body_steps) = S ((S (ff_i_ph_pfh_iff_natural_body_steps)) * c)) /\ exists fs_q_ph_pfh_iff_natural_body_steps_coefficient. b = fs_q_ph_pfh_iff_natural_body_steps_coefficient * S ((S (ff_i_ph_pfh_iff_natural_body_steps)) * c) + (ff_coefficient_ph_pfh_iff_natural_body_steps))) /\ ((((exists fs_h_ph_pfh_iff_natural_body_steps_before. fs_h_ph_pfh_iff_natural_body_steps_before + S (ff_previous_ph_pfh_iff_natural_body_steps) = S ((S (ff_i_ph_pfh_iff_natural_body_steps)) * ff_v_ph_pfh_iff_natural)) /\ exists fs_q_ph_pfh_iff_natural_body_steps_before. ff_u_ph_pfh_iff_natural = fs_q_ph_pfh_iff_natural_body_steps_before * S ((S (ff_i_ph_pfh_iff_natural_body_steps)) * ff_v_ph_pfh_iff_natural) + (ff_previous_ph_pfh_iff_natural_body_steps))) /\ ((((exists fs_h_ph_pfh_iff_natural_body_steps_after. fs_h_ph_pfh_iff_natural_body_steps_after + S (ff_current_ph_pfh_iff_natural_body_steps) = S ((S (S ff_i_ph_pfh_iff_natural_body_steps)) * ff_v_ph_pfh_iff_natural)) /\ exists fs_q_ph_pfh_iff_natural_body_steps_after. ff_u_ph_pfh_iff_natural = fs_q_ph_pfh_iff_natural_body_steps_after * S ((S (S ff_i_ph_pfh_iff_natural_body_steps)) * ff_v_ph_pfh_iff_natural) + (ff_current_ph_pfh_iff_natural_body_steps))) /\ ff_current_ph_pfh_iff_natural_body_steps = ff_previous_ph_pfh_iff_natural_body_steps * t + ff_coefficient_ph_pfh_iff_natural_body_steps)))))) -> (((exists pfh_trace_code_iff_execution_forward pfh_trace_scale_iff_execution_forward. (((exists pfa_gap_iff_execution_forwardtracebase. pfa_gap_iff_execution_forwardtracebase + S (t) = (p)) /\ (((((exists ff_h_pfp_iff_execution_forwardtraceinitial. ff_h_pfp_iff_execution_forwardtraceinitial + S (0) = S ((S (0)) * pfh_trace_scale_iff_execution_forward)) /\ exists ff_q_pfp_iff_execution_forwardtraceinitial. pfh_trace_code_iff_execution_forward = ff_q_pfp_iff_execution_forwardtraceinitial * S ((S (0)) * pfh_trace_scale_iff_execution_forward) + (0))) /\ (((((exists ff_h_pfp_iff_execution_forwardtraceterminal. ff_h_pfp_iff_execution_forwardtraceterminal + S (r) = S ((S (l)) * pfh_trace_scale_iff_execution_forward)) /\ exists ff_q_pfp_iff_execution_forwardtraceterminal. pfh_trace_code_iff_execution_forward = ff_q_pfp_iff_execution_forwardtraceterminal * S ((S (l)) * pfh_trace_scale_iff_execution_forward) + (r))) /\ ((forall pfh_index_iff_execution_forwardtracesteps. (exists pfa_gap_iff_execution_forwardtracestepsindex. pfa_gap_iff_execution_forwardtracestepsindex + S (pfh_index_iff_execution_forwardtracesteps) = (l)) -> (exists pfh_coefficient_iff_execution_forwardtracestepsstep pfh_before_iff_execution_forwardtracestepsstep pfh_after_iff_execution_forwardtracestepsstep pfh_product_iff_execution_forwardtracestepsstep. ((((exists ff_h_pfp_iff_execution_forwardtracestepsstepcoefficient. ff_h_pfp_iff_execution_forwardtracestepsstepcoefficient + S (pfh_coefficient_iff_execution_forwardtracestepsstep) = S ((S (pfh_index_iff_execution_forwardtracesteps)) * e)) /\ exists ff_q_pfp_iff_execution_forwardtracestepsstepcoefficient. d = ff_q_pfp_iff_execution_forwardtracestepsstepcoefficient * S ((S (pfh_index_iff_execution_forwardtracesteps)) * e) + (pfh_coefficient_iff_execution_forwardtracestepsstep))) /\ (((((exists ff_h_pfp_iff_execution_forwardtracestepsstepbefore. ff_h_pfp_iff_execution_forwardtracestepsstepbefore + S (pfh_before_iff_execution_forwardtracestepsstep) = S ((S (pfh_index_iff_execution_forwardtracesteps)) * pfh_trace_scale_iff_execution_forward)) /\ exists ff_q_pfp_iff_execution_forwardtracestepsstepbefore. pfh_trace_code_iff_execution_forward = ff_q_pfp_iff_execution_forwardtracestepsstepbefore * S ((S (pfh_index_iff_execution_forwardtracesteps)) * pfh_trace_scale_iff_execution_forward) + (pfh_before_iff_execution_forwardtracestepsstep))) /\ (((((exists ff_h_pfp_iff_execution_forwardtracestepsstepafter. ff_h_pfp_iff_execution_forwardtracestepsstepafter + S (pfh_after_iff_execution_forwardtracestepsstep) = S ((S (S (pfh_index_iff_execution_forwardtracesteps))) * pfh_trace_scale_iff_execution_forward)) /\ exists ff_q_pfp_iff_execution_forwardtracestepsstepafter. pfh_trace_code_iff_execution_forward = ff_q_pfp_iff_execution_forwardtracestepsstepafter * S ((S (S (pfh_index_iff_execution_forwardtracesteps))) * pfh_trace_scale_iff_execution_forward) + (pfh_after_iff_execution_forwardtracestepsstep))) /\ (((((exists pfa_gap_iff_execution_forwardtracestepsstepmultiplyleft. pfa_gap_iff_execution_forwardtracestepsstepmultiplyleft + S (pfh_before_iff_execution_forwardtracestepsstep) = (p)) /\ (((exists pfa_gap_iff_execution_forwardtracestepsstepmultiplyright. pfa_gap_iff_execution_forwardtracestepsstepmultiplyright + S (t) = (p)) /\ ((((exists pfa_gap_iff_execution_forwardtracestepsstepmultiplyresultbound. pfa_gap_iff_execution_forwardtracestepsstepmultiplyresultbound + S (pfh_product_iff_execution_forwardtracestepsstep) = (p)) /\ ((exists pfa_offset_left_iff_execution_forwardtracestepsstepmultiplyresultcongruence pfa_offset_right_iff_execution_forwardtracestepsstepmultiplyresultcongruence. ((pfh_before_iff_execution_forwardtracestepsstep) * (t)) + (p) * pfa_offset_left_iff_execution_forwardtracestepsstepmultiplyresultcongruence = (pfh_product_iff_execution_forwardtracestepsstep) + (p) * pfa_offset_right_iff_execution_forwardtracestepsstepmultiplyresultcongruence))))))))) /\ ((((exists pfa_gap_iff_execution_forwardtracestepsstepaddleft. pfa_gap_iff_execution_forwardtracestepsstepaddleft + S (pfh_product_iff_execution_forwardtracestepsstep) = (p)) /\ (((exists pfa_gap_iff_execution_forwardtracestepsstepaddright. pfa_gap_iff_execution_forwardtracestepsstepaddright + S (pfh_coefficient_iff_execution_forwardtracestepsstep) = (p)) /\ ((((exists pfa_gap_iff_execution_forwardtracestepsstepaddresultbound. pfa_gap_iff_execution_forwardtracestepsstepaddresultbound + S (pfh_after_iff_execution_forwardtracestepsstep) = (p)) /\ ((exists pfa_offset_left_iff_execution_forwardtracestepsstepaddresultcongruence pfa_offset_right_iff_execution_forwardtracestepsstepaddresultcongruence. ((pfh_product_iff_execution_forwardtracestepsstep) + (pfh_coefficient_iff_execution_forwardtracestepsstep)) + (p) * pfa_offset_left_iff_execution_forwardtracestepsstepaddresultcongruence = (pfh_after_iff_execution_forwardtracestepsstep) + (p) * pfa_offset_right_iff_execution_forwardtracestepsstepaddresultcongruence))))))))))))))))))))))))))) -> (((exists pfa_gap_iff_residue_forwardbound. pfa_gap_iff_residue_forwardbound + S (r) = (p)) /\ ((exists pfa_offset_left_iff_residue_forwardcongruence pfa_offset_right_iff_residue_forwardcongruence. (n) + (p) * pfa_offset_left_iff_residue_forwardcongruence = (r) + (p) * pfa_offset_right_iff_residue_forwardcongruence))))) /\ (((((exists pfa_gap_iff_residue_backwardbound. pfa_gap_iff_residue_backwardbound + S (r) = (p)) /\ ((exists pfa_offset_left_iff_residue_backwardcongruence pfa_offset_right_iff_residue_backwardcongruence. (n) + (p) * pfa_offset_left_iff_residue_backwardcongruence = (r) + (p) * pfa_offset_right_iff_residue_backwardcongruence)))) -> (exists pfh_trace_code_iff_execution_backward pfh_trace_scale_iff_execution_backward. (((exists pfa_gap_iff_execution_backwardtracebase. pfa_gap_iff_execution_backwardtracebase + S (t) = (p)) /\ (((((exists ff_h_pfp_iff_execution_backwardtraceinitial. ff_h_pfp_iff_execution_backwardtraceinitial + S (0) = S ((S (0)) * pfh_trace_scale_iff_execution_backward)) /\ exists ff_q_pfp_iff_execution_backwardtraceinitial. pfh_trace_code_iff_execution_backward = ff_q_pfp_iff_execution_backwardtraceinitial * S ((S (0)) * pfh_trace_scale_iff_execution_backward) + (0))) /\ (((((exists ff_h_pfp_iff_execution_backwardtraceterminal. ff_h_pfp_iff_execution_backwardtraceterminal + S (r) = S ((S (l)) * pfh_trace_scale_iff_execution_backward)) /\ exists ff_q_pfp_iff_execution_backwardtraceterminal. pfh_trace_code_iff_execution_backward = ff_q_pfp_iff_execution_backwardtraceterminal * S ((S (l)) * pfh_trace_scale_iff_execution_backward) + (r))) /\ ((forall pfh_index_iff_execution_backwardtracesteps. (exists pfa_gap_iff_execution_backwardtracestepsindex. pfa_gap_iff_execution_backwardtracestepsindex + S (pfh_index_iff_execution_backwardtracesteps) = (l)) -> (exists pfh_coefficient_iff_execution_backwardtracestepsstep pfh_before_iff_execution_backwardtracestepsstep pfh_after_iff_execution_backwardtracestepsstep pfh_product_iff_execution_backwardtracestepsstep. ((((exists ff_h_pfp_iff_execution_backwardtracestepsstepcoefficient. ff_h_pfp_iff_execution_backwardtracestepsstepcoefficient + S (pfh_coefficient_iff_execution_backwardtracestepsstep) = S ((S (pfh_index_iff_execution_backwardtracesteps)) * e)) /\ exists ff_q_pfp_iff_execution_backwardtracestepsstepcoefficient. d = ff_q_pfp_iff_execution_backwardtracestepsstepcoefficient * S ((S (pfh_index_iff_execution_backwardtracesteps)) * e) + (pfh_coefficient_iff_execution_backwardtracestepsstep))) /\ (((((exists ff_h_pfp_iff_execution_backwardtracestepsstepbefore. ff_h_pfp_iff_execution_backwardtracestepsstepbefore + S (pfh_before_iff_execution_backwardtracestepsstep) = S ((S (pfh_index_iff_execution_backwardtracesteps)) * pfh_trace_scale_iff_execution_backward)) /\ exists ff_q_pfp_iff_execution_backwardtracestepsstepbefore. pfh_trace_code_iff_execution_backward = ff_q_pfp_iff_execution_backwardtracestepsstepbefore * S ((S (pfh_index_iff_execution_backwardtracesteps)) * pfh_trace_scale_iff_execution_backward) + (pfh_before_iff_execution_backwardtracestepsstep))) /\ (((((exists ff_h_pfp_iff_execution_backwardtracestepsstepafter. ff_h_pfp_iff_execution_backwardtracestepsstepafter + S (pfh_after_iff_execution_backwardtracestepsstep) = S ((S (S (pfh_index_iff_execution_backwardtracesteps))) * pfh_trace_scale_iff_execution_backward)) /\ exists ff_q_pfp_iff_execution_backwardtracestepsstepafter. pfh_trace_code_iff_execution_backward = ff_q_pfp_iff_execution_backwardtracestepsstepafter * S ((S (S (pfh_index_iff_execution_backwardtracesteps))) * pfh_trace_scale_iff_execution_backward) + (pfh_after_iff_execution_backwardtracestepsstep))) /\ (((((exists pfa_gap_iff_execution_backwardtracestepsstepmultiplyleft. pfa_gap_iff_execution_backwardtracestepsstepmultiplyleft + S (pfh_before_iff_execution_backwardtracestepsstep) = (p)) /\ (((exists pfa_gap_iff_execution_backwardtracestepsstepmultiplyright. pfa_gap_iff_execution_backwardtracestepsstepmultiplyright + S (t) = (p)) /\ ((((exists pfa_gap_iff_execution_backwardtracestepsstepmultiplyresultbound. pfa_gap_iff_execution_backwardtracestepsstepmultiplyresultbound + S (pfh_product_iff_execution_backwardtracestepsstep) = (p)) /\ ((exists pfa_offset_left_iff_execution_backwardtracestepsstepmultiplyresultcongruence pfa_offset_right_iff_execution_backwardtracestepsstepmultiplyresultcongruence. ((pfh_before_iff_execution_backwardtracestepsstep) * (t)) + (p) * pfa_offset_left_iff_execution_backwardtracestepsstepmultiplyresultcongruence = (pfh_product_iff_execution_backwardtracestepsstep) + (p) * pfa_offset_right_iff_execution_backwardtracestepsstepmultiplyresultcongruence))))))))) /\ ((((exists pfa_gap_iff_execution_backwardtracestepsstepaddleft. pfa_gap_iff_execution_backwardtracestepsstepaddleft + S (pfh_product_iff_execution_backwardtracestepsstep) = (p)) /\ (((exists pfa_gap_iff_execution_backwardtracestepsstepaddright. pfa_gap_iff_execution_backwardtracestepsstepaddright + S (pfh_coefficient_iff_execution_backwardtracestepsstep) = (p)) /\ ((((exists pfa_gap_iff_execution_backwardtracestepsstepaddresultbound. pfa_gap_iff_execution_backwardtracestepsstepaddresultbound + S (pfh_after_iff_execution_backwardtracestepsstep) = (p)) /\ ((exists pfa_offset_left_iff_execution_backwardtracestepsstepaddresultcongruence pfa_offset_right_iff_execution_backwardtracestepsstepaddresultcongruence. ((pfh_product_iff_execution_backwardtracestepsstep) + (pfh_coefficient_iff_execution_backwardtracestepsstep)) + (p) * pfa_offset_left_iff_execution_backwardtracestepsstepaddresultcongruence = (pfh_after_iff_execution_backwardtracestepsstep) + (p) * pfa_offset_right_iff_execution_backwardtracestepsstepaddresultcongruence))))))))))))))))))))))))))))))

Complete tactic proof in conservative notation

All 74 original proof lines are preserved. Only local proposition formulas are abbreviated; every abbreviation has an exact binder-safe expansion check. The linked exact edition contains the unchanged replay script.

Read the argument

Proof checkpoints

74 script commands · 14 reading checkpoints · 3 local claims

This is a reading aid, not a new proof or a proof-tree certificate. Checkpoint groups are consecutive commands, not inferred branch boundaries. Every step links to the preserved script.

Definition notation is shown below. Open the paired exact edition for the original native formulas. Source pairing is not a new equivalence certificate.

Named ingredients (3)
01Fix variables and assumptionsL1–10

Work with arbitrary variables or the premises of the current implication.

  1. L1
    intro p
  2. L2
    intro b
  3. L3
    intro c
  4. L4
    intro d
  5. L5
    intro e
  6. L6
    intro t
  7. L7
    intro l
  8. L8
    intro n
  9. L9
    intro r
  10. L10
    intro hp
02Fix variables and assumptionsL11–13

Work with arbitrary variables or the premises of the current implication.

  1. L11
    intro hred
  2. L12
    intro ht
  3. L13
    intro hn
03Separate the logical casesL14–14

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L14
    split
04Fix variables and assumptionsL15–15

Work with arbitrary variables or the premises of the current implication.

  1. L15
    intro he
05Use earlier factsL16–25

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L16
    specialize prime_field_polynomial_horner_normalization_residue (p)
  2. L17
    specialize prime_field_polynomial_horner_normalization_residue (b)
  3. L18
    specialize prime_field_polynomial_horner_normalization_residue (c)
  4. L19
    specialize prime_field_polynomial_horner_normalization_residue (d)
  5. L20
    specialize prime_field_polynomial_horner_normalization_residue (e)
  6. L21
    specialize prime_field_polynomial_horner_normalization_residue (t)
  7. L22
    specialize prime_field_polynomial_horner_normalization_residue (l)
  8. L23
    specialize prime_field_polynomial_horner_normalization_residue (n)
  9. L24
    specialize prime_field_polynomial_horner_normalization_residue (r)
  10. L25
    apply prime_field_polynomial_horner_normalization_residue
06Use earlier factsL26–29

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L26
    exact hp
  2. L27
    exact hred
  3. L28
    exact hn
  4. L29
    exact he
07Fix variables and assumptionsL30–30

Work with arbitrary variables or the premises of the current implication.

  1. L30
    intro hr
08Establish heL31–40

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply prime field polynomial horner exists.

  1. L31
    have he : ∃ s. FpHorner(p,d,e,t,l,s)Definitions: FpHorner(p,d,e,t,l,s)Original native command in the exact edition
  2. L32
    specialize prime_field_polynomial_horner_exists (p)
  3. L33
    specialize prime_field_polynomial_horner_exists (d)
  4. L34
    specialize prime_field_polynomial_horner_exists (e)
  5. L35
    specialize prime_field_polynomial_horner_exists (t)
  6. L36
    specialize prime_field_polynomial_horner_exists (l)
  7. L37
    apply prime_field_polynomial_horner_exists
  8. L38
    exact hp
  9. L39
    specialize prime_field_polynomial_normalization_bounded (p)
  10. L40
    specialize prime_field_polynomial_normalization_bounded (b)
09Use earlier factsL41–47

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L41
    specialize prime_field_polynomial_normalization_bounded (c)
  2. L42
    specialize prime_field_polynomial_normalization_bounded (d)
  3. L43
    specialize prime_field_polynomial_normalization_bounded (e)
  4. L44
    specialize prime_field_polynomial_normalization_bounded (l)
  5. L45
    apply prime_field_polynomial_normalization_bounded
  6. L46
    exact hred
  7. L47
    exact ht
10Separate the logical casesL48–48

Follow the explicit conjunction, disjunction, witness, or contradiction step recorded below.

  1. L48
    cases he
11Establish hsL49–58

Establish this local claim before using it. It is not an additional assumption.

  1. L49
    have hs : CanonicalModularResidue(p,n,x)Definitions: CanonicalModularResidue(p,n,x)Original native command in the exact edition
  2. L50
    specialize prime_field_polynomial_horner_normalization_residue (p)
  3. L51
    specialize prime_field_polynomial_horner_normalization_residue (b)
  4. L52
    specialize prime_field_polynomial_horner_normalization_residue (c)
  5. L53
    specialize prime_field_polynomial_horner_normalization_residue (d)
  6. L54
    specialize prime_field_polynomial_horner_normalization_residue (e)
  7. L55
    specialize prime_field_polynomial_horner_normalization_residue (t)
  8. L56
    specialize prime_field_polynomial_horner_normalization_residue (l)
  9. L57
    specialize prime_field_polynomial_horner_normalization_residue (n)
  10. L58
    specialize prime_field_polynomial_horner_normalization_residue (x)
12Use earlier factsL59–63

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L59
    apply prime_field_polynomial_horner_normalization_residue
  2. L60
    exact hp
  3. L61
    exact hred
  4. L62
    exact hn
  5. L63
    exact he_witness
13Establish heqL64–73

Establish this local claim before using it. It is not an additional assumption. The following proof commands apply binary canonical residue functional.

  1. L64
    have heq : x=r
  2. L65
    specialize binary_canonical_residue_functional (p)
  3. L66
    specialize binary_canonical_residue_functional (n)
  4. L67
    specialize binary_canonical_residue_functional (x)
  5. L68
    specialize binary_canonical_residue_functional (r)
  6. L69
    apply binary_canonical_residue_functional
  7. L70
    exact hs
  8. L71
    exact hr
  9. L72
    rewrite heq at he_witness
  10. L73
    rewrite heq at he_witness
14Use earlier factsL74–74

Instantiate or apply named facts and discharge the corresponding proof obligations.

  1. L74
    exact he_witness

Library-wide reading audit

Original defined command ledger · 74 lines
  1. 0001intro p
  2. 0002intro b
  3. 0003intro c
  4. 0004intro d
  5. 0005intro e
  6. 0006intro t
  7. 0007intro l
  8. 0008intro n
  9. 0009intro r
  10. 0010intro hp
  11. 0011intro hred
  12. 0012intro ht
  13. 0013intro hn
  14. 0014split
  15. 0015intro he
  16. 0016specialize prime_field_polynomial_horner_normalization_residue (p)
  17. 0017specialize prime_field_polynomial_horner_normalization_residue (b)
  18. 0018specialize prime_field_polynomial_horner_normalization_residue (c)
  19. 0019specialize prime_field_polynomial_horner_normalization_residue (d)
  20. 0020specialize prime_field_polynomial_horner_normalization_residue (e)
  21. 0021specialize prime_field_polynomial_horner_normalization_residue (t)
  22. 0022specialize prime_field_polynomial_horner_normalization_residue (l)
  23. 0023specialize prime_field_polynomial_horner_normalization_residue (n)
  24. 0024specialize prime_field_polynomial_horner_normalization_residue (r)
  25. 0025apply prime_field_polynomial_horner_normalization_residue
  26. 0026exact hp
  27. 0027exact hred
  28. 0028exact hn
  29. 0029exact he
  30. 0030intro hr
  31. 0031have he : ∃ s. FpHorner(p,d,e,t,l,s)
  32. 0032specialize prime_field_polynomial_horner_exists (p)
  33. 0033specialize prime_field_polynomial_horner_exists (d)
  34. 0034specialize prime_field_polynomial_horner_exists (e)
  35. 0035specialize prime_field_polynomial_horner_exists (t)
  36. 0036specialize prime_field_polynomial_horner_exists (l)
  37. 0037apply prime_field_polynomial_horner_exists
  38. 0038exact hp
  39. 0039specialize prime_field_polynomial_normalization_bounded (p)
  40. 0040specialize prime_field_polynomial_normalization_bounded (b)
  41. 0041specialize prime_field_polynomial_normalization_bounded (c)
  42. 0042specialize prime_field_polynomial_normalization_bounded (d)
  43. 0043specialize prime_field_polynomial_normalization_bounded (e)
  44. 0044specialize prime_field_polynomial_normalization_bounded (l)
  45. 0045apply prime_field_polynomial_normalization_bounded
  46. 0046exact hred
  47. 0047exact ht
  48. 0048cases he
  49. 0049have hs : CanonicalModularResidue(p,n,x)
  50. 0050specialize prime_field_polynomial_horner_normalization_residue (p)
  51. 0051specialize prime_field_polynomial_horner_normalization_residue (b)
  52. 0052specialize prime_field_polynomial_horner_normalization_residue (c)
  53. 0053specialize prime_field_polynomial_horner_normalization_residue (d)
  54. 0054specialize prime_field_polynomial_horner_normalization_residue (e)
  55. 0055specialize prime_field_polynomial_horner_normalization_residue (t)
  56. 0056specialize prime_field_polynomial_horner_normalization_residue (l)
  57. 0057specialize prime_field_polynomial_horner_normalization_residue (n)
  58. 0058specialize prime_field_polynomial_horner_normalization_residue (x)
  59. 0059apply prime_field_polynomial_horner_normalization_residue
  60. 0060exact hp
  61. 0061exact hred
  62. 0062exact hn
  63. 0063exact he_witness
  64. 0064have heq : x=r
  65. 0065specialize binary_canonical_residue_functional (p)
  66. 0066specialize binary_canonical_residue_functional (n)
  67. 0067specialize binary_canonical_residue_functional (x)
  68. 0068specialize binary_canonical_residue_functional (r)
  69. 0069apply binary_canonical_residue_functional
  70. 0070exact hs
  71. 0071exact hr
  72. 0072rewrite heq at he_witness
  73. 0073rewrite heq at he_witness
  74. 0074exact he_witness