Take advantage of special prime modulus to optimize sqrt

2 files changed, 97 insertions, 4 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java
index 57828917..0a874767 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java
@@ -128,8 +128,67 @@ public class SecP256K1FieldElement extends ECFieldElement
      */
     public ECFieldElement sqrt()
     {
-        ECFieldElement root = new ECFieldElement.Fp(Q, toBigInteger()).sqrt();
-        return root == null ? null : new SecP256K1FieldElement(root.toBigInteger());
+        /*
+         * Raise this element to the exponent 2^254 - 2^30 - 2^7 - 2^6 - 2^5 - 2^4 - 2^2
+         * 
+         * Breaking up the exponent's binary representation into "repunits", we get:
+         * { 223 1s } { 1 0s } { 22 1s } { 4 0s } { 2 1s } { 2 0s}
+         * 
+         * Therefore we need an addition chain containing 2, 22, 223 (the lengths of the repunits)
+         * We use: 1, [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223]
+         */
+
+        int[] x1 = this.x;
+        if (Nat256.isZero(x1) || Nat256.isOne(x1))
+        {
+            return this;
+        }
+
+        int[] x2 = Nat256.create();
+        SecP256K1Field.square(x1, x2);
+        SecP256K1Field.multiply(x2, x1, x2);
+        int[] x3 = Nat256.create();
+        SecP256K1Field.square(x2, x3);
+        SecP256K1Field.multiply(x3, x1, x3);
+        int[] x6 = Nat256.create();
+        SecP256K1Field.squareN(x3, 3, x6);
+        SecP256K1Field.multiply(x6, x3, x6);
+        int[] x9 = x6;
+        SecP256K1Field.squareN(x6, 3, x9);
+        SecP256K1Field.multiply(x9, x3, x9);
+        int[] x11 = x9;
+        SecP256K1Field.squareN(x9, 2, x11);
+        SecP256K1Field.multiply(x11, x2, x11);
+        int[] x22 = Nat256.create();
+        SecP256K1Field.squareN(x11, 11, x22);
+        SecP256K1Field.multiply(x22, x11, x22);
+        int[] x44 = x11;
+        SecP256K1Field.squareN(x22, 22, x44);
+        SecP256K1Field.multiply(x44, x22, x44);
+        int[] x88 = Nat256.create();
+        SecP256K1Field.squareN(x44, 44, x88);
+        SecP256K1Field.multiply(x88, x44, x88);
+        int[] x176 = Nat256.create();
+        SecP256K1Field.squareN(x88, 88, x176);
+        SecP256K1Field.multiply(x176, x88, x176);
+        int[] x220 = x88;
+        SecP256K1Field.squareN(x176, 44, x220);
+        SecP256K1Field.multiply(x220, x44, x220);
+        int[] x223 = x44;
+        SecP256K1Field.squareN(x220, 3, x223);
+        SecP256K1Field.multiply(x223, x3, x223);
+
+        int[] t1 = x223;
+        SecP256K1Field.squareN(t1, 23, t1);
+        SecP256K1Field.multiply(t1, x22, t1);
+        SecP256K1Field.squareN(t1, 6, t1);
+        SecP256K1Field.multiply(t1, x2, t1);
+        SecP256K1Field.squareN(t1, 2, t1);
+
+        int[] t2 = x2;
+        SecP256K1Field.square(t1, t2);
+
+        return Arrays.areEqual(x1, t2) ? new SecP256K1FieldElement(t1) : null;        
     }
 
     public boolean equals(Object other)
diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java
index 03895cfb..f9eaff0e 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java
@@ -129,8 +129,42 @@ public class SecP256R1FieldElement extends ECFieldElement
      */
     public ECFieldElement sqrt()
     {
-        ECFieldElement root = new ECFieldElement.Fp(Q, toBigInteger()).sqrt();
-        return root == null ? null : new SecP256R1FieldElement(root.toBigInteger());
+        // Raise this element to the exponent 2^254 - 2^222 + 2^190 + 2^94
+
+        int[] x1 = this.x;
+        if (Nat256.isZero(x1) || Nat256.isOne(x1))
+        {
+            return this;
+        }
+
+        int[] t1 = Nat256.create();
+        int[] t2 = Nat256.create();
+
+        SecP256R1Field.square(x1, t1);
+        SecP256R1Field.multiply(t1, x1, t1);
+
+        SecP256R1Field.squareN(t1, 2, t2);
+        SecP256R1Field.multiply(t2, t1, t2);
+
+        SecP256R1Field.squareN(t2, 4, t1);
+        SecP256R1Field.multiply(t1, t2, t1);
+
+        SecP256R1Field.squareN(t1, 8, t2);
+        SecP256R1Field.multiply(t2, t1, t2);
+
+        SecP256R1Field.squareN(t2, 16, t1);
+        SecP256R1Field.multiply(t1, t2, t1);
+
+        SecP256R1Field.squareN(t1, 32, t1);
+        SecP256R1Field.multiply(t1, x1, t1);
+
+        SecP256R1Field.squareN(t1, 96, t1);
+        SecP256R1Field.multiply(t1, x1, t1);
+
+        SecP256R1Field.squareN(t1, 94, t1);
+        SecP256R1Field.square(t1, t2);
+
+        return Arrays.areEqual(x1, t2) ? new SecP256R1FieldElement(t1) : null;
     }
 
     public boolean equals(Object other)