BD0017

binary_modular_execution_bitlength_bound

Alpha v34 independently verified · alpha_closed; checked-use authorized; not Stable

Every complete actual canonical-length square-and-multiply execution has genuine BitCount-measured operation cost at most 3*BitLen(exponent)+2.

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

Exact expanded first-order arithmetic statement

forall n a m l b c r operations. ((((((((n) = 0 /\ (l) = 1) \/ exists ff_exponent_bl_bd_full_run_canonical_length ff_lower_bl_bd_full_run_canonical_length ff_upper_bl_bd_full_run_canonical_length. (((l) = S ff_exponent_bl_bd_full_run_canonical_length) /\ ((exists ff_positive_bl_bd_full_run_canonical_length. ff_positive_bl_bd_full_run_canonical_length + 1 = (n)) /\ ((exists pa_b_bl_bd_full_run_canonical_length_lower pa_c_bl_bd_full_run_canonical_length_lower. ((forall pa_i_bl_bd_full_run_canonical_length_lower_repeat. (exists pa_lt_bl_bd_full_run_canonical_length_lower_repeat_bound. pa_lt_bl_bd_full_run_canonical_length_lower_repeat_bound + S pa_i_bl_bd_full_run_canonical_length_lower_repeat = ff_exponent_bl_bd_full_run_canonical_length) -> (((exists pa_h_bl_bd_full_run_canonical_length_lower_repeat_decoded. pa_h_bl_bd_full_run_canonical_length_lower_repeat_decoded + S (2) = S ((S (pa_i_bl_bd_full_run_canonical_length_lower_repeat)) * pa_c_bl_bd_full_run_canonical_length_lower)) /\ exists pa_q_bl_bd_full_run_canonical_length_lower_repeat_decoded. pa_b_bl_bd_full_run_canonical_length_lower = pa_q_bl_bd_full_run_canonical_length_lower_repeat_decoded * S ((S (pa_i_bl_bd_full_run_canonical_length_lower_repeat)) * pa_c_bl_bd_full_run_canonical_length_lower) + (2)))) /\ (exists pa_u_bl_bd_full_run_canonical_length_lower_product pa_v_bl_bd_full_run_canonical_length_lower_product. ((((exists pa_h_bl_bd_full_run_canonical_length_lower_product_start. pa_h_bl_bd_full_run_canonical_length_lower_product_start + S (1) = S ((S (0)) * pa_v_bl_bd_full_run_canonical_length_lower_product)) /\ exists pa_q_bl_bd_full_run_canonical_length_lower_product_start. pa_u_bl_bd_full_run_canonical_length_lower_product = pa_q_bl_bd_full_run_canonical_length_lower_product_start * S ((S (0)) * pa_v_bl_bd_full_run_canonical_length_lower_product) + (1))) /\ ((((exists pa_h_bl_bd_full_run_canonical_length_lower_product_terminal. pa_h_bl_bd_full_run_canonical_length_lower_product_terminal + S (ff_lower_bl_bd_full_run_canonical_length) = S ((S (ff_exponent_bl_bd_full_run_canonical_length)) * pa_v_bl_bd_full_run_canonical_length_lower_product)) /\ exists pa_q_bl_bd_full_run_canonical_length_lower_product_terminal. pa_u_bl_bd_full_run_canonical_length_lower_product = pa_q_bl_bd_full_run_canonical_length_lower_product_terminal * S ((S (ff_exponent_bl_bd_full_run_canonical_length)) * pa_v_bl_bd_full_run_canonical_length_lower_product) + (ff_lower_bl_bd_full_run_canonical_length))) /\ forall pa_i_bl_bd_full_run_canonical_length_lower_product. (exists pa_lt_bl_bd_full_run_canonical_length_lower_product_bound. pa_lt_bl_bd_full_run_canonical_length_lower_product_bound + S pa_i_bl_bd_full_run_canonical_length_lower_product = ff_exponent_bl_bd_full_run_canonical_length) -> exists pa_p_bl_bd_full_run_canonical_length_lower_product pa_r_bl_bd_full_run_canonical_length_lower_product pa_s_bl_bd_full_run_canonical_length_lower_product. ((((exists pa_h_bl_bd_full_run_canonical_length_lower_product_factor. pa_h_bl_bd_full_run_canonical_length_lower_product_factor + S (pa_p_bl_bd_full_run_canonical_length_lower_product) = S ((S (pa_i_bl_bd_full_run_canonical_length_lower_product)) * pa_c_bl_bd_full_run_canonical_length_lower)) /\ exists pa_q_bl_bd_full_run_canonical_length_lower_product_factor. pa_b_bl_bd_full_run_canonical_length_lower = pa_q_bl_bd_full_run_canonical_length_lower_product_factor * S ((S (pa_i_bl_bd_full_run_canonical_length_lower_product)) * pa_c_bl_bd_full_run_canonical_length_lower) + (pa_p_bl_bd_full_run_canonical_length_lower_product))) /\ ((((exists pa_h_bl_bd_full_run_canonical_length_lower_product_partial. pa_h_bl_bd_full_run_canonical_length_lower_product_partial + S (pa_r_bl_bd_full_run_canonical_length_lower_product) = S ((S (pa_i_bl_bd_full_run_canonical_length_lower_product)) * pa_v_bl_bd_full_run_canonical_length_lower_product)) /\ exists pa_q_bl_bd_full_run_canonical_length_lower_product_partial. pa_u_bl_bd_full_run_canonical_length_lower_product = pa_q_bl_bd_full_run_canonical_length_lower_product_partial * S ((S (pa_i_bl_bd_full_run_canonical_length_lower_product)) * pa_v_bl_bd_full_run_canonical_length_lower_product) + (pa_r_bl_bd_full_run_canonical_length_lower_product))) /\ ((((exists pa_h_bl_bd_full_run_canonical_length_lower_product_successor. pa_h_bl_bd_full_run_canonical_length_lower_product_successor + S (pa_s_bl_bd_full_run_canonical_length_lower_product) = S ((S (S pa_i_bl_bd_full_run_canonical_length_lower_product)) * pa_v_bl_bd_full_run_canonical_length_lower_product)) /\ exists pa_q_bl_bd_full_run_canonical_length_lower_product_successor. pa_u_bl_bd_full_run_canonical_length_lower_product = pa_q_bl_bd_full_run_canonical_length_lower_product_successor * S ((S (S pa_i_bl_bd_full_run_canonical_length_lower_product)) * pa_v_bl_bd_full_run_canonical_length_lower_product) + (pa_s_bl_bd_full_run_canonical_length_lower_product))) /\ pa_s_bl_bd_full_run_canonical_length_lower_product = pa_r_bl_bd_full_run_canonical_length_lower_product * pa_p_bl_bd_full_run_canonical_length_lower_product)))))))) /\ ((exists pa_b_bl_bd_full_run_canonical_length_upper pa_c_bl_bd_full_run_canonical_length_upper. ((forall pa_i_bl_bd_full_run_canonical_length_upper_repeat. (exists pa_lt_bl_bd_full_run_canonical_length_upper_repeat_bound. pa_lt_bl_bd_full_run_canonical_length_upper_repeat_bound + S pa_i_bl_bd_full_run_canonical_length_upper_repeat = l) -> (((exists pa_h_bl_bd_full_run_canonical_length_upper_repeat_decoded. pa_h_bl_bd_full_run_canonical_length_upper_repeat_decoded + S (2) = S ((S (pa_i_bl_bd_full_run_canonical_length_upper_repeat)) * pa_c_bl_bd_full_run_canonical_length_upper)) /\ exists pa_q_bl_bd_full_run_canonical_length_upper_repeat_decoded. pa_b_bl_bd_full_run_canonical_length_upper = pa_q_bl_bd_full_run_canonical_length_upper_repeat_decoded * S ((S (pa_i_bl_bd_full_run_canonical_length_upper_repeat)) * pa_c_bl_bd_full_run_canonical_length_upper) + (2)))) /\ (exists pa_u_bl_bd_full_run_canonical_length_upper_product pa_v_bl_bd_full_run_canonical_length_upper_product. ((((exists pa_h_bl_bd_full_run_canonical_length_upper_product_start. pa_h_bl_bd_full_run_canonical_length_upper_product_start + S (1) = S ((S (0)) * pa_v_bl_bd_full_run_canonical_length_upper_product)) /\ exists pa_q_bl_bd_full_run_canonical_length_upper_product_start. pa_u_bl_bd_full_run_canonical_length_upper_product = pa_q_bl_bd_full_run_canonical_length_upper_product_start * S ((S (0)) * pa_v_bl_bd_full_run_canonical_length_upper_product) + (1))) /\ ((((exists pa_h_bl_bd_full_run_canonical_length_upper_product_terminal. pa_h_bl_bd_full_run_canonical_length_upper_product_terminal + S (ff_upper_bl_bd_full_run_canonical_length) = S ((S (l)) * pa_v_bl_bd_full_run_canonical_length_upper_product)) /\ exists pa_q_bl_bd_full_run_canonical_length_upper_product_terminal. pa_u_bl_bd_full_run_canonical_length_upper_product = pa_q_bl_bd_full_run_canonical_length_upper_product_terminal * S ((S (l)) * pa_v_bl_bd_full_run_canonical_length_upper_product) + (ff_upper_bl_bd_full_run_canonical_length))) /\ forall pa_i_bl_bd_full_run_canonical_length_upper_product. (exists pa_lt_bl_bd_full_run_canonical_length_upper_product_bound. pa_lt_bl_bd_full_run_canonical_length_upper_product_bound + S pa_i_bl_bd_full_run_canonical_length_upper_product = l) -> exists pa_p_bl_bd_full_run_canonical_length_upper_product pa_r_bl_bd_full_run_canonical_length_upper_product pa_s_bl_bd_full_run_canonical_length_upper_product. ((((exists pa_h_bl_bd_full_run_canonical_length_upper_product_factor. pa_h_bl_bd_full_run_canonical_length_upper_product_factor + S (pa_p_bl_bd_full_run_canonical_length_upper_product) = S ((S (pa_i_bl_bd_full_run_canonical_length_upper_product)) * pa_c_bl_bd_full_run_canonical_length_upper)) /\ exists pa_q_bl_bd_full_run_canonical_length_upper_product_factor. pa_b_bl_bd_full_run_canonical_length_upper = pa_q_bl_bd_full_run_canonical_length_upper_product_factor * S ((S (pa_i_bl_bd_full_run_canonical_length_upper_product)) * pa_c_bl_bd_full_run_canonical_length_upper) + (pa_p_bl_bd_full_run_canonical_length_upper_product))) /\ ((((exists pa_h_bl_bd_full_run_canonical_length_upper_product_partial. pa_h_bl_bd_full_run_canonical_length_upper_product_partial + S (pa_r_bl_bd_full_run_canonical_length_upper_product) = S ((S (pa_i_bl_bd_full_run_canonical_length_upper_product)) * pa_v_bl_bd_full_run_canonical_length_upper_product)) /\ exists pa_q_bl_bd_full_run_canonical_length_upper_product_partial. pa_u_bl_bd_full_run_canonical_length_upper_product = pa_q_bl_bd_full_run_canonical_length_upper_product_partial * S ((S (pa_i_bl_bd_full_run_canonical_length_upper_product)) * pa_v_bl_bd_full_run_canonical_length_upper_product) + (pa_r_bl_bd_full_run_canonical_length_upper_product))) /\ ((((exists pa_h_bl_bd_full_run_canonical_length_upper_product_successor. pa_h_bl_bd_full_run_canonical_length_upper_product_successor + S (pa_s_bl_bd_full_run_canonical_length_upper_product) = S ((S (S pa_i_bl_bd_full_run_canonical_length_upper_product)) * pa_v_bl_bd_full_run_canonical_length_upper_product)) /\ exists pa_q_bl_bd_full_run_canonical_length_upper_product_successor. pa_u_bl_bd_full_run_canonical_length_upper_product = pa_q_bl_bd_full_run_canonical_length_upper_product_successor * S ((S (S pa_i_bl_bd_full_run_canonical_length_upper_product)) * pa_v_bl_bd_full_run_canonical_length_upper_product) + (pa_s_bl_bd_full_run_canonical_length_upper_product))) /\ pa_s_bl_bd_full_run_canonical_length_upper_product = pa_r_bl_bd_full_run_canonical_length_upper_product * pa_p_bl_bd_full_run_canonical_length_upper_product)))))))) /\ ((exists ff_lower_gap_bl_bd_full_run_canonical_length. ff_lower_gap_bl_bd_full_run_canonical_length + (ff_lower_bl_bd_full_run_canonical_length) = (n)) /\ (exists ff_upper_gap_bl_bd_full_run_canonical_length. ff_upper_gap_bl_bd_full_run_canonical_length + S (n) = (ff_upper_bl_bd_full_run_canonical_length))))))))) /\ (((forall ff_index_be_bd_full_run_canonical_code_digits ff_digit_be_bd_full_run_canonical_code_digits. (exists ff_lt_be_bd_full_run_canonical_code_digits_bound. ff_lt_be_bd_full_run_canonical_code_digits_bound + S ff_index_be_bd_full_run_canonical_code_digits = l) -> (((exists ff_h_be_bd_full_run_canonical_code_digits_digit. ff_h_be_bd_full_run_canonical_code_digits_digit + S (ff_digit_be_bd_full_run_canonical_code_digits) = S ((S (ff_index_be_bd_full_run_canonical_code_digits)) * c)) /\ exists ff_q_be_bd_full_run_canonical_code_digits_digit. b = ff_q_be_bd_full_run_canonical_code_digits_digit * S ((S (ff_index_be_bd_full_run_canonical_code_digits)) * c) + (ff_digit_be_bd_full_run_canonical_code_digits))) -> (ff_digit_be_bd_full_run_canonical_code_digits = 0 \/ ff_digit_be_bd_full_run_canonical_code_digits = 1)) /\ (exists ff_u_ph_bd_full_run_canonical_code_horner ff_v_ph_bd_full_run_canonical_code_horner. ((((exists fs_h_ph_bd_full_run_canonical_code_horner_body_start. fs_h_ph_bd_full_run_canonical_code_horner_body_start + S (0) = S ((S (0)) * ff_v_ph_bd_full_run_canonical_code_horner)) /\ exists fs_q_ph_bd_full_run_canonical_code_horner_body_start. ff_u_ph_bd_full_run_canonical_code_horner = fs_q_ph_bd_full_run_canonical_code_horner_body_start * S ((S (0)) * ff_v_ph_bd_full_run_canonical_code_horner) + (0))) /\ ((((exists fs_h_ph_bd_full_run_canonical_code_horner_body_terminal. fs_h_ph_bd_full_run_canonical_code_horner_body_terminal + S (n) = S ((S (l)) * ff_v_ph_bd_full_run_canonical_code_horner)) /\ exists fs_q_ph_bd_full_run_canonical_code_horner_body_terminal. ff_u_ph_bd_full_run_canonical_code_horner = fs_q_ph_bd_full_run_canonical_code_horner_body_terminal * S ((S (l)) * ff_v_ph_bd_full_run_canonical_code_horner) + (n))) /\ forall ff_i_ph_bd_full_run_canonical_code_horner_body_steps. (exists ph_bound_bd_full_run_canonical_code_horner_body_steps. ph_bound_bd_full_run_canonical_code_horner_body_steps + S ff_i_ph_bd_full_run_canonical_code_horner_body_steps = l) -> exists ff_coefficient_ph_bd_full_run_canonical_code_horner_body_steps ff_previous_ph_bd_full_run_canonical_code_horner_body_steps ff_current_ph_bd_full_run_canonical_code_horner_body_steps. ((((exists fs_h_ph_bd_full_run_canonical_code_horner_body_steps_coefficient. fs_h_ph_bd_full_run_canonical_code_horner_body_steps_coefficient + S (ff_coefficient_ph_bd_full_run_canonical_code_horner_body_steps) = S ((S (ff_i_ph_bd_full_run_canonical_code_horner_body_steps)) * c)) /\ exists fs_q_ph_bd_full_run_canonical_code_horner_body_steps_coefficient. b = fs_q_ph_bd_full_run_canonical_code_horner_body_steps_coefficient * S ((S (ff_i_ph_bd_full_run_canonical_code_horner_body_steps)) * c) + (ff_coefficient_ph_bd_full_run_canonical_code_horner_body_steps))) /\ ((((exists fs_h_ph_bd_full_run_canonical_code_horner_body_steps_before. fs_h_ph_bd_full_run_canonical_code_horner_body_steps_before + S (ff_previous_ph_bd_full_run_canonical_code_horner_body_steps) = S ((S (ff_i_ph_bd_full_run_canonical_code_horner_body_steps)) * ff_v_ph_bd_full_run_canonical_code_horner)) /\ exists fs_q_ph_bd_full_run_canonical_code_horner_body_steps_before. ff_u_ph_bd_full_run_canonical_code_horner = fs_q_ph_bd_full_run_canonical_code_horner_body_steps_before * S ((S (ff_i_ph_bd_full_run_canonical_code_horner_body_steps)) * ff_v_ph_bd_full_run_canonical_code_horner) + (ff_previous_ph_bd_full_run_canonical_code_horner_body_steps))) /\ ((((exists fs_h_ph_bd_full_run_canonical_code_horner_body_steps_after. fs_h_ph_bd_full_run_canonical_code_horner_body_steps_after + S (ff_current_ph_bd_full_run_canonical_code_horner_body_steps) = S ((S (S ff_i_ph_bd_full_run_canonical_code_horner_body_steps)) * ff_v_ph_bd_full_run_canonical_code_horner)) /\ exists fs_q_ph_bd_full_run_canonical_code_horner_body_steps_after. ff_u_ph_bd_full_run_canonical_code_horner = fs_q_ph_bd_full_run_canonical_code_horner_body_steps_after * S ((S (S ff_i_ph_bd_full_run_canonical_code_horner_body_steps)) * ff_v_ph_bd_full_run_canonical_code_horner) + (ff_current_ph_bd_full_run_canonical_code_horner_body_steps))) /\ ff_current_ph_bd_full_run_canonical_code_horner_body_steps = ff_previous_ph_bd_full_run_canonical_code_horner_body_steps * 2 + ff_coefficient_ph_bd_full_run_canonical_code_horner_body_steps)))))))))) /\ ((exists ff_trace_code_be_bd_full_run_execution ff_trace_scale_be_bd_full_run_execution. ((((((exists ff_h_be_bd_full_run_execution_trace_start. ff_h_be_bd_full_run_execution_trace_start + S (1) = S ((S (0)) * ff_trace_scale_be_bd_full_run_execution)) /\ exists ff_q_be_bd_full_run_execution_trace_start. ff_trace_code_be_bd_full_run_execution = ff_q_be_bd_full_run_execution_trace_start * S ((S (0)) * ff_trace_scale_be_bd_full_run_execution) + (1))) /\ forall ff_index_be_bd_full_run_execution_trace. (exists ff_lt_be_bd_full_run_execution_trace_bound. ff_lt_be_bd_full_run_execution_trace_bound + S ff_index_be_bd_full_run_execution_trace = l) -> exists ff_digit_be_bd_full_run_execution_trace ff_previous_be_bd_full_run_execution_trace ff_current_be_bd_full_run_execution_trace. ((((exists ff_h_be_bd_full_run_execution_trace_source. ff_h_be_bd_full_run_execution_trace_source + S (ff_digit_be_bd_full_run_execution_trace) = S ((S (ff_index_be_bd_full_run_execution_trace)) * c)) /\ exists ff_q_be_bd_full_run_execution_trace_source. b = ff_q_be_bd_full_run_execution_trace_source * S ((S (ff_index_be_bd_full_run_execution_trace)) * c) + (ff_digit_be_bd_full_run_execution_trace))) /\ ((((exists ff_h_be_bd_full_run_execution_trace_before. ff_h_be_bd_full_run_execution_trace_before + S (ff_previous_be_bd_full_run_execution_trace) = S ((S (ff_index_be_bd_full_run_execution_trace)) * ff_trace_scale_be_bd_full_run_execution)) /\ exists ff_q_be_bd_full_run_execution_trace_before. ff_trace_code_be_bd_full_run_execution = ff_q_be_bd_full_run_execution_trace_before * S ((S (ff_index_be_bd_full_run_execution_trace)) * ff_trace_scale_be_bd_full_run_execution) + (ff_previous_be_bd_full_run_execution_trace))) /\ ((((exists ff_h_be_bd_full_run_execution_trace_after. ff_h_be_bd_full_run_execution_trace_after + S (ff_current_be_bd_full_run_execution_trace) = S ((S (S ff_index_be_bd_full_run_execution_trace)) * ff_trace_scale_be_bd_full_run_execution)) /\ exists ff_q_be_bd_full_run_execution_trace_after. ff_trace_code_be_bd_full_run_execution = ff_q_be_bd_full_run_execution_trace_after * S ((S (S ff_index_be_bd_full_run_execution_trace)) * ff_trace_scale_be_bd_full_run_execution) + (ff_current_be_bd_full_run_execution_trace))) /\ ((((ff_digit_be_bd_full_run_execution_trace = 0) /\ (((exists ff_gap_binary_be_bd_full_run_execution_trace_transition_square. ff_gap_binary_be_bd_full_run_execution_trace_transition_square + S (ff_current_be_bd_full_run_execution_trace) = m) /\ (exists ff_left_binary_be_bd_full_run_execution_trace_transition_square_congruence ff_right_binary_be_bd_full_run_execution_trace_transition_square_congruence. (ff_previous_be_bd_full_run_execution_trace * ff_previous_be_bd_full_run_execution_trace) + m * ff_left_binary_be_bd_full_run_execution_trace_transition_square_congruence = (ff_current_be_bd_full_run_execution_trace) + m * ff_right_binary_be_bd_full_run_execution_trace_transition_square_congruence)))) \/ ((ff_digit_be_bd_full_run_execution_trace = 1) /\ (((exists ff_gap_binary_be_bd_full_run_execution_trace_transition_multiply. ff_gap_binary_be_bd_full_run_execution_trace_transition_multiply + S (ff_current_be_bd_full_run_execution_trace) = m) /\ (exists ff_left_binary_be_bd_full_run_execution_trace_transition_multiply_congruence ff_right_binary_be_bd_full_run_execution_trace_transition_multiply_congruence. ((ff_previous_be_bd_full_run_execution_trace * ff_previous_be_bd_full_run_execution_trace) * a) + m * ff_left_binary_be_bd_full_run_execution_trace_transition_multiply_congruence = (ff_current_be_bd_full_run_execution_trace) + m * ff_right_binary_be_bd_full_run_execution_trace_transition_multiply_congruence))))))))))) /\ (((exists ff_h_be_bd_full_run_execution_terminal. ff_h_be_bd_full_run_execution_terminal + S (r) = S ((S (l)) * ff_trace_scale_be_bd_full_run_execution)) /\ exists ff_q_be_bd_full_run_execution_terminal. ff_trace_code_be_bd_full_run_execution = ff_q_be_bd_full_run_execution_terminal * S ((S (l)) * ff_trace_scale_be_bd_full_run_execution) + (r))))) /\ (exists ff_power_binary_bd_full_run_power. ((exists ff_b_binary_bd_full_run_power_value ff_c_binary_bd_full_run_power_value. ((forall ff_i_binary_bd_full_run_power_value_repeat. (exists ff_lt_binary_bd_full_run_power_value_repeat_bound. ff_lt_binary_bd_full_run_power_value_repeat_bound + S ff_i_binary_bd_full_run_power_value_repeat = n) -> (((exists ff_h_binary_bd_full_run_power_value_repeat_decoded. ff_h_binary_bd_full_run_power_value_repeat_decoded + S (a) = S ((S (ff_i_binary_bd_full_run_power_value_repeat)) * ff_c_binary_bd_full_run_power_value)) /\ exists ff_q_binary_bd_full_run_power_value_repeat_decoded. ff_b_binary_bd_full_run_power_value = ff_q_binary_bd_full_run_power_value_repeat_decoded * S ((S (ff_i_binary_bd_full_run_power_value_repeat)) * ff_c_binary_bd_full_run_power_value) + (a)))) /\ (exists ff_u_binary_bd_full_run_power_value_product ff_v_binary_bd_full_run_power_value_product. ((((exists ff_h_binary_bd_full_run_power_value_product_start. ff_h_binary_bd_full_run_power_value_product_start + S (1) = S ((S (0)) * ff_v_binary_bd_full_run_power_value_product)) /\ exists ff_q_binary_bd_full_run_power_value_product_start. ff_u_binary_bd_full_run_power_value_product = ff_q_binary_bd_full_run_power_value_product_start * S ((S (0)) * ff_v_binary_bd_full_run_power_value_product) + (1))) /\ ((((exists ff_h_binary_bd_full_run_power_value_product_terminal. ff_h_binary_bd_full_run_power_value_product_terminal + S (ff_power_binary_bd_full_run_power) = S ((S (n)) * ff_v_binary_bd_full_run_power_value_product)) /\ exists ff_q_binary_bd_full_run_power_value_product_terminal. ff_u_binary_bd_full_run_power_value_product = ff_q_binary_bd_full_run_power_value_product_terminal * S ((S (n)) * ff_v_binary_bd_full_run_power_value_product) + (ff_power_binary_bd_full_run_power))) /\ forall ff_i_binary_bd_full_run_power_value_product. (exists ff_lt_binary_bd_full_run_power_value_product_bound. ff_lt_binary_bd_full_run_power_value_product_bound + S ff_i_binary_bd_full_run_power_value_product = n) -> exists ff_p_binary_bd_full_run_power_value_product ff_r_binary_bd_full_run_power_value_product ff_s_binary_bd_full_run_power_value_product. ((((exists ff_h_binary_bd_full_run_power_value_product_factor. ff_h_binary_bd_full_run_power_value_product_factor + S (ff_p_binary_bd_full_run_power_value_product) = S ((S (ff_i_binary_bd_full_run_power_value_product)) * ff_c_binary_bd_full_run_power_value)) /\ exists ff_q_binary_bd_full_run_power_value_product_factor. ff_b_binary_bd_full_run_power_value = ff_q_binary_bd_full_run_power_value_product_factor * S ((S (ff_i_binary_bd_full_run_power_value_product)) * ff_c_binary_bd_full_run_power_value) + (ff_p_binary_bd_full_run_power_value_product))) /\ ((((exists ff_h_binary_bd_full_run_power_value_product_partial. ff_h_binary_bd_full_run_power_value_product_partial + S (ff_r_binary_bd_full_run_power_value_product) = S ((S (ff_i_binary_bd_full_run_power_value_product)) * ff_v_binary_bd_full_run_power_value_product)) /\ exists ff_q_binary_bd_full_run_power_value_product_partial. ff_u_binary_bd_full_run_power_value_product = ff_q_binary_bd_full_run_power_value_product_partial * S ((S (ff_i_binary_bd_full_run_power_value_product)) * ff_v_binary_bd_full_run_power_value_product) + (ff_r_binary_bd_full_run_power_value_product))) /\ ((((exists ff_h_binary_bd_full_run_power_value_product_successor. ff_h_binary_bd_full_run_power_value_product_successor + S (ff_s_binary_bd_full_run_power_value_product) = S ((S (S ff_i_binary_bd_full_run_power_value_product)) * ff_v_binary_bd_full_run_power_value_product)) /\ exists ff_q_binary_bd_full_run_power_value_product_successor. ff_u_binary_bd_full_run_power_value_product = ff_q_binary_bd_full_run_power_value_product_successor * S ((S (S ff_i_binary_bd_full_run_power_value_product)) * ff_v_binary_bd_full_run_power_value_product) + (ff_s_binary_bd_full_run_power_value_product))) /\ ff_s_binary_bd_full_run_power_value_product = ff_r_binary_bd_full_run_power_value_product * ff_p_binary_bd_full_run_power_value_product)))))))) /\ (((exists ff_gap_binary_bd_full_run_power_residue. ff_gap_binary_bd_full_run_power_residue + S (r) = m) /\ (exists ff_left_binary_bd_full_run_power_residue_congruence ff_right_binary_bd_full_run_power_residue_congruence. (ff_power_binary_bd_full_run_power) + m * ff_left_binary_bd_full_run_power_residue_congruence = (r) + m * ff_right_binary_bd_full_run_power_residue_congruence)))))))) -> (exists ff_ones_bd_run_bound_cost. ((((exists ff_u_bd_run_bound_cost_count_sum ff_v_bd_run_bound_cost_count_sum. ((((exists ff_h_bd_run_bound_cost_count_sum_start. ff_h_bd_run_bound_cost_count_sum_start + S (0) = S ((S (0)) * ff_v_bd_run_bound_cost_count_sum)) /\ exists ff_q_bd_run_bound_cost_count_sum_start. ff_u_bd_run_bound_cost_count_sum = ff_q_bd_run_bound_cost_count_sum_start * S ((S (0)) * ff_v_bd_run_bound_cost_count_sum) + (0))) /\ ((((exists ff_h_bd_run_bound_cost_count_sum_terminal. ff_h_bd_run_bound_cost_count_sum_terminal + S (ff_ones_bd_run_bound_cost) = S ((S (l)) * ff_v_bd_run_bound_cost_count_sum)) /\ exists ff_q_bd_run_bound_cost_count_sum_terminal. ff_u_bd_run_bound_cost_count_sum = ff_q_bd_run_bound_cost_count_sum_terminal * S ((S (l)) * ff_v_bd_run_bound_cost_count_sum) + (ff_ones_bd_run_bound_cost))) /\ forall ff_i_bd_run_bound_cost_count_sum. (exists ff_lt_bd_run_bound_cost_count_sum_bound. ff_lt_bd_run_bound_cost_count_sum_bound + S ff_i_bd_run_bound_cost_count_sum = l) -> exists ff_a_bd_run_bound_cost_count_sum ff_r_bd_run_bound_cost_count_sum ff_s_bd_run_bound_cost_count_sum. ((((exists ff_h_bd_run_bound_cost_count_sum_summand. ff_h_bd_run_bound_cost_count_sum_summand + S (ff_a_bd_run_bound_cost_count_sum) = S ((S (ff_i_bd_run_bound_cost_count_sum)) * c)) /\ exists ff_q_bd_run_bound_cost_count_sum_summand. b = ff_q_bd_run_bound_cost_count_sum_summand * S ((S (ff_i_bd_run_bound_cost_count_sum)) * c) + (ff_a_bd_run_bound_cost_count_sum))) /\ ((((exists ff_h_bd_run_bound_cost_count_sum_partial. ff_h_bd_run_bound_cost_count_sum_partial + S (ff_r_bd_run_bound_cost_count_sum) = S ((S (ff_i_bd_run_bound_cost_count_sum)) * ff_v_bd_run_bound_cost_count_sum)) /\ exists ff_q_bd_run_bound_cost_count_sum_partial. ff_u_bd_run_bound_cost_count_sum = ff_q_bd_run_bound_cost_count_sum_partial * S ((S (ff_i_bd_run_bound_cost_count_sum)) * ff_v_bd_run_bound_cost_count_sum) + (ff_r_bd_run_bound_cost_count_sum))) /\ ((((exists ff_h_bd_run_bound_cost_count_sum_successor. ff_h_bd_run_bound_cost_count_sum_successor + S (ff_s_bd_run_bound_cost_count_sum) = S ((S (S ff_i_bd_run_bound_cost_count_sum)) * ff_v_bd_run_bound_cost_count_sum)) /\ exists ff_q_bd_run_bound_cost_count_sum_successor. ff_u_bd_run_bound_cost_count_sum = ff_q_bd_run_bound_cost_count_sum_successor * S ((S (S ff_i_bd_run_bound_cost_count_sum)) * ff_v_bd_run_bound_cost_count_sum) + (ff_s_bd_run_bound_cost_count_sum))) /\ ff_s_bd_run_bound_cost_count_sum = ff_r_bd_run_bound_cost_count_sum + ff_a_bd_run_bound_cost_count_sum)))))) /\ (forall ff_i_bd_run_bound_cost_count_bits. (exists ff_lt_bd_run_bound_cost_count_bits_bound. ff_lt_bd_run_bound_cost_count_bits_bound + S ff_i_bd_run_bound_cost_count_bits = l) -> exists ff_bit_bd_run_bound_cost_count_bits. ((((exists ff_h_bd_run_bound_cost_count_bits_decoded. ff_h_bd_run_bound_cost_count_bits_decoded + S (ff_bit_bd_run_bound_cost_count_bits) = S ((S (ff_i_bd_run_bound_cost_count_bits)) * c)) /\ exists ff_q_bd_run_bound_cost_count_bits_decoded. b = ff_q_bd_run_bound_cost_count_bits_decoded * S ((S (ff_i_bd_run_bound_cost_count_bits)) * c) + (ff_bit_bd_run_bound_cost_count_bits))) /\ (ff_bit_bd_run_bound_cost_count_bits = 0 \/ ff_bit_bd_run_bound_cost_count_bits = 1))))) /\ operations = (2 + (l + l)) + ff_ones_bd_run_bound_cost)) -> exists gap. gap + operations = 3 * l + 2

Constructive proof overview

Generated structural guide

Every complete actual canonical-length square-and-multiply execution has genuine BitCount-measured operation cost at most 3*BitLen(exponent)+2.

The unchanged tactic script uses 1 declared prerequisite and contains 16 exact native proof lines.

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

Proof neighborhood

Direct dependencies

Direct dependents

Formal native tactic body

Dependencies are introduced as named hypotheses before line 1. Local theorem links identify exact declared prerequisites. This exact body belongs to a complete independently kernel-checked constructive proof bundle and has Alpha checked-use authority; it does not imply Stable membership.

Read the argument

Proof checkpoints

16 script commands · 2 reading checkpoints · 0 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.

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

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

  1. L1
    intro n
  2. L2
    intro a
  3. L3
    intro m
  4. L4
    intro l
  5. L5
    intro b
  6. L6
    intro c
  7. L7
    intro r
  8. L8
    intro operations
  9. L9
    intro hexecution
  10. L10
    intro hcost
02Use earlier factsL11–16

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

  1. L11
    specialize binary_digit_operation_count_bound b
  2. L12
    specialize binary_digit_operation_count_bound c
  3. L13
    specialize binary_digit_operation_count_bound l
  4. L14
    specialize binary_digit_operation_count_bound operations
  5. L15
    apply binary_digit_operation_count_bound
  6. L16
    exact hcost

Library-wide reading audit

Original exact command ledger · 16 lines
  1. 0001intro n
  2. 0002intro a
  3. 0003intro m
  4. 0004intro l
  5. 0005intro b
  6. 0006intro c
  7. 0007intro r
  8. 0008intro operations
  9. 0009intro hexecution
  10. 0010intro hcost
  11. 0011specialize binary_digit_operation_count_bound b
  12. 0012specialize binary_digit_operation_count_bound c
  13. 0013specialize binary_digit_operation_count_bound l
  14. 0014specialize binary_digit_operation_count_bound operations
  15. 0015apply binary_digit_operation_count_bound
  16. 0016exact hcost

Separate complete second-wave branches: Full T13 proof · Alpha v27.