pub(super) const fn barrett_reduce(lo: U256, hi: U256) -> U256Expand description
Barrett Reduction
NOTE: this implementation is specialized to P-256’s order! See #1155
The general algorithm is:
p = n = order of group
b = 2^64 = 64bit machine word
k = 4
a \in [0, 2^512]
mu := floor(b^{2k} / p)
q1 := floor(a / b^{k - 1})
q2 := q1 * mu
q3 := floor(q2 / b^{k + 1})
r1 := a mod b^{k + 1}
r2 := q3 * m mod b^{k + 1}
r := r1 - r2
if r < 0: r := r + b^{k + 1}
while r >= p: do r := r - p (at most twice)References:
-
Handbook of Applied Cryptography, Chapter 14 Algorithm 14.42 http://cacr.uwaterloo.ca/hac/about/chap14.pdf
-
Efficient and Secure Elliptic Curve Cryptography Implementation of Curve P-256 Algorithm 6) Barrett Reduction modulo p https://csrc.nist.gov/csrc/media/events/workshop-on-elliptic-curve-cryptography-standards/documents/papers/session6-adalier-mehmet.pdf