def thresh_m

bend-collections-laws-math@1.0.0.0 · proofs/math/random/uint64n.bend:80

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/spec/math/random/rand.bend as SR
import bend-collections-laws-math@1.0.0.0/src/math/u64.bend as WU
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/random/rand.bend as R
import bend-collections-laws-math@1.0.0.0/proofs/lib/nat.bend as N
import bend-collections-laws-math@1.0.0.0/proofs/lib/arith.bend as LA
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/proofs/math/typed/w64dmrem.bend as DMR
import bend-collections-laws-math@1.0.0.0/proofs/math/natural/arith.bend as AR

80def thresh_m(+one: Nat, +h1: {one == 1n : Nat}, +n: WU.U64, +m: Nat, +hv: {SW.value(n) == 1n+m : Nat}, +hz: {X.is_zero(n) == False{} : Bool}) -> {SW.value(R.thresh(n)) == SR.pow2mod(64n, 1n+m) : Nat}:
81  +s = SW.value(X.sub(Z(), n))
82  +hn = Equal.trans(Bool, Nat.is_eq(SW.value(n), 0n), X.is_zero(n), False{}, Equal.sym(Bool, X.is_zero(n), Nat.is_eq(SW.value(n), 0n), WA.is_zero_value(n)), hz)
83  +ns = Equal.trans(Nat, Nat.add(s, 1n+m), Nat.add(s, SW.value(n)), C.shift(64n, one), Equal.cong(Nat, Nat, z => Nat.add(s, z), 1n+m, SW.value(n), Equal.sym(Nat, SW.value(n), 1n+m, hv)), neg_sum(one, h1, n, hn))
84  Equal.trans(Nat, SW.value(R.thresh(n)), Nat.mod(s, SW.value(n)), SR.pow2mod(64n, 1n+m),
85    DMR.divmod_rem(X.sub(Z(), n), n, hz),
86    %Equal.sym(Nat, SW.value(n), 1n+m, hv) : {Nat.mod(s, _) == SR.pow2mod(64n, 1n+m) : Nat}
87    Equal.trans(Nat, Nat.mod(s, 1n+m), Nat.mod(Nat.add(Nat.mul(1n, 1n+m), s), 1n+m), SR.pow2mod(64n, 1n+m),
88      Equal.sym(Nat, Nat.mod(Nat.add(Nat.mul(1n, 1n+m), s), 1n+m), Nat.mod(s, 1n+m), AR.absorb(m, 1n, s)),
89      %Equal.sym(Nat, Nat.mul(1n, 1n+m), 1n+m, LA.one_mul(1n+m)) : {Nat.mod(Nat.add(_, s), 1n+m) == SR.pow2mod(64n, 1n+m) : Nat}
90      %N.add_comm(s, 1n+m) : {Nat.mod(_, 1n+m) == SR.pow2mod(64n, 1n+m) : Nat}
91      %Equal.sym(Nat, Nat.add(s, 1n+m), C.shift(64n, one), ns) : {Nat.mod(_, 1n+m) == SR.pow2mod(64n, 1n+m) : Nat}
92      Equal.sym(Nat, SR.pow2mod(64n, 1n+m), Nat.mod(C.shift(64n, one), 1n+m), pm_one(64n, m, one, h1))))