def sel1

bend-collections-laws-crypto@1.0.0.0 · proofs/crypto/secp256k1/sel.bend:56

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/src/crypto/secp256k1/limbs.bend as L
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/lib/lemmas/proofs/nat_algebra.bend as NA

56def sel1(+one: Nat, n: Nat, xs: List<&2, Nat>, ys: List<&2, Nat>, +hx: {FS.limbs16(one, n, xs) == True{} : Bool}, +hy: {FS.limbs16(one, n, ys) == True{} : Bool}) -> {L.select(1n, xs, ys) == xs : List<&2, Nat>}:
57  match n xs:
58    case 0n Nil{}:
59      match ys:
60        case Nil{}:
61          {==}
62        case y <> t:
63          Empty.absurd({L.select(1n, [], y <> t) == [] : List<&2, Nat>}, Lg.false_true(hy))
64    case 0n x <> t:
65      Empty.absurd({L.select(1n, x <> t, ys) == x <> t : List<&2, Nat>}, Lg.false_true(hx))
66    case 1n+k Nil{}:
67      Empty.absurd({L.select(1n, [], ys) == [] : List<&2, Nat>}, Lg.false_true(hx))
68    case 1n+ +k +x <> +xt:
69      match ys:
70        case Nil{}:
71          Empty.absurd({L.select(1n, x <> xt, []) == x <> xt : List<&2, Nat>}, Lg.false_true(hy))
72        case +y <> +yt:
73          +hxt = Lg.and_right(Nat.is_lt(x, C.shift(16n, one)), FS.limbs16(one, k, xt), hx)
74          +hyt = Lg.and_right(Nat.is_lt(y, C.shift(16n, one)), FS.limbs16(one, k, yt), hy)
75          %Equal.sym(List<&2, Nat>, L.select(1n, xt, yt), xt, sel1(one, k, xt, yt, hxt, hyt)) : {Nat.add(Nat.mul(x, 1n), Nat.mul(y, 0n)) <> _ == x <> xt : List<&2, Nat>}
76          %Equal.sym(Nat, Nat.mul(y, 0n), 0n, NA.mul_zero(y)) : {Nat.add(Nat.mul(x, 1n), _) <> xt == x <> xt : List<&2, Nat>}
77          %Equal.sym(Nat, Nat.mul(x, 1n), x, NA.mul_one(x)) : {Nat.add(_, 0n) <> xt == x <> xt : List<&2, Nat>}
78          %Equal.sym(Nat, Nat.add(x, 0n), x, NA.add_zero(x)) : {_ <> xt == x <> xt : List<&2, Nat>}
79          {==}