def xp_digits

bend-collections-laws-crypto@1.0.0.0 · proofs/crypto/secp256k1/fieldpow.bend:146

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/lemmas/proofs/nat_algebra.bend as NA
import bend-collections-laws-crypto@1.0.0.0/proofs/math/typed/width.bend as WW
import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/semiring.bend as SR

146# 978 + 2^32 = c_p + 1
147def xp_digits(+one: Nat, +h1: {one == 1n : Nat}) -> {FS.digits(one, L.norm16([978n, 0n, 1n])) == Nat.add(FS.cp(one), one) : Nat}:
148  %Equal.sym(List<&2, Nat>, L.norm16([978n, 0n, 1n]), [978n, 0n, 1n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n], xp_lit()) : {FS.digits(one, _) == Nat.add(FS.cp(one), one) : Nat}
149  %Equal.sym(Nat, FS.digits(one, [0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n, 0n]), 0n, zeros13(one)) : {Nat.add(Nat.mul(one, 978n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, _)))))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
150  %Equal.sym(Nat, Nat.mul(one, 978n), Nat.add(one, Nat.mul(one, 977n)), NA.mul_succ(one, 977n)) : {Nat.add(_, C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
151  %Equal.sym(Nat, Nat.mul(one, 0n), 0n, NA.mul_zero(one)) : {Nat.add(Nat.add(one, Nat.mul(one, 977n)), C.shift(16n, Nat.add(_, C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
152  %Equal.sym(Nat, Nat.mul(one, 1n), one, NA.mul_one(one)) : {Nat.add(Nat.add(one, Nat.mul(one, 977n)), C.shift(16n, Nat.add(0n, C.shift(16n, Nat.add(_, C.shift(16n, 0n)))))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
153  %Equal.sym(Nat, C.shift(16n, 0n), 0n, WW.shift_zero(16n)) : {Nat.add(Nat.add(one, Nat.mul(one, 977n)), C.shift(16n, Nat.add(0n, C.shift(16n, Nat.add(one, _))))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
154  %Equal.sym(Nat, Nat.add(one, 0n), one, NA.add_zero(one)) : {Nat.add(Nat.add(one, Nat.mul(one, 977n)), C.shift(16n, Nat.add(0n, C.shift(16n, _)))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
155  %Equal.sym(Nat, Nat.add(0n, C.shift(16n, one)), C.shift(16n, one), SR.zero_add(C.shift(16n, one))) : {Nat.add(Nat.add(one, Nat.mul(one, 977n)), C.shift(16n, _)) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
156  %Equal.sym(Nat, C.shift(16n, C.shift(16n, one)), C.shift(32n, one), SR.shift_shift(16n, 16n, one)) : {Nat.add(Nat.add(one, Nat.mul(one, 977n)), _) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
157  %Equal.sym(Nat, Nat.add(Nat.add(one, Nat.mul(one, 977n)), C.shift(32n, one)), Nat.add(one, Nat.add(Nat.mul(one, 977n), C.shift(32n, one))), NA.add_assoc(one, Nat.mul(one, 977n), C.shift(32n, one))) : {_ == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
158  %Equal.sym(Nat, Nat.add(Nat.mul(one, 977n), C.shift(32n, one)), Nat.add(C.shift(32n, one), Nat.mul(one, 977n)), NA.add_comm(Nat.mul(one, 977n), C.shift(32n, one))) : {Nat.add(one, _) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(Nat.mul(one, 0n), C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
159  %Equal.sym(Nat, Nat.mul(one, 0n), 0n, NA.mul_zero(one)) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(_, C.shift(16n, Nat.add(Nat.mul(one, 1n), C.shift(16n, 0n)))))), one) : Nat}
160  %Equal.sym(Nat, Nat.mul(one, 1n), one, NA.mul_one(one)) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(0n, C.shift(16n, Nat.add(_, C.shift(16n, 0n)))))), one) : Nat}
161  %Equal.sym(Nat, C.shift(16n, 0n), 0n, WW.shift_zero(16n)) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(0n, C.shift(16n, Nat.add(one, _))))), one) : Nat}
162  %Equal.sym(Nat, Nat.add(one, 0n), one, NA.add_zero(one)) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, Nat.add(0n, C.shift(16n, _)))), one) : Nat}
163  %Equal.sym(Nat, Nat.add(0n, C.shift(16n, one)), C.shift(16n, one), SR.zero_add(C.shift(16n, one))) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == Nat.add(Nat.add(Nat.mul(one, 977n), C.shift(16n, _)), one) : Nat}
164  %Equal.sym(Nat, C.shift(16n, C.shift(16n, one)), C.shift(32n, one), SR.shift_shift(16n, 16n, one)) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == Nat.add(Nat.add(Nat.mul(one, 977n), _), one) : Nat}
165  %Equal.sym(Nat, Nat.add(Nat.mul(one, 977n), C.shift(32n, one)), Nat.add(C.shift(32n, one), Nat.mul(one, 977n)), NA.add_comm(Nat.mul(one, 977n), C.shift(32n, one))) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == Nat.add(_, one) : Nat}
166  %Equal.sym(Nat, Nat.add(Nat.add(C.shift(32n, one), Nat.mul(one, 977n)), one), Nat.add(C.shift(32n, one), Nat.add(Nat.mul(one, 977n), one)), NA.add_assoc(C.shift(32n, one), Nat.mul(one, 977n), one)) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == _ : Nat}
167  %Equal.sym(Nat, Nat.add(Nat.mul(one, 977n), one), Nat.add(one, Nat.mul(one, 977n)), NA.add_comm(Nat.mul(one, 977n), one)) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == Nat.add(C.shift(32n, one), _) : Nat}
168  %Equal.sym(Nat, Nat.add(C.shift(32n, one), Nat.add(one, Nat.mul(one, 977n))), Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))), NA.add_swap(C.shift(32n, one), one, Nat.mul(one, 977n))) : {Nat.add(one, Nat.add(C.shift(32n, one), Nat.mul(one, 977n))) == _ : Nat}
169  {==}