diff options
Diffstat (limited to 'src/math/big/nat.go')
| -rw-r--r-- | src/math/big/nat.go | 29 |
1 files changed, 21 insertions, 8 deletions
diff --git a/src/math/big/nat.go b/src/math/big/nat.go index 6545bc17ed..c7362e679b 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -216,23 +216,36 @@ func basicMul(z, x, y nat) { } } -// montgomery computes x*y*2^(-n*_W) mod m, -// assuming k = -1/m mod 2^_W. +// montgomery computes z mod m = x*y*2**(-n*_W) mod m, +// assuming k = -1/m mod 2**_W. // z is used for storing the result which is returned; // z must not alias x, y or m. +// See Gueron, "Efficient Software Implementations of Modular Exponentiation". +// https://eprint.iacr.org/2011/239.pdf +// In the terminology of that paper, this is an "Almost Montgomery Multiplication": +// x and y are required to satisfy 0 <= z < 2**(n*_W) and then the result +// z is guaranteed to satisfy 0 <= z < 2**(n*_W), but it may not be < m. func (z nat) montgomery(x, y, m nat, k Word, n int) nat { - var c1, c2 Word + // This code assumes x, y, m are all the same length, n. + // (required by addMulVVW and the for loop). + // It also assumes that x, y are already reduced mod m, + // or else the result will not be properly reduced. + if len(x) != n || len(y) != n || len(m) != n { + panic("math/big: mismatched montgomery number lengths") + } + var c1, c2, c3 Word z = z.make(n) z.clear() for i := 0; i < n; i++ { d := y[i] - c1 += addMulVVW(z, x, d) + c2 = addMulVVW(z, x, d) t := z[0] * k - c2 = addMulVVW(z, m, t) - + c3 = addMulVVW(z, m, t) copy(z, z[1:]) - z[n-1] = c1 + c2 - if z[n-1] < c1 { + cx := c1 + c2 + cy := cx + c3 + z[n-1] = cy + if cx < c2 || cy < c3 { c1 = 1 } else { c1 = 0 |