def limbs_lt

bend-collections-laws-crypto@1.0.0.0 · proofs/crypto/secp256k1/bounds.bend:72

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/spec/crypto/secp256k1/field.bend as FS
import bend-collections-laws-crypto@1.0.0.0/proofs/lib/logic.bend as Lg
import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/limbs.bend as LV
import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/ineq.bend as I

72# k limbs below 2^16 have a value below 2^(16 k)
73def limbs_lt(+one: Nat, +h1: {one == 1n : Nat}, k: Nat, ys: List<&2, Nat>, +h: {FS.limbs16(one, k, ys) == True{} : Bool}) -> {Nat.is_lt(LV.ev(ys), LV.pos(k, one)) == True{} : Bool}:
74  match k ys:
75    case 0n Nil{}:
76      lt_one(one, h1)
77    case 0n y <> t:
78      Empty.absurd({Nat.is_lt(LV.ev(y <> t), LV.pos(0n, one)) == True{} : Bool}, Lg.false_true(h))
79    case 1n+i Nil{}:
80      Empty.absurd({Nat.is_lt(LV.ev([]), LV.pos(1n+i, one)) == True{} : Bool}, Lg.false_true(h))
81    case 1n+ +i +y <> +t:
82      +hy = Lg.and_left(Nat.is_lt(y, C.shift(16n, one)), FS.limbs16(one, i, t), h)
83      +ht = Lg.and_right(Nat.is_lt(y, C.shift(16n, one)), FS.limbs16(one, i, t), h)
84      I.digit_lt(16n, one, h1, y, LV.ev(t), LV.pos(i, one), hy, limbs_lt(one, h1, i, t, ht))