diff options
| author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-28 15:25:02 +0700 |
|---|---|---|
| committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-28 15:25:02 +0700 |
| commit | a959f6a9c1ebb46d9cd044008d92532d1b5fd364 (patch) | |
| tree | f7b759f9882c68544925a38a0040ce576901fa3c | |
| parent | Fix and re-enable twicePlus for lambda-projective coordinates (diff) | |
| download | BouncyCastle.NET-ed25519-a959f6a9c1ebb46d9cd044008d92532d1b5fd364.tar.xz | |
Implement multi-squaring in-place and use for F2m sqrt()
| -rw-r--r-- | crypto/src/math/ec/ECFieldElement.cs | 13 | ||||
| -rw-r--r-- | crypto/src/math/ec/LongArray.cs | 66 |
2 files changed, 39 insertions, 40 deletions
diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs index 838053827..66fadddec 100644 --- a/crypto/src/math/ec/ECFieldElement.cs +++ b/crypto/src/math/ec/ECFieldElement.cs @@ -1160,15 +1160,14 @@ namespace Org.BouncyCastle.Math.EC public override ECFieldElement Sqrt() { - LongArray root = this.x; - if (root.IsOne() || root.IsZero()) - return this; - - for (int i = 1; i < m; ++i) + LongArray x1 = this.x; + if (x1.IsOne() || x1.IsZero()) { - root = root.ModSquare(m, ks); + return this; } - return new F2mFieldElement(m, ks, root); + + LongArray x2 = x1.ModSquareN(m - 1, m, ks); + return new F2mFieldElement(m, ks, x2); } /** diff --git a/crypto/src/math/ec/LongArray.cs b/crypto/src/math/ec/LongArray.cs index a863c0a61..29f971c46 100644 --- a/crypto/src/math/ec/LongArray.cs +++ b/crypto/src/math/ec/LongArray.cs @@ -1370,7 +1370,7 @@ namespace Org.BouncyCastle.Math.EC private static int ReduceInPlace(long[] buf, int off, int len, int m, int[] ks) { - int mLen = (int)((uint)(m + 63) >> 6); + int mLen = (m + 63) >> 6; if (len < mLen) { return len; @@ -1525,37 +1525,37 @@ namespace Org.BouncyCastle.Math.EC return new LongArray(r, 0, ReduceInPlace(r, 0, r.Length, m, ks)); } - // private LongArray modSquareN(int n, int m, int[] ks) - // { - // int len = GetUsedLength(); - // if (len == 0) - // { - // return this; - // } - // - // int mLen = (m + 63) >>> 6; - // long[] r = new long[mLen << 1]; - // Array.Copy(m_ints, 0, r, 0, len); - // - // while (--n >= 0) - // { - // squareInPlace(r, len, m, ks); - // len = reduceInPlace(r, 0, r.Length, m, ks); - // } - // - // return new LongArray(r, 0, len); - // } - // - // private static void squareInPlace(long[] x, int xLen, int m, int[] ks) - // { - // int pos = xLen << 1; - // while (--xLen >= 0) - // { - // long xVal = x[xLen]; - // x[--pos] = Interleave2_32to64((int)(xVal >>> 32)); - // x[--pos] = Interleave2_32to64((int)xVal); - // } - // } + public LongArray ModSquareN(int n, int m, int[] ks) + { + int len = GetUsedLength(); + if (len == 0) + { + return this; + } + + int mLen = (m + 63) >> 6; + long[] r = new long[mLen << 1]; + Array.Copy(m_ints, 0, r, 0, len); + + while (--n >= 0) + { + SquareInPlace(r, len, m, ks); + len = ReduceInPlace(r, 0, r.Length, m, ks); + } + + return new LongArray(r, 0, len); + } + + private static void SquareInPlace(long[] x, int xLen, int m, int[] ks) + { + int pos = xLen << 1; + while (--xLen >= 0) + { + long xVal = x[xLen]; + x[--pos] = Interleave2_32to64((int)((ulong)xVal >> 32)); + x[--pos] = Interleave2_32to64((int)xVal); + } + } private static void Interleave(long[] x, int xOff, long[] z, int zOff, int count, int width) { @@ -1891,7 +1891,7 @@ namespace Org.BouncyCastle.Math.EC // u(z) := a(z) LongArray uz = (LongArray)Copy(); - int t = (int)((uint)(m + 63) >> 6); + int t = (m + 63) >> 6; // v(z) := f(z) LongArray vz = new LongArray(t); |