def step_e

bend-collections-laws-crypto@1.0.0.0 · proofs/crypto/secp256k1/scalarpow.bend:28

import Base
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/scalar.bend as S
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/lemmas/proofs/nat_algebra.bend as NA
import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/semiring.bend as SR
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/consts.bend as K
import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/modexp.bend as ME
import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/scalarops.bend as SO

28# one square-and-multiply step
29def step_e(+one: Nat, +h1: {one == 1n : Nat}, +x: List<&2, Nat>, +hx: {FS.reduced(one, FS.order(one), x) == True{} : Bool}, +acc: List<&2, Nat>, +ha: {FS.reduced(one, FS.order(one), acc) == True{} : Bool}, +e: Nat, +he: {LV.ev(acc) == Nat.mod(Nat.pow(LV.ev(x), e), 1n+K.np(one)) : Nat}, b: Nat, +hb: {Nat.is_lt(b, 2n) == True{} : Bool}) -> {LV.ev(S.pow_step(b, x, S.mul(acc, acc))) == Nat.mod(Nat.pow(LV.ev(x), Nat.add(Nat.mul(b, one), Nat.double(e))), 1n+K.np(one)) : Nat}:
30  match b:
31    case 0n:
32      %Equal.sym(Nat, LV.ev(S.mul(acc, acc)), Nat.mod(Nat.mul(LV.ev(acc), LV.ev(acc)), 1n+K.np(one)), SO.mul_e(one, h1, acc, acc, ha, ha)) : {_ == Nat.mod(Nat.pow(LV.ev(x), Nat.double(e)), 1n+K.np(one)) : Nat}
33      ME.sq_step(K.np(one), LV.ev(x), e, LV.ev(acc), he)
34    case 1n:
35      +sq = S.mul(acc, acc)
36      +es = Equal.trans(Nat, LV.ev(sq), Nat.mod(Nat.mul(LV.ev(acc), LV.ev(acc)), 1n+K.np(one)), Nat.mod(Nat.pow(LV.ev(x), Nat.double(e)), 1n+K.np(one)), SO.mul_e(one, h1, acc, acc, ha, ha), ME.sq_step(K.np(one), LV.ev(x), e, LV.ev(acc), he))
37      %Equal.sym(Nat, Nat.mul(1n, one), one, SR.one_mul(one)) : {LV.ev(S.mul(S.mul(acc, acc), x)) == Nat.mod(Nat.pow(LV.ev(x), Nat.add(_, Nat.double(e))), 1n+K.np(one)) : Nat}
38      %Equal.sym(Nat, one, 1n, h1) : {LV.ev(S.mul(S.mul(acc, acc), x)) == Nat.mod(Nat.pow(LV.ev(x), Nat.add(_, Nat.double(e))), 1n+K.np(one)) : Nat}
39      %Equal.sym(Nat, Nat.add(1n, Nat.double(e)), Nat.add(Nat.double(e), 1n), NA.add_comm(1n, Nat.double(e))) : {LV.ev(S.mul(S.mul(acc, acc), x)) == Nat.mod(Nat.pow(LV.ev(x), _), 1n+K.np(one)) : Nat}
40      %Equal.sym(Nat, LV.ev(S.mul(S.mul(acc, acc), x)), Nat.mod(Nat.mul(LV.ev(S.mul(acc, acc)), LV.ev(x)), 1n+K.np(one)), SO.mul_e(one, h1, S.mul(acc, acc), x, SO.mul_r(one, h1, acc, acc, ha, ha), hx)) : {_ == Nat.mod(Nat.pow(LV.ev(x), Nat.add(Nat.double(e), 1n)), 1n+K.np(one)) : Nat}
41      ME.mul_step(K.np(one), LV.ev(x), Nat.double(e), LV.ev(S.mul(acc, acc)), es)
42    case 2n+ +k:
43      Empty.absurd({LV.ev(S.pow_step(2n+k, x, S.mul(acc, acc))) == Nat.mod(Nat.pow(LV.ev(x), Nat.add(Nat.mul(2n+k, one), Nat.double(e))), 1n+K.np(one)) : Nat}, N.lt_zero_absurd(k, hb))