diff options
| author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-24 18:55:27 +0700 |
|---|---|---|
| committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-24 18:55:27 +0700 |
| commit | fc99ec8763011525d7c2d38f7901c8802a17c9b0 (patch) | |
| tree | d0b3e8a83d7603578edb9d9f3e7c398829429c10 | |
| parent | Run point test on all supported coordinate systems (diff) | |
| download | BouncyCastle.NET-ed25519-fc99ec8763011525d7c2d38f7901c8802a17c9b0.tar.xz | |
Implement very basic Barrett reduction as alternative to very slow BigInteger.Mod
| -rw-r--r-- | crypto/src/math/ec/ECFieldElement.cs | 60 |
1 files changed, 41 insertions, 19 deletions
diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs index d8813bf0b..c2754ada8 100644 --- a/crypto/src/math/ec/ECFieldElement.cs +++ b/crypto/src/math/ec/ECFieldElement.cs @@ -77,20 +77,24 @@ namespace Org.BouncyCastle.Math.EC internal static BigInteger CalculateResidue(BigInteger p) { int bitLength = p.BitLength; - //if (bitLength > 128) - if (bitLength > 64) + if (bitLength > 128) + //if (bitLength > 64) { /* * NOTE: Due to poor performance of BigInteger.Mod in C#, the residue-based reduction is * currently faster even for e.g. P-256, where the prime has 32 leading 1 bits. */ - //BigInteger firstWord = p.ShiftRight(bitLength - 64); - //if (firstWord.LongValue == -1L) - BigInteger firstWord = p.ShiftRight(bitLength - 32); - if (firstWord.IntValue == -1) + BigInteger firstWord = p.ShiftRight(bitLength - 64); + if (firstWord.LongValue == -1L) + //BigInteger firstWord = p.ShiftRight(bitLength - 32); + //if (firstWord.IntValue == -1) { return BigInteger.One.ShiftLeft(bitLength).Subtract(p); } + if ((bitLength & 31) == 0) + { + return BigInteger.One.ShiftLeft(bitLength << 1).Divide(p).Negate(); + } } return null; } @@ -338,7 +342,11 @@ namespace Org.BouncyCastle.Math.EC protected virtual BigInteger ModReduce(BigInteger x) { - if (r != null) + if (r == null) + { + x = x.Mod(q); + } + else { bool negative = x.SignValue < 0; if (negative) @@ -346,17 +354,35 @@ namespace Org.BouncyCastle.Math.EC x = x.Abs(); } int qLen = q.BitLength; - BigInteger qMod = BigInteger.One.ShiftLeft(qLen); - bool rIsOne = r.Equals(BigInteger.One); - while (x.BitLength > (qLen + 1)) + if (r.SignValue > 0) { - BigInteger u = x.ShiftRight(qLen); - BigInteger v = x.Remainder(qMod); - if (!rIsOne) + BigInteger qMod = BigInteger.One.ShiftLeft(qLen); + bool rIsOne = r.Equals(BigInteger.One); + while (x.BitLength > (qLen + 1)) { - u = u.Multiply(r); + BigInteger u = x.ShiftRight(qLen); + BigInteger v = x.Remainder(qMod); + if (!rIsOne) + { + u = u.Multiply(r); + } + x = u.Add(v); + } + } + else + { + BigInteger mu = r.Negate(); + BigInteger u = mu.Multiply(x.ShiftRight(qLen - 32)); + BigInteger quot = u.ShiftRight(qLen + 32); + BigInteger v = quot.Multiply(q); + BigInteger bk1 = BigInteger.One.ShiftLeft(qLen + 32); + v = v.Remainder(bk1); + x = x.Remainder(bk1); + x = x.Subtract(v); + if (x.SignValue < 0) + { + x = x.Add(bk1); } - x = u.Add(v); } while (x.CompareTo(q) >= 0) { @@ -367,10 +393,6 @@ namespace Org.BouncyCastle.Math.EC x = q.Subtract(x); } } - else - { - x = x.Mod(q); - } return x; } |