summaryrefslogtreecommitdiffstats
path: root/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
diff options
context:
space:
mode:
Diffstat (limited to 'bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java')
-rw-r--r--bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java871
1 files changed, 217 insertions, 654 deletions
diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
index 87608eb..5943882 100644
--- a/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
+++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java
@@ -3,6 +3,8 @@ package org.bouncycastle.math.ec;
import java.math.BigInteger;
import java.util.Random;
+import org.bouncycastle.math.raw.Mod;
+import org.bouncycastle.math.raw.Nat;
import org.bouncycastle.util.Arrays;
import org.bouncycastle.util.BigIntegers;
@@ -27,11 +29,36 @@ public abstract class ECFieldElement
return toBigInteger().bitLength();
}
+ public boolean isOne()
+ {
+ return bitLength() == 1;
+ }
+
public boolean isZero()
{
return 0 == toBigInteger().signum();
}
+ public ECFieldElement multiplyMinusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y)
+ {
+ return multiply(b).subtract(x.multiply(y));
+ }
+
+ public ECFieldElement multiplyPlusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y)
+ {
+ return multiply(b).add(x.multiply(y));
+ }
+
+ public ECFieldElement squareMinusProduct(ECFieldElement x, ECFieldElement y)
+ {
+ return square().subtract(x.multiply(y));
+ }
+
+ public ECFieldElement squarePlusProduct(ECFieldElement x, ECFieldElement y)
+ {
+ return square().add(x.multiply(y));
+ }
+
public boolean testBitZero()
{
return toBigInteger().testBit(0);
@@ -51,42 +78,10 @@ public abstract class ECFieldElement
{
BigInteger q, r, x;
-// static int[] calculateNaf(BigInteger p)
-// {
-// int[] naf = WNafUtil.generateCompactNaf(p);
-//
-// int bit = 0;
-// for (int i = 0; i < naf.length; ++i)
-// {
-// int ni = naf[i];
-// int digit = ni >> 16, zeroes = ni & 0xFFFF;
-//
-// bit += zeroes;
-// naf[i] = digit < 0 ? ~bit : bit;
-// ++bit;
-// }
-//
-// int last = naf.length - 1;
-// if (last > 0 && last <= 16)
-// {
-// int top = naf[last], top2 = naf[last - 1];
-// if (top2 < 0)
-// {
-// top2 = ~top2;
-// }
-// if (top - top2 >= 64)
-// {
-// return naf;
-// }
-// }
-//
-// return null;
-// }
-
static BigInteger calculateResidue(BigInteger p)
{
int bitLength = p.bitLength();
- if (bitLength > 128)
+ if (bitLength >= 96)
{
BigInteger firstWord = p.shiftRight(bitLength - 64);
if (firstWord.longValue() == -1L)
@@ -159,13 +154,7 @@ public abstract class ECFieldElement
public ECFieldElement subtract(ECFieldElement b)
{
- BigInteger x2 = b.toBigInteger();
- BigInteger x3 = x.subtract(x2);
- if (x3.signum() < 0)
- {
- x3 = x3.add(q);
- }
- return new Fp(q, r, x3);
+ return new Fp(q, r, modSubtract(x, b.toBigInteger()));
}
public ECFieldElement multiply(ECFieldElement b)
@@ -173,27 +162,30 @@ public abstract class ECFieldElement
return new Fp(q, r, modMult(x, b.toBigInteger()));
}
+ public ECFieldElement multiplyMinusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y)
+ {
+ BigInteger ax = this.x, bx = b.toBigInteger(), xx = x.toBigInteger(), yx = y.toBigInteger();
+ BigInteger ab = ax.multiply(bx);
+ BigInteger xy = xx.multiply(yx);
+ return new Fp(q, r, modReduce(ab.subtract(xy)));
+ }
+
+ public ECFieldElement multiplyPlusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y)
+ {
+ BigInteger ax = this.x, bx = b.toBigInteger(), xx = x.toBigInteger(), yx = y.toBigInteger();
+ BigInteger ab = ax.multiply(bx);
+ BigInteger xy = xx.multiply(yx);
+ return new Fp(q, r, modReduce(ab.add(xy)));
+ }
+
public ECFieldElement divide(ECFieldElement b)
{
- return new Fp(q, modMult(x, b.toBigInteger().modInverse(q)));
+ return new Fp(q, r, modMult(x, modInverse(b.toBigInteger())));
}
public ECFieldElement negate()
{
- BigInteger x2;
- if (x.signum() == 0)
- {
- x2 = x;
- }
- else if (ONE.equals(r))
- {
- x2 = q.xor(x);
- }
- else
- {
- x2 = q.subtract(x);
- }
- return new Fp(q, r, x2);
+ return x.signum() == 0 ? this : new Fp(q, r, q.subtract(x));
}
public ECFieldElement square()
@@ -201,10 +193,26 @@ public abstract class ECFieldElement
return new Fp(q, r, modMult(x, x));
}
+ public ECFieldElement squareMinusProduct(ECFieldElement x, ECFieldElement y)
+ {
+ BigInteger ax = this.x, xx = x.toBigInteger(), yx = y.toBigInteger();
+ BigInteger aa = ax.multiply(ax);
+ BigInteger xy = xx.multiply(yx);
+ return new Fp(q, r, modReduce(aa.subtract(xy)));
+ }
+
+ public ECFieldElement squarePlusProduct(ECFieldElement x, ECFieldElement y)
+ {
+ BigInteger ax = this.x, xx = x.toBigInteger(), yx = y.toBigInteger();
+ BigInteger aa = ax.multiply(ax);
+ BigInteger xy = xx.multiply(yx);
+ return new Fp(q, r, modReduce(aa.add(xy)));
+ }
+
public ECFieldElement invert()
{
// TODO Modular inversion can be faster for a (Generalized) Mersenne Prime.
- return new Fp(q, r, x.modInverse(q));
+ return new Fp(q, r, modInverse(x));
}
// D.1.4 91
@@ -214,6 +222,11 @@ public abstract class ECFieldElement
*/
public ECFieldElement sqrt()
{
+ if (this.isZero() || this.isOne()) // earlier JDK compatibility
+ {
+ return this;
+ }
+
if (!q.testBit(0))
{
throw new RuntimeException("not done yet");
@@ -221,29 +234,44 @@ public abstract class ECFieldElement
// note: even though this class implements ECConstants don't be tempted to
// remove the explicit declaration, some J2ME environments don't cope.
- // p mod 4 == 3
- if (q.testBit(1))
+
+ if (q.testBit(1)) // q == 4m + 3
+ {
+ BigInteger e = q.shiftRight(2).add(ECConstants.ONE);
+ return checkSqrt(new Fp(q, r, x.modPow(e, q)));
+ }
+
+ if (q.testBit(2)) // q == 8m + 5
{
- // z = g^(u+1) + p, p = 4u + 3
- ECFieldElement z = new Fp(q, r, x.modPow(q.shiftRight(2).add(ECConstants.ONE), q));
+ BigInteger t1 = x.modPow(q.shiftRight(3), q);
+ BigInteger t2 = modMult(t1, x);
+ BigInteger t3 = modMult(t2, t1);
+
+ if (t3.equals(ECConstants.ONE))
+ {
+ return checkSqrt(new Fp(q, r, t2));
+ }
+
+ // TODO This is constant and could be precomputed
+ BigInteger t4 = ECConstants.TWO.modPow(q.shiftRight(2), q);
- return z.square().equals(this) ? z : null;
+ BigInteger y = modMult(t2, t4);
+
+ return checkSqrt(new Fp(q, r, y));
}
- // p mod 4 == 1
- BigInteger qMinusOne = q.subtract(ECConstants.ONE);
+ // q == 8m + 1
- BigInteger legendreExponent = qMinusOne.shiftRight(1);
+ BigInteger legendreExponent = q.shiftRight(1);
if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
{
return null;
}
- BigInteger u = qMinusOne.shiftRight(2);
- BigInteger k = u.shiftLeft(1).add(ECConstants.ONE);
+ BigInteger X = this.x;
+ BigInteger fourX = modDouble(modDouble(X));
- BigInteger Q = this.x;
- BigInteger fourQ = modDouble(modDouble(Q));
+ BigInteger k = legendreExponent.add(ECConstants.ONE), qMinusOne = q.subtract(ECConstants.ONE);
BigInteger U, V;
Random rand = new Random();
@@ -255,94 +283,39 @@ public abstract class ECFieldElement
P = new BigInteger(q.bitLength(), rand);
}
while (P.compareTo(q) >= 0
- || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, q).equals(qMinusOne)));
+ || !modReduce(P.multiply(P).subtract(fourX)).modPow(legendreExponent, q).equals(qMinusOne));
- BigInteger[] result = lucasSequence(P, Q, k);
+ BigInteger[] result = lucasSequence(P, X, k);
U = result[0];
V = result[1];
- if (modMult(V, V).equals(fourQ))
+ if (modMult(V, V).equals(fourX))
{
- // Integer division by 2, mod q
- if (V.testBit(0))
- {
- V = V.add(q);
- }
-
- V = V.shiftRight(1);
-
- //assert V.multiply(V).mod(q).equals(x);
-
- return new ECFieldElement.Fp(q, r, V);
+ return new ECFieldElement.Fp(q, r, modHalfAbs(V));
}
}
while (U.equals(ECConstants.ONE) || U.equals(qMinusOne));
return null;
-
-// BigInteger qMinusOne = q.subtract(ECConstants.ONE);
-// BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO);
-// if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
-// {
-// return null;
-// }
-//
-// Random rand = new Random();
-// BigInteger fourX = x.shiftLeft(2);
-//
-// BigInteger r;
-// do
-// {
-// r = new BigInteger(q.bitLength(), rand);
-// }
-// while (r.compareTo(q) >= 0
-// || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne)));
-//
-// BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR);
-// BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR);
-//
-// BigInteger wOne = WOne(r, x, q);
-// BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q);
-// BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r);
-//
-// BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q)
-// .multiply(x).mod(q)
-// .multiply(wSum).mod(q);
-//
-// return new Fp(q, root);
}
-// private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p)
-// {
-// if (n.equals(ECConstants.ONE))
-// {
-// return wOne;
-// }
-// boolean isEven = !n.testBit(0);
-// n = n.shiftRight(1);//divide(ECConstants.TWO);
-// if (isEven)
-// {
-// BigInteger w = W(n, wOne, p);
-// return w.multiply(w).subtract(ECConstants.TWO).mod(p);
-// }
-// BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p);
-// BigInteger w2 = W(n, wOne, p);
-// return w1.multiply(w2).subtract(wOne).mod(p);
-// }
-//
-// private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p)
-// {
-// return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p);
-// }
+ private ECFieldElement checkSqrt(ECFieldElement z)
+ {
+ return z.square().equals(this) ? z : null;
+ }
private BigInteger[] lucasSequence(
BigInteger P,
BigInteger Q,
BigInteger k)
{
+ // TODO Research and apply "common-multiplicand multiplication here"
+
int n = k.bitLength();
int s = k.getLowestSetBit();
+ // assert k.testBit(s);
+
BigInteger Uh = ECConstants.ONE;
BigInteger Vl = ECConstants.TWO;
BigInteger Vh = P;
@@ -405,6 +378,35 @@ public abstract class ECFieldElement
return _2x;
}
+ protected BigInteger modHalf(BigInteger x)
+ {
+ if (x.testBit(0))
+ {
+ x = q.add(x);
+ }
+ return x.shiftRight(1);
+ }
+
+ protected BigInteger modHalfAbs(BigInteger x)
+ {
+ if (x.testBit(0))
+ {
+ x = q.subtract(x);
+ }
+ return x.shiftRight(1);
+ }
+
+ protected BigInteger modInverse(BigInteger x)
+ {
+ int bits = getFieldSize();
+ int len = (bits + 31) >> 5;
+ int[] p = Nat.fromBigInteger(bits, q);
+ int[] n = Nat.fromBigInteger(bits, x);
+ int[] z = Nat.create(len);
+ Mod.invert(p, n, z);
+ return Nat.toBigInteger(len, z);
+ }
+
protected BigInteger modMult(BigInteger x1, BigInteger x2)
{
return modReduce(x1.multiply(x2));
@@ -412,44 +414,20 @@ public abstract class ECFieldElement
protected BigInteger modReduce(BigInteger x)
{
-// if (naf != null)
-// {
-// int last = naf.length - 1;
-// int bits = naf[last];
-// while (x.bitLength() > (bits + 1))
-// {
-// BigInteger u = x.shiftRight(bits);
-// BigInteger v = x.subtract(u.shiftLeft(bits));
-//
-// x = v;
-//
-// for (int i = 0; i < last; ++i)
-// {
-// int ni = naf[i];
-// if (ni < 0)
-// {
-// x = x.add(u.shiftLeft(~ni));
-// }
-// else
-// {
-// x = x.subtract(u.shiftLeft(ni));
-// }
-// }
-// }
-// while (x.compareTo(q) >= 0)
-// {
-// x = x.subtract(q);
-// }
-// }
-// else
if (r != null)
{
+ boolean negative = x.signum() < 0;
+ if (negative)
+ {
+ x = x.abs();
+ }
int qLen = q.bitLength();
+ boolean rIsOne = r.equals(ECConstants.ONE);
while (x.bitLength() > (qLen + 1))
{
BigInteger u = x.shiftRight(qLen);
BigInteger v = x.subtract(u.shiftLeft(qLen));
- if (!r.equals(ONE))
+ if (!rIsOne)
{
u = u.multiply(r);
}
@@ -459,6 +437,10 @@ public abstract class ECFieldElement
{
x = x.subtract(q);
}
+ if (negative && x.signum() != 0)
+ {
+ x = q.subtract(x);
+ }
}
else
{
@@ -467,6 +449,16 @@ public abstract class ECFieldElement
return x;
}
+ protected BigInteger modSubtract(BigInteger x1, BigInteger x2)
+ {
+ BigInteger x3 = x1.subtract(x2);
+ if (x3.signum() < 0)
+ {
+ x3 = x3.add(q);
+ }
+ return x3;
+ }
+
public boolean equals(Object other)
{
if (other == this)
@@ -489,467 +481,6 @@ public abstract class ECFieldElement
}
}
-// /**
-// * Class representing the Elements of the finite field
-// * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
-// * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial
-// * basis representations are supported. Gaussian normal basis (GNB)
-// * representation is not supported.
-// */
-// public static class F2m extends ECFieldElement
-// {
-// BigInteger x;
-//
-// /**
-// * Indicates gaussian normal basis representation (GNB). Number chosen
-// * according to X9.62. GNB is not implemented at present.
-// */
-// public static final int GNB = 1;
-//
-// /**
-// * Indicates trinomial basis representation (TPB). Number chosen
-// * according to X9.62.
-// */
-// public static final int TPB = 2;
-//
-// /**
-// * Indicates pentanomial basis representation (PPB). Number chosen
-// * according to X9.62.
-// */
-// public static final int PPB = 3;
-//
-// /**
-// * TPB or PPB.
-// */
-// private int representation;
-//
-// /**
-// * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
-// */
-// private int m;
-//
-// /**
-// * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
-// * x<sup>k</sup> + 1</code> represents the reduction polynomial
-// * <code>f(z)</code>.<br>
-// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// private int k1;
-//
-// /**
-// * TPB: Always set to <code>0</code><br>
-// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// private int k2;
-//
-// /**
-// * TPB: Always set to <code>0</code><br>
-// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// private int k3;
-//
-// /**
-// * Constructor for PPB.
-// * @param m The exponent <code>m</code> of
-// * <code>F<sub>2<sup>m</sup></sub></code>.
-// * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.
-// * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.
-// * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.
-// * @param x The BigInteger representing the value of the field element.
-// */
-// public F2m(
-// int m,
-// int k1,
-// int k2,
-// int k3,
-// BigInteger x)
-// {
-//// super(x);
-// this.x = x;
-//
-// if ((k2 == 0) && (k3 == 0))
-// {
-// this.representation = TPB;
-// }
-// else
-// {
-// if (k2 >= k3)
-// {
-// throw new IllegalArgumentException(
-// "k2 must be smaller than k3");
-// }
-// if (k2 <= 0)
-// {
-// throw new IllegalArgumentException(
-// "k2 must be larger than 0");
-// }
-// this.representation = PPB;
-// }
-//
-// if (x.signum() < 0)
-// {
-// throw new IllegalArgumentException("x value cannot be negative");
-// }
-//
-// this.m = m;
-// this.k1 = k1;
-// this.k2 = k2;
-// this.k3 = k3;
-// }
-//
-// /**
-// * Constructor for TPB.
-// * @param m The exponent <code>m</code> of
-// * <code>F<sub>2<sup>m</sup></sub></code>.
-// * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
-// * x<sup>k</sup> + 1</code> represents the reduction
-// * polynomial <code>f(z)</code>.
-// * @param x The BigInteger representing the value of the field element.
-// */
-// public F2m(int m, int k, BigInteger x)
-// {
-// // Set k1 to k, and set k2 and k3 to 0
-// this(m, k, 0, 0, x);
-// }
-//
-// public BigInteger toBigInteger()
-// {
-// return x;
-// }
-//
-// public String getFieldName()
-// {
-// return "F2m";
-// }
-//
-// public int getFieldSize()
-// {
-// return m;
-// }
-//
-// /**
-// * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
-// * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
-// * (having the same representation).
-// * @param a field element.
-// * @param b field element to be compared.
-// * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
-// * are not elements of the same field
-// * <code>F<sub>2<sup>m</sup></sub></code> (having the same
-// * representation).
-// */
-// public static void checkFieldElements(
-// ECFieldElement a,
-// ECFieldElement b)
-// {
-// if ((!(a instanceof F2m)) || (!(b instanceof F2m)))
-// {
-// throw new IllegalArgumentException("Field elements are not "
-// + "both instances of ECFieldElement.F2m");
-// }
-//
-// if ((a.toBigInteger().signum() < 0) || (b.toBigInteger().signum() < 0))
-// {
-// throw new IllegalArgumentException(
-// "x value may not be negative");
-// }
-//
-// ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a;
-// ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b;
-//
-// if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
-// || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3))
-// {
-// throw new IllegalArgumentException("Field elements are not "
-// + "elements of the same field F2m");
-// }
-//
-// if (aF2m.representation != bF2m.representation)
-// {
-// // Should never occur
-// throw new IllegalArgumentException(
-// "One of the field "
-// + "elements are not elements has incorrect representation");
-// }
-// }
-//
-// /**
-// * Computes <code>z * a(z) mod f(z)</code>, where <code>f(z)</code> is
-// * the reduction polynomial of <code>this</code>.
-// * @param a The polynomial <code>a(z)</code> to be multiplied by
-// * <code>z mod f(z)</code>.
-// * @return <code>z * a(z) mod f(z)</code>
-// */
-// private BigInteger multZModF(final BigInteger a)
-// {
-// // Left-shift of a(z)
-// BigInteger az = a.shiftLeft(1);
-// if (az.testBit(this.m))
-// {
-// // If the coefficient of z^m in a(z) equals 1, reduction
-// // modulo f(z) is performed: Add f(z) to to a(z):
-// // Step 1: Unset mth coeffient of a(z)
-// az = az.clearBit(this.m);
-//
-// // Step 2: Add r(z) to a(z), where r(z) is defined as
-// // f(z) = z^m + r(z), and k1, k2, k3 are the positions of
-// // the non-zero coefficients in r(z)
-// az = az.flipBit(0);
-// az = az.flipBit(this.k1);
-// if (this.representation == PPB)
-// {
-// az = az.flipBit(this.k2);
-// az = az.flipBit(this.k3);
-// }
-// }
-// return az;
-// }
-//
-// public ECFieldElement add(final ECFieldElement b)
-// {
-// // No check performed here for performance reasons. Instead the
-// // elements involved are checked in ECPoint.F2m
-// // checkFieldElements(this, b);
-// if (b.toBigInteger().signum() == 0)
-// {
-// return this;
-// }
-//
-// return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.toBigInteger()));
-// }
-//
-// public ECFieldElement subtract(final ECFieldElement b)
-// {
-// // Addition and subtraction are the same in F2m
-// return add(b);
-// }
-//
-//
-// public ECFieldElement multiply(final ECFieldElement b)
-// {
-// // Left-to-right shift-and-add field multiplication in F2m
-// // Input: Binary polynomials a(z) and b(z) of degree at most m-1
-// // Output: c(z) = a(z) * b(z) mod f(z)
-//
-// // No check performed here for performance reasons. Instead the
-// // elements involved are checked in ECPoint.F2m
-// // checkFieldElements(this, b);
-// final BigInteger az = this.x;
-// BigInteger bz = b.toBigInteger();
-// BigInteger cz;
-//
-// // Compute c(z) = a(z) * b(z) mod f(z)
-// if (az.testBit(0))
-// {
-// cz = bz;
-// }
-// else
-// {
-// cz = ECConstants.ZERO;
-// }
-//
-// for (int i = 1; i < this.m; i++)
-// {
-// // b(z) := z * b(z) mod f(z)
-// bz = multZModF(bz);
-//
-// if (az.testBit(i))
-// {
-// // If the coefficient of x^i in a(z) equals 1, b(z) is added
-// // to c(z)
-// cz = cz.xor(bz);
-// }
-// }
-// return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz);
-// }
-//
-//
-// public ECFieldElement divide(final ECFieldElement b)
-// {
-// // There may be more efficient implementations
-// ECFieldElement bInv = b.invert();
-// return multiply(bInv);
-// }
-//
-// public ECFieldElement negate()
-// {
-// // -x == x holds for all x in F2m
-// return this;
-// }
-//
-// public ECFieldElement square()
-// {
-// // Naive implementation, can probably be speeded up using modular
-// // reduction
-// return multiply(this);
-// }
-//
-// public ECFieldElement invert()
-// {
-// // Inversion in F2m using the extended Euclidean algorithm
-// // Input: A nonzero polynomial a(z) of degree at most m-1
-// // Output: a(z)^(-1) mod f(z)
-//
-// // u(z) := a(z)
-// BigInteger uz = this.x;
-// if (uz.signum() <= 0)
-// {
-// throw new ArithmeticException("x is zero or negative, " +
-// "inversion is impossible");
-// }
-//
-// // v(z) := f(z)
-// BigInteger vz = ECConstants.ZERO.setBit(m);
-// vz = vz.setBit(0);
-// vz = vz.setBit(this.k1);
-// if (this.representation == PPB)
-// {
-// vz = vz.setBit(this.k2);
-// vz = vz.setBit(this.k3);
-// }
-//
-// // g1(z) := 1, g2(z) := 0
-// BigInteger g1z = ECConstants.ONE;
-// BigInteger g2z = ECConstants.ZERO;
-//
-// // while u != 1
-// while (!(uz.equals(ECConstants.ZERO)))
-// {
-// // j := deg(u(z)) - deg(v(z))
-// int j = uz.bitLength() - vz.bitLength();
-//
-// // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
-// if (j < 0)
-// {
-// final BigInteger uzCopy = uz;
-// uz = vz;
-// vz = uzCopy;
-//
-// final BigInteger g1zCopy = g1z;
-// g1z = g2z;
-// g2z = g1zCopy;
-//
-// j = -j;
-// }
-//
-// // u(z) := u(z) + z^j * v(z)
-// // Note, that no reduction modulo f(z) is required, because
-// // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
-// // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
-// // = deg(u(z))
-// uz = uz.xor(vz.shiftLeft(j));
-//
-// // g1(z) := g1(z) + z^j * g2(z)
-// g1z = g1z.xor(g2z.shiftLeft(j));
-//// if (g1z.bitLength() > this.m) {
-//// throw new ArithmeticException(
-//// "deg(g1z) >= m, g1z = " + g1z.toString(16));
-//// }
-// }
-// return new ECFieldElement.F2m(
-// this.m, this.k1, this.k2, this.k3, g2z);
-// }
-//
-// public ECFieldElement sqrt()
-// {
-// throw new RuntimeException("Not implemented");
-// }
-//
-// /**
-// * @return the representation of the field
-// * <code>F<sub>2<sup>m</sup></sub></code>, either of
-// * TPB (trinomial
-// * basis representation) or
-// * PPB (pentanomial
-// * basis representation).
-// */
-// public int getRepresentation()
-// {
-// return this.representation;
-// }
-//
-// /**
-// * @return the degree <code>m</code> of the reduction polynomial
-// * <code>f(z)</code>.
-// */
-// public int getM()
-// {
-// return this.m;
-// }
-//
-// /**
-// * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
-// * x<sup>k</sup> + 1</code> represents the reduction polynomial
-// * <code>f(z)</code>.<br>
-// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// public int getK1()
-// {
-// return this.k1;
-// }
-//
-// /**
-// * @return TPB: Always returns <code>0</code><br>
-// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// public int getK2()
-// {
-// return this.k2;
-// }
-//
-// /**
-// * @return TPB: Always set to <code>0</code><br>
-// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// public int getK3()
-// {
-// return this.k3;
-// }
-//
-// public boolean equals(Object anObject)
-// {
-// if (anObject == this)
-// {
-// return true;
-// }
-//
-// if (!(anObject instanceof ECFieldElement.F2m))
-// {
-// return false;
-// }
-//
-// ECFieldElement.F2m b = (ECFieldElement.F2m)anObject;
-//
-// return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2)
-// && (this.k3 == b.k3)
-// && (this.representation == b.representation)
-// && (this.x.equals(b.x)));
-// }
-//
-// public int hashCode()
-// {
-// return x.hashCode() ^ m ^ k1 ^ k2 ^ k3;
-// }
-// }
-
/**
* Class representing the Elements of the finite field
* <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
@@ -987,32 +518,6 @@ public abstract class ECFieldElement
*/
private int m;
-// /**
-// * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
-// * x<sup>k</sup> + 1</code> represents the reduction polynomial
-// * <code>f(z)</code>.<br>
-// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// private int k1;
-//
-// /**
-// * TPB: Always set to <code>0</code><br>
-// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// private int k2;
-//
-// /**
-// * TPB: Always set to <code>0</code><br>
-// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
-// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
-// * represents the reduction polynomial <code>f(z)</code>.<br>
-// */
-// private int k3;
-
private int[] ks;
/**
@@ -1097,6 +602,11 @@ public abstract class ECFieldElement
return x.degree();
}
+ public boolean isOne()
+ {
+ return x.isOne();
+ }
+
public boolean isZero()
{
return x.isZero();
@@ -1192,6 +702,29 @@ public abstract class ECFieldElement
return new F2m(m, ks, x.modMultiply(((F2m)b).x, m, ks));
}
+ public ECFieldElement multiplyMinusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y)
+ {
+ return multiplyPlusProduct(b, x, y);
+ }
+
+ public ECFieldElement multiplyPlusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y)
+ {
+ LongArray ax = this.x, bx = ((F2m)b).x, xx = ((F2m)x).x, yx = ((F2m)y).x;
+
+ LongArray ab = ax.multiply(bx, m, ks);
+ LongArray xy = xx.multiply(yx, m, ks);
+
+ if (ab == ax || ab == bx)
+ {
+ ab = (LongArray)ab.clone();
+ }
+
+ ab.addShiftedByWords(xy, 0);
+ ab.reduce(m, ks);
+
+ return new F2m(m, ks, ab);
+ }
+
public ECFieldElement divide(final ECFieldElement b)
{
// There may be more efficient implementations
@@ -1210,6 +743,29 @@ public abstract class ECFieldElement
return new F2m(m, ks, x.modSquare(m, ks));
}
+ public ECFieldElement squareMinusProduct(ECFieldElement x, ECFieldElement y)
+ {
+ return squarePlusProduct(x, y);
+ }
+
+ public ECFieldElement squarePlusProduct(ECFieldElement x, ECFieldElement y)
+ {
+ LongArray ax = this.x, xx = ((F2m)x).x, yx = ((F2m)y).x;
+
+ LongArray aa = ax.square(m, ks);
+ LongArray xy = xx.multiply(yx, m, ks);
+
+ if (aa == ax)
+ {
+ aa = (LongArray)aa.clone();
+ }
+
+ aa.addShiftedByWords(xy, 0);
+ aa.reduce(m, ks);
+
+ return new F2m(m, ks, aa);
+ }
+
public ECFieldElement invert()
{
return new ECFieldElement.F2m(this.m, this.ks, this.x.modInverse(m, ks));
@@ -1217,7 +773,14 @@ public abstract class ECFieldElement
public ECFieldElement sqrt()
{
- throw new RuntimeException("Not implemented");
+ LongArray x1 = this.x;
+ if (x1.isOne() || x1.isZero())
+ {
+ return this;
+ }
+
+ LongArray x2 = x1.modSquareN(m - 1, m, ks);
+ return new ECFieldElement.F2m(m, ks, x2);
}
/**
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-29 01:53:13 +0000