def binpow

bend-collections-laws-crypto@1.0.0.0 · spec/math/generic.bend:263

import Base
import bend-collections-laws-crypto@1.0.0.0/src/math/num.bend as N

263# right-to-left binary exponentiation: acc *= base on a 1 bit, base *= base
264# while bits remain, each product rounded (k = 0 is a fixed point, so any
265# fuel past k's bit length gives the same result)
266def binpow(~T: Data, ~op: N.Op<T> -> T, fuel: Nat, +k: Nat, +base: T, +acc: T) -> T:
267  match fuel:
268    case 0n:
269      acc
270    case 1n+f:
271      binpow(~T, ~op, f, Nat.div(k, 2n), pick(T, Nat.is_lt(1n, k), op(N.Mul{base, base}), base), pick(T, Nat.is_eq(Nat.mod(k, 2n), 1n), op(N.Mul{acc, base}), acc))