Optimize sqrt() for custom secp384r1

1 files changed, 58 insertions, 2 deletions

diff --git a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1FieldElement.java b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1FieldElement.java
index 4f5f42c3..2615038a 100644
--- a/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1FieldElement.java
+++ b/core/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1FieldElement.java
@@ -128,8 +128,64 @@ public class SecP384R1FieldElement extends ECFieldElement
      */
     public ECFieldElement sqrt()
     {
-        ECFieldElement root = new ECFieldElement.Fp(Q, toBigInteger()).sqrt();
-        return root == null ? null : new SecP384R1FieldElement(root.toBigInteger());
+        // Raise this element to the exponent 2^382 - 2^126 - 2^94 + 2^30
+
+        int[] x1 = this.x;
+        if (Nat.isZero(12, x1) || Nat.isOne(12, x1))
+        {
+            return this;
+        }
+
+        int[] t1 = Nat.create(12);
+        int[] t2 = Nat.create(12);
+        int[] t3 = Nat.create(12);
+        int[] t4 = Nat.create(12);
+
+        SecP384R1Field.square(x1, t1);
+        SecP384R1Field.multiply(t1, x1, t1);
+
+        SecP384R1Field.squareN(t1, 2, t2);
+        SecP384R1Field.multiply(t2, t1, t2);
+
+        SecP384R1Field.square(t2, t2);
+        SecP384R1Field.multiply(t2, x1, t2);
+
+        SecP384R1Field.squareN(t2, 5, t3);
+        SecP384R1Field.multiply(t3, t2, t3);
+
+        SecP384R1Field.squareN(t3, 5, t4);
+        SecP384R1Field.multiply(t4, t2, t4);
+
+        SecP384R1Field.squareN(t4, 15, t2);
+        SecP384R1Field.multiply(t2, t4, t2);
+
+        SecP384R1Field.squareN(t2, 2, t3);
+        SecP384R1Field.multiply(t1, t3, t1);
+
+        SecP384R1Field.squareN(t3, 28, t3);
+        SecP384R1Field.multiply(t2, t3, t2);
+
+        SecP384R1Field.squareN(t2, 60, t3);
+        SecP384R1Field.multiply(t3, t2, t3);
+
+        int[] r = t2;
+
+        SecP384R1Field.squareN(t3, 120, r);
+        SecP384R1Field.multiply(r, t3, r);
+
+        SecP384R1Field.squareN(r, 15, r);
+        SecP384R1Field.multiply(r, t4, r);
+
+        SecP384R1Field.squareN(r, 33, r);
+        SecP384R1Field.multiply(r, t1, r);
+
+        SecP384R1Field.squareN(r, 64, r);
+        SecP384R1Field.multiply(r, x1, r);
+
+        SecP384R1Field.squareN(r, 30, t1);
+        SecP384R1Field.square(t1, t2);
+
+        return Nat.eq(12, x1, t2) ? new SecP384R1FieldElement(t1) : null;
     }
 
     public boolean equals(Object other)