def high_div

bend-collections-laws-crypto@1.0.0.0 · proofs/math/typed/width.bend:445

import Base
import bend-collections-laws-crypto@1.0.0.0/spec/lib/common.bend as C
import bend-collections-laws-crypto@1.0.0.0/proofs/lib/nat.bend as N
import bend-collections-laws-crypto@1.0.0.0/proofs/lib/logic.bend as L
import bend-collections-laws-crypto@1.0.0.0/proofs/math/natural/arith.bend as NR

445# high(k, n) is n div 2^k, low(k, n) is n mod 2^k
446def high_div(+k: Nat, +n: Nat, +pp: Nat, +hp: {C.pow2(k) == 1n+pp : Nat}) -> {C.high(k, n) == Nat.div(n, 1n+pp) : Nat}:
447  +l = C.low(k, n)
448  +h = C.high(k, n)
449  +eS = Equal.trans(Nat, C.shift(k, h), Nat.mul(h, C.shift(k, 1n)), Nat.mul(h, 1n+pp), shift_mul(k, h), Equal.cong(Nat, Nat, t => Nat.mul(h, t), C.shift(k, 1n), 1n+pp, Equal.trans(Nat, C.shift(k, 1n), C.pow2(k), 1n+pp, shift_one(k), hp)))
450  +e = Equal.trans(Nat, Nat.add(Nat.mul(h, 1n+pp), l), Nat.add(l, Nat.mul(h, 1n+pp)), n, N.add_comm(Nat.mul(h, 1n+pp), l), Equal.trans(Nat, Nat.add(l, Nat.mul(h, 1n+pp)), Nat.add(l, C.shift(k, h)), n, Equal.cong(Nat, Nat, t => Nat.add(l, t), Nat.mul(h, 1n+pp), C.shift(k, h), Equal.sym(Nat, C.shift(k, h), Nat.mul(h, 1n+pp), eS)), Equal.sym(Nat, n, Nat.add(l, C.shift(k, h)), low_high(k, n))))
451  +hl = L.subst(Nat, t => {Nat.is_lt(l, t) == True{} : Bool}, C.pow2(k), 1n+pp, hp, low_lt(k, n))
452  Equal.trans(Nat, h, Nat.div(Nat.add(Nat.mul(h, 1n+pp), l), 1n+pp), Nat.div(n, 1n+pp), Equal.sym(Nat, Nat.div(Nat.add(Nat.mul(h, 1n+pp), l), 1n+pp), h, NR.div_of(h, pp, l, hl)), Equal.cong(Nat, Nat, t => Nat.div(t, 1n+pp), Nat.add(Nat.mul(h, 1n+pp), l), n, e))