def msim

bend-collections-laws-math@1.0.0.0 · proofs/math/typed/u64mont.bend:242

import Base
import bend-collections-laws-math@1.0.0.0/spec/lib/common.bend as C
import bend-collections-laws-math@1.0.0.0/spec/math/w64.bend as SW
import bend-collections-laws-math@1.0.0.0/src/math/w64.bend as X
import bend-collections-laws-math@1.0.0.0/src/math/u64.bend as WU
import bend-collections-laws-math@1.0.0.0/proofs/math/natural/arith.bend as NR
import bend-collections-laws-math@1.0.0.0/proofs/math/typed/w64add.bend as WA
import bend-collections-laws-math@1.0.0.0/src/math/natural.bend as M

242# the Montgomery loop computes pow_mod_go on the forms
243def msim(+one: Nat, +h1: {one == 1n : Nat}, +bp: Nat, +m: WU.U64, +mp: WU.U64, +hM: {SW.value(m) == 1n+bp : Nat}, +hinv: {1n+C.low(64n, Nat.mul(1n+bp, SW.value(mp))) == C.shift(64n, one) : Nat}, +h63: {Nat.is_lt(1n+bp, C.shift(63n, one)) == True{} : Bool}, +hh: Nat, +hH: {1n+1n+bp == Nat.add(hh, hh) : Nat}, +f: Nat, +b: WU.U64, +acc: WU.U64, +e: WU.U64, +bn: Nat, +an: Nat, +hb: {SW.value(b) == Nat.mod(C.shift(64n, bn), 1n+bp) : Nat}, +ha: {SW.value(acc) == Nat.mod(C.shift(64n, an), 1n+bp) : Nat}, +ez: Bool, +ne: Nat, +hez: {X.is_zero(e) == ez : Bool}, +hne: {SW.value(e) == ne : Nat}) -> {SW.value(X.mpow_go(f, m, mp, b, acc, (e, ez))) == Nat.mod(C.shift(64n, M.pow_mod_go(f, 1n+bp, ne, bn, an)), 1n+bp) : Nat}:
244  match f ez ne:
245    case 0n _ _:
246      ha
247    case 1n+g True{} 0n:
248      ha
249    case 1n+g True{} 1n+ep:
250      Empty.absurd({SW.value(X.mpow_go(1n+g, m, mp, b, acc, (e, True{}))) == Nat.mod(C.shift(64n, M.pow_mod_go(1n+g, 1n+bp, 1n+ep, bn, an)), 1n+bp) : Nat}, true_ne_false(Equal.trans(Bool, True{}, X.is_zero(e), False{}, Equal.sym(Bool, X.is_zero(e), True{}, hez), izv(e, 1n+ep, hne))))
251    case 1n+g False{} 0n:
252      Empty.absurd({SW.value(X.mpow_go(1n+g, m, mp, b, acc, (e, False{}))) == Nat.mod(C.shift(64n, M.pow_mod_go(1n+g, 1n+bp, 0n, bn, an)), 1n+bp) : Nat}, true_ne_false(Equal.trans(Bool, True{}, X.is_zero(e), False{}, Equal.sym(Bool, X.is_zero(e), True{}, izv(e, 0n, hne)), hez)))
253    case 1n+ +g False{} 1n+ +ep:
254      +b2 = X.mont(m, mp, b, b)
255      +eb2 = mform(one, h1, bp, m, mp, hM, hinv, h63, hh, hH, b, b, bn, bn, hb, hb)
256      +o = X.odd(e)
257      +d = Nat.mod(1n+ep, 2n)
258      +ho = Equal.trans(Bool, o, Nat.is_eq(Nat.mod(SW.value(e), 2n), 1n), Nat.is_eq(d, 1n), WA.odd_value(e), Equal.cong(Nat, Bool, t => Nat.is_eq(Nat.mod(t, 2n), 1n), SW.value(e), 1n+ep, hne))
259      +a2 = X.mbit(o, m, mp, b, acc)
260      +ea2 = mbit_v(one, h1, bp, m, mp, hM, hinv, h63, hh, hH, b, acc, bn, an, hb, ha, d, o, NR.dm_lt(1n, 1n+ep), ho)
261      +e2 = X.half(e)
262      +ee2 = Equal.trans(Nat, SW.value(e2), Nat.div(SW.value(e), 2n), Nat.div(1n+ep, 2n), WA.half_value(e), Equal.cong(Nat, Nat, t => Nat.div(t, 2n), SW.value(e), 1n+ep, hne))
263      msim(one, h1, bp, m, mp, hM, hinv, h63, hh, hH, g, b2, a2, e2, Nat.mod(Nat.mul(bn, bn), 1n+bp), M.pow_mod_odd(1n+bp, d, bn, an), eb2, ea2, X.is_zero(e2), Nat.div(1n+ep, 2n), {==}, ee2)