def Mag.modpow

bend-kit-bignum@0.1.0.0 · bigint.bend:274

import Base

274# b^e * acc mod m, with b and acc below m. f counts e's bits: 14 per limb,
275# since 10^4 < 2^14.
276def Mag.modpow(+f: Nat, +b: List<&2, U32>, +e: List<&2, U32>,
277  +acc: List<&2, U32>, +m: List<&2, U32>) -> List<&2, U32>:
278  match f:
279    case 0n:
280      acc
281    case 1n+g:
282      +h = Mag.half(e)
283      +acc2 = Mag.if(List<&2, U32>, Mag.odd(e),
284        u => Mag.rem(Mag.mul(acc, b), m), u => acc)
285      Mag.if(List<&2, U32>, List.is_empty(&2, U32, h), u => acc2,
286        u => Mag.modpow(g, Mag.rem(Mag.mul(b, b), m), h, acc2, m))