diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-28 12:24:19 +0400 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2014-01-28 12:24:19 +0400 |
commit | 36be1ca95148ded1cde0ea39551ef9524f89a609 (patch) | |
tree | d87e4d0723386dc287c47f627f5bad6ddbd6a95f /core/src/main/java/org/bouncycastle/math | |
parent | 9af8f490ba965734301f8d587b9b792801eaebce (diff) |
Implement multi-squaring in-place and use for F2m sqrt()
Diffstat (limited to 'core/src/main/java/org/bouncycastle/math')
-rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java | 11 | ||||
-rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/LongArray.java | 62 |
2 files changed, 35 insertions, 38 deletions
diff --git a/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java index 26670cb1..6374b238 100644 --- a/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java +++ b/core/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java @@ -1189,17 +1189,14 @@ public abstract class ECFieldElement public ECFieldElement sqrt() { - LongArray root = this.x; - if (root.isOne() || root.isZero()) + LongArray x1 = this.x; + if (x1.isOne() || x1.isZero()) { return this; } - for (int i = 1; i < m; ++i) - { - root = root.modSquare(m, ks); - } - return new ECFieldElement.F2m(m, ks, root); + LongArray x2 = x1.modSquareN(m - 1, m, ks); + return new ECFieldElement.F2m(m, ks, x2); } /** diff --git a/core/src/main/java/org/bouncycastle/math/ec/LongArray.java b/core/src/main/java/org/bouncycastle/math/ec/LongArray.java index 34881ec1..e2fdf090 100644 --- a/core/src/main/java/org/bouncycastle/math/ec/LongArray.java +++ b/core/src/main/java/org/bouncycastle/math/ec/LongArray.java @@ -1524,37 +1524,37 @@ class LongArray 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]; -// System.arraycopy(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]; + System.arraycopy(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); + } + } private static void interleave(long[] x, int xOff, long[] z, int zOff, int count, int width) { |