def exp_sqrt

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

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/limbs.bend as L
import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/field.bend as F
import bend-collections-laws-crypto@1.0.0.0/proofs/math/natural/arith.bend as NR
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/bitsv.bend as BV

314# 4 hv(sqrt bits) = p + 1, so hv(sqrt bits) = (p + 1) / 4
315def exp_sqrt(+one: Nat, +h1: {one == 1n : Nat}) -> {BV.hv(F.sqrt_bits(), one, 0n) == Nat.div(Nat.add(1n+K.pp(one), 1n), 4n) : Nat}:
316  +d = FS.digits(one, L.norm16([975n, 0n, 1n]))
317  +h = BV.hv(F.sqrt_bits(), one, 0n)
318  +e = NR.add_cancel(Nat.add(d, one), BV.hv(L.cbits(L.bits(L.norm16([975n, 0n, 1n]))), one, 0n), Nat.add(1n+K.pp(one), one), sq_g(one, h1))
319  +e4 = Equal.trans(Nat, Nat.add(Nat.add(h, h), Nat.add(h, h)), BV.hv(L.cbits(L.bits(L.norm16([975n, 0n, 1n]))), one, 0n), Nat.add(1n+K.pp(one), one), Equal.sym(Nat, BV.hv(L.cbits(L.bits(L.norm16([975n, 0n, 1n]))), one, 0n), Nat.add(Nat.add(h, h), Nat.add(h, h)), sq_four(one)), e)
320  %Equal.sym(Nat, 1n, one, Equal.sym(Nat, one, 1n, h1)) : {BV.hv(F.sqrt_bits(), one, 0n) == Nat.div(Nat.add(1n+K.pp(one), _), 4n) : Nat}
321  %Equal.sym(Nat, Nat.add(1n+K.pp(one), one), Nat.add(Nat.add(BV.hv(F.sqrt_bits(), one, 0n), BV.hv(F.sqrt_bits(), one, 0n)), Nat.add(BV.hv(F.sqrt_bits(), one, 0n), BV.hv(F.sqrt_bits(), one, 0n))), Equal.sym(Nat, Nat.add(Nat.add(BV.hv(F.sqrt_bits(), one, 0n), BV.hv(F.sqrt_bits(), one, 0n)), Nat.add(BV.hv(F.sqrt_bits(), one, 0n), BV.hv(F.sqrt_bits(), one, 0n))), Nat.add(1n+K.pp(one), one), e4)) : {BV.hv(F.sqrt_bits(), one, 0n) == Nat.div(_, 4n) : Nat}
322  %Equal.sym(Nat, Nat.add(Nat.add(BV.hv(F.sqrt_bits(), one, 0n), BV.hv(F.sqrt_bits(), one, 0n)), Nat.add(BV.hv(F.sqrt_bits(), one, 0n), BV.hv(F.sqrt_bits(), one, 0n))), Nat.add(Nat.mul(BV.hv(F.sqrt_bits(), one, 0n), 4n), 0n), four_h(BV.hv(F.sqrt_bits(), one, 0n))) : {BV.hv(F.sqrt_bits(), one, 0n) == Nat.div(_, 4n) : Nat}
323  Equal.sym(Nat, Nat.div(Nat.add(Nat.mul(BV.hv(F.sqrt_bits(), one, 0n), 4n), 0n), 4n), BV.hv(F.sqrt_bits(), one, 0n), NR.div_of(BV.hv(F.sqrt_bits(), one, 0n), 3n, 0n, {==}))