18212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrompackage org.bouncycastle.math.ec; 28212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 38212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromimport java.math.BigInteger; 48212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromimport java.util.Random; 58212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 65db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootimport org.bouncycastle.util.Arrays; 75db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootimport org.bouncycastle.util.BigIntegers; 85db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 98212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrompublic abstract class ECFieldElement 108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom implements ECConstants 118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom{ 128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract BigInteger toBigInteger(); 138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract String getFieldName(); 148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract int getFieldSize(); 158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement add(ECFieldElement b); 165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public abstract ECFieldElement addOne(); 178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement subtract(ECFieldElement b); 188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement multiply(ECFieldElement b); 198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement divide(ECFieldElement b); 208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement negate(); 218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement square(); 228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement invert(); 238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement sqrt(); 248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public int bitLength() 265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return toBigInteger().bitLength(); 285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public boolean isZero() 315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return 0 == toBigInteger().signum(); 335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public boolean testBitZero() 365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return toBigInteger().testBit(0); 385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public String toString() 418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this.toBigInteger().toString(16); 435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public byte[] getEncoded() 465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return BigIntegers.asUnsignedByteArray((getFieldSize() + 7) / 8, toBigInteger()); 488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static class Fp extends ECFieldElement 518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger q, r, x; 538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// static int[] calculateNaf(BigInteger p) 555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int[] naf = WNafUtil.generateCompactNaf(p); 575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int bit = 0; 595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (int i = 0; i < naf.length; ++i) 605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int ni = naf[i]; 625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int digit = ni >> 16, zeroes = ni & 0xFFFF; 635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// bit += zeroes; 655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// naf[i] = digit < 0 ? ~bit : bit; 665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// ++bit; 675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int last = naf.length - 1; 705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (last > 0 && last <= 16) 715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int top = naf[last], top2 = naf[last - 1]; 735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (top2 < 0) 745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// top2 = ~top2; 765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (top - top2 >= 64) 785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return naf; 805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return null; 845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root static BigInteger calculateResidue(BigInteger p) 875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bitLength = p.bitLength(); 895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (bitLength > 128) 905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger firstWord = p.shiftRight(bitLength - 64); 925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (firstWord.longValue() == -1L) 935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return ONE.shiftLeft(bitLength).subtract(p); 955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return null; 985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /** 1015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * @deprecated Use ECCurve.fromBigInteger to construct field elements 1025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 1038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public Fp(BigInteger q, BigInteger x) 1048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this(q, calculateResidue(q), x); 1065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Fp(BigInteger q, BigInteger r, BigInteger x) 1095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (x == null || x.signum() < 0 || x.compareTo(q) >= 0) 1118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root throw new IllegalArgumentException("x value invalid in Fp field element"); 1138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.q = q; 1165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this.r = r; 1175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this.x = x; 1188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public BigInteger toBigInteger() 1218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return x; 1238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 1268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * return the field name for this field. 1278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 1288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return the string "Fp". 1298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 1308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public String getFieldName() 1318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return "Fp"; 1338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getFieldSize() 1368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q.bitLength(); 1388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public BigInteger getQ() 1418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q; 1438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement add(ECFieldElement b) 1468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new Fp(q, r, modAdd(x, b.toBigInteger())); 1485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public ECFieldElement addOne() 1515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger x2 = x.add(ECConstants.ONE); 1535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (x2.compareTo(q) == 0) 1545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x2 = ECConstants.ZERO; 1565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new Fp(q, r, x2); 1588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement subtract(ECFieldElement b) 1618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger x2 = b.toBigInteger(); 1635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger x3 = x.subtract(x2); 1645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (x3.signum() < 0) 1655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x3 = x3.add(q); 1675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new Fp(q, r, x3); 1698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement multiply(ECFieldElement b) 1728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new Fp(q, r, modMult(x, b.toBigInteger())); 1748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement divide(ECFieldElement b) 1778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new Fp(q, modMult(x, b.toBigInteger().modInverse(q))); 1798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement negate() 1828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger x2; 1845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (x.signum() == 0) 1855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x2 = x; 1875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else if (ONE.equals(r)) 1895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x2 = q.xor(x); 1915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 1935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x2 = q.subtract(x); 1955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 1965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new Fp(q, r, x2); 1978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement square() 2008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new Fp(q, r, modMult(x, x)); 2028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement invert() 2058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // TODO Modular inversion can be faster for a (Generalized) Mersenne Prime. 2075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new Fp(q, r, x.modInverse(q)); 2088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // D.1.4 91 2118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 2128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * return a sqrt root - the routine verifies that the calculation 2138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * returns the right value - if none exists it returns null. 2148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 2158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement sqrt() 2168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!q.testBit(0)) 2188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new RuntimeException("not done yet"); 2208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // note: even though this class implements ECConstants don't be tempted to 2238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // remove the explicit declaration, some J2ME environments don't cope. 2248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // p mod 4 == 3 2258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (q.testBit(1)) 2268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // z = g^(u+1) + p, p = 4u + 3 2285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECFieldElement z = new Fp(q, r, x.modPow(q.shiftRight(2).add(ECConstants.ONE), q)); 2298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return z.square().equals(this) ? z : null; 2318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // p mod 4 == 1 2348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger qMinusOne = q.subtract(ECConstants.ONE); 2358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger legendreExponent = qMinusOne.shiftRight(1); 2378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) 2388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return null; 2408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger u = qMinusOne.shiftRight(2); 2438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger k = u.shiftLeft(1).add(ECConstants.ONE); 2448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Q = this.x; 2465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger fourQ = modDouble(modDouble(Q)); 2478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger U, V; 2498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Random rand = new Random(); 2508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom do 2518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger P; 2538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom do 2548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom P = new BigInteger(q.bitLength(), rand); 2568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (P.compareTo(q) >= 0 2588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, q).equals(qMinusOne))); 2598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger[] result = lucasSequence(P, Q, k); 2618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom U = result[0]; 2628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom V = result[1]; 2638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (modMult(V, V).equals(fourQ)) 2658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Integer division by 2, mod q 2678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (V.testBit(0)) 2688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom V = V.add(q); 2708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom V = V.shiftRight(1); 2738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom //assert V.multiply(V).mod(q).equals(x); 2758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new ECFieldElement.Fp(q, r, V); 2778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (U.equals(ECConstants.ONE) || U.equals(qMinusOne)); 2808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return null; 2828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger qMinusOne = q.subtract(ECConstants.ONE); 2848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO); 2858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) 2868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 2878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return null; 2888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 2898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 2908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// Random rand = new Random(); 2918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger fourX = x.shiftLeft(2); 2928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 2938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger r; 2948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// do 2958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 2968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// r = new BigInteger(q.bitLength(), rand); 2978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 2988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// while (r.compareTo(q) >= 0 2998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne))); 3008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR); 3028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR); 3038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger wOne = WOne(r, x, q); 3058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q); 3068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r); 3078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q) 3098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// .multiply(x).mod(q) 3108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// .multiply(wSum).mod(q); 3118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return new Fp(q, root); 3138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p) 3168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 3178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (n.equals(ECConstants.ONE)) 3188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 3198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return wOne; 3208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 3218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// boolean isEven = !n.testBit(0); 3228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// n = n.shiftRight(1);//divide(ECConstants.TWO); 3238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (isEven) 3248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 3258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger w = W(n, wOne, p); 3268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return w.multiply(w).subtract(ECConstants.TWO).mod(p); 3278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 3288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p); 3298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger w2 = W(n, wOne, p); 3308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return w1.multiply(w2).subtract(wOne).mod(p); 3318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 3328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p) 3348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 3358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p); 3368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 3378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private BigInteger[] lucasSequence( 3398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger P, 3408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Q, 3418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger k) 3428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int n = k.bitLength(); 3448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int s = k.getLowestSetBit(); 3458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Uh = ECConstants.ONE; 3478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Vl = ECConstants.TWO; 3488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Vh = P; 3498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Ql = ECConstants.ONE; 3508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Qh = ECConstants.ONE; 3518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = n - 1; j >= s + 1; --j) 3538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Ql = modMult(Ql, Qh); 3558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (k.testBit(j)) 3578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Qh = modMult(Ql, Q); 3595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Uh = modMult(Uh, Vh); 3605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Vl = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql))); 3615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Vh = modReduce(Vh.multiply(Vh).subtract(Qh.shiftLeft(1))); 3628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 3648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Qh = Ql; 3665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Uh = modReduce(Uh.multiply(Vl).subtract(Ql)); 3675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Vh = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql))); 3685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Vl = modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1))); 3698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Ql = modMult(Ql, Qh); 3735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Qh = modMult(Ql, Q); 3745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Uh = modReduce(Uh.multiply(Vl).subtract(Ql)); 3755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Vl = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql))); 3765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Ql = modMult(Ql, Qh); 3778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = 1; j <= s; ++j) 3798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Uh = modMult(Uh, Vl); 3815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Vl = modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1))); 3825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root Ql = modMult(Ql, Ql); 3838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new BigInteger[]{ Uh, Vl }; 3868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root protected BigInteger modAdd(BigInteger x1, BigInteger x2) 3895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger x3 = x1.add(x2); 3915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (x3.compareTo(q) >= 0) 3925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x3 = x3.subtract(q); 3945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return x3; 3965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root protected BigInteger modDouble(BigInteger x) 3995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger _2x = x.shiftLeft(1); 4015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (_2x.compareTo(q) >= 0) 4025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root _2x = _2x.subtract(q); 4045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return _2x; 4065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root protected BigInteger modMult(BigInteger x1, BigInteger x2) 4095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return modReduce(x1.multiply(x2)); 4115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root protected BigInteger modReduce(BigInteger x) 4145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (naf != null) 4165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int last = naf.length - 1; 4185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int bits = naf[last]; 4195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while (x.bitLength() > (bits + 1)) 4205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// BigInteger u = x.shiftRight(bits); 4225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// BigInteger v = x.subtract(u.shiftLeft(bits)); 4235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 4245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = v; 4255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 4265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (int i = 0; i < last; ++i) 4275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int ni = naf[i]; 4295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (ni < 0) 4305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = x.add(u.shiftLeft(~ni)); 4325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// else 4345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = x.subtract(u.shiftLeft(ni)); 4365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while (x.compareTo(q) >= 0) 4405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = x.subtract(q); 4425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// else 4455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (r != null) 4465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int qLen = q.bitLength(); 4485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (x.bitLength() > (qLen + 1)) 4495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger u = x.shiftRight(qLen); 4515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root BigInteger v = x.subtract(u.shiftLeft(qLen)); 4525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (!r.equals(ONE)) 4535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root u = u.multiply(r); 4555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x = u.add(v); 4575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (x.compareTo(q) >= 0) 4595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x = x.subtract(q); 4615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 4645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x = x.mod(q); 4665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return x; 4685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public boolean equals(Object other) 4718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (other == this) 4738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return true; 4758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!(other instanceof ECFieldElement.Fp)) 4788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return false; 4808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement.Fp o = (ECFieldElement.Fp)other; 4838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q.equals(o.q) && x.equals(o.x); 4848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int hashCode() 4878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q.hashCode() ^ x.hashCode(); 4898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 4938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Class representing the Elements of the finite field 4948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB) 4958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial 4968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * basis representations are supported. Gaussian normal basis (GNB) 4978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * representation is not supported. 4988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 4998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static class F2m extends ECFieldElement 5008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger x; 5028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Indicates gaussian normal basis representation (GNB). Number chosen 5058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * according to X9.62. GNB is not implemented at present. 5068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static final int GNB = 1; 5088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Indicates trinomial basis representation (TPB). Number chosen 5118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * according to X9.62. 5128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static final int TPB = 2; 5148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Indicates pentanomial basis representation (PPB). Number chosen 5178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * according to X9.62. 5188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static final int PPB = 3; 5208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB or PPB. 5238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int representation; 5258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. 5288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int m; 5308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 5338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k</sup> + 1</code> represents the reduction polynomial 5348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>f(z)</code>.<br> 5358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 5368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 5378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 5388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int k1; 5408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB: Always set to <code>0</code><br> 5438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 5448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 5458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 5468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int k2; 5488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB: Always set to <code>0</code><br> 5518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 5528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 5538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 5548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int k3; 5568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Constructor for PPB. 5598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param m The exponent <code>m</code> of 5608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code>. 5618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 5628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 5638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>. 5648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 5658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 5668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>. 5678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 5688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 5698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>. 5708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param x The BigInteger representing the value of the field element. 5718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public F2m( 5738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int m, 5748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int k1, 5758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int k2, 5768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int k3, 5778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger x) 5788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// super(x); 5808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.x = x; 5818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if ((k2 == 0) && (k3 == 0)) 5838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.representation = TPB; 5858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// else 5878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (k2 >= k3) 5898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException( 5918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "k2 must be smaller than k3"); 5928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (k2 <= 0) 5948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException( 5968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "k2 must be larger than 0"); 5978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.representation = PPB; 5998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (x.signum() < 0) 6028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException("x value cannot be negative"); 6048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.m = m; 6078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.k1 = k1; 6088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.k2 = k2; 6098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.k3 = k3; 6108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 6138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Constructor for TPB. 6148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param m The exponent <code>m</code> of 6158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code>. 6168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 6178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k</sup> + 1</code> represents the reduction 6188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * polynomial <code>f(z)</code>. 6198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param x The BigInteger representing the value of the field element. 6208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 6218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public F2m(int m, int k, BigInteger x) 6228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Set k1 to k, and set k2 and k3 to 0 6248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this(m, k, 0, 0, x); 6258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public BigInteger toBigInteger() 6288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return x; 6308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public String getFieldName() 6338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return "F2m"; 6358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getFieldSize() 6388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return m; 6408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 6438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Checks, if the ECFieldElements <code>a</code> and <code>b</code> 6448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code> 6458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * (having the same representation). 6468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param a field element. 6478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param b field element to be compared. 6488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @throws IllegalArgumentException if <code>a</code> and <code>b</code> 6498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * are not elements of the same field 6508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code> (having the same 6518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * representation). 6528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 6538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static void checkFieldElements( 6548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement a, 6558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement b) 6568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if ((!(a instanceof F2m)) || (!(b instanceof F2m))) 6588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException("Field elements are not " 6608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// + "both instances of ECFieldElement.F2m"); 6618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if ((a.toBigInteger().signum() < 0) || (b.toBigInteger().signum() < 0)) 6648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException( 6668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "x value may not be negative"); 6678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a; 6708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b; 6718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1) 6738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3)) 6748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException("Field elements are not " 6768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// + "elements of the same field F2m"); 6778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (aF2m.representation != bF2m.representation) 6808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Should never occur 6828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException( 6838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "One of the field " 6848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// + "elements are not elements has incorrect representation"); 6858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 6898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Computes <code>z * a(z) mod f(z)</code>, where <code>f(z)</code> is 6908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * the reduction polynomial of <code>this</code>. 6918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param a The polynomial <code>a(z)</code> to be multiplied by 6928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>z mod f(z)</code>. 6938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return <code>z * a(z) mod f(z)</code> 6948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 6958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private BigInteger multZModF(final BigInteger a) 6968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Left-shift of a(z) 6988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger az = a.shiftLeft(1); 6998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (az.testBit(this.m)) 7008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // If the coefficient of z^m in a(z) equals 1, reduction 7028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // modulo f(z) is performed: Add f(z) to to a(z): 7038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Step 1: Unset mth coeffient of a(z) 7048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.clearBit(this.m); 7058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Step 2: Add r(z) to a(z), where r(z) is defined as 7078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // f(z) = z^m + r(z), and k1, k2, k3 are the positions of 7088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // the non-zero coefficients in r(z) 7098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.flipBit(0); 7108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.flipBit(this.k1); 7118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (this.representation == PPB) 7128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.flipBit(this.k2); 7148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.flipBit(this.k3); 7158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return az; 7188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement add(final ECFieldElement b) 7218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // No check performed here for performance reasons. Instead the 7238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // elements involved are checked in ECPoint.F2m 7248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // checkFieldElements(this, b); 7258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (b.toBigInteger().signum() == 0) 7268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this; 7288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.toBigInteger())); 7318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement subtract(final ECFieldElement b) 7348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Addition and subtraction are the same in F2m 7368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return add(b); 7378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement multiply(final ECFieldElement b) 7418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Left-to-right shift-and-add field multiplication in F2m 7438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Input: Binary polynomials a(z) and b(z) of degree at most m-1 7448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Output: c(z) = a(z) * b(z) mod f(z) 7458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // No check performed here for performance reasons. Instead the 7478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // elements involved are checked in ECPoint.F2m 7488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // checkFieldElements(this, b); 7498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// final BigInteger az = this.x; 7508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger bz = b.toBigInteger(); 7518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger cz; 7528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Compute c(z) = a(z) * b(z) mod f(z) 7548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (az.testBit(0)) 7558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// cz = bz; 7578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// else 7598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// cz = ECConstants.ZERO; 7618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// for (int i = 1; i < this.m; i++) 7648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // b(z) := z * b(z) mod f(z) 7668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// bz = multZModF(bz); 7678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (az.testBit(i)) 7698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // If the coefficient of x^i in a(z) equals 1, b(z) is added 7718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // to c(z) 7728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// cz = cz.xor(bz); 7738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz); 7768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement divide(final ECFieldElement b) 7808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // There may be more efficient implementations 7828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement bInv = b.invert(); 7838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return multiply(bInv); 7848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement negate() 7878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // -x == x holds for all x in F2m 7898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this; 7908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement square() 7938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Naive implementation, can probably be speeded up using modular 7958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // reduction 7968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return multiply(this); 7978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement invert() 8008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 8018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Inversion in F2m using the extended Euclidean algorithm 8028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Input: A nonzero polynomial a(z) of degree at most m-1 8038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Output: a(z)^(-1) mod f(z) 8048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // u(z) := a(z) 8068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger uz = this.x; 8078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (uz.signum() <= 0) 8088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 8098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new ArithmeticException("x is zero or negative, " + 8108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "inversion is impossible"); 8118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 8128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // v(z) := f(z) 8148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger vz = ECConstants.ZERO.setBit(m); 8158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = vz.setBit(0); 8168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = vz.setBit(this.k1); 8178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (this.representation == PPB) 8188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 8198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = vz.setBit(this.k2); 8208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = vz.setBit(this.k3); 8218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 8228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // g1(z) := 1, g2(z) := 0 8248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger g1z = ECConstants.ONE; 8258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger g2z = ECConstants.ZERO; 8268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // while u != 1 8288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// while (!(uz.equals(ECConstants.ZERO))) 8298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 8308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // j := deg(u(z)) - deg(v(z)) 8318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int j = uz.bitLength() - vz.bitLength(); 8328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j 8348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (j < 0) 8358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 8368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// final BigInteger uzCopy = uz; 8378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// uz = vz; 8388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = uzCopy; 8398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// final BigInteger g1zCopy = g1z; 8418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// g1z = g2z; 8428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// g2z = g1zCopy; 8438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// j = -j; 8458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 8468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // u(z) := u(z) + z^j * v(z) 8488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Note, that no reduction modulo f(z) is required, because 8498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z))) 8508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z)) 8518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // = deg(u(z)) 8528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// uz = uz.xor(vz.shiftLeft(j)); 8538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // g1(z) := g1(z) + z^j * g2(z) 8558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// g1z = g1z.xor(g2z.shiftLeft(j)); 8568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// if (g1z.bitLength() > this.m) { 8578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// throw new ArithmeticException( 8585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root//// "deg(g1z) >= m, g1z = " + g1z.toString(16)); 8598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// } 8608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 8618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return new ECFieldElement.F2m( 8628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.m, this.k1, this.k2, this.k3, g2z); 8638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 8648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement sqrt() 8668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 8678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new RuntimeException("Not implemented"); 8688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 8698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 8718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return the representation of the field 8728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code>, either of 8738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB (trinomial 8748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * basis representation) or 8758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB (pentanomial 8768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * basis representation). 8778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 8788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getRepresentation() 8798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 8808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.representation; 8818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 8828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 8848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return the degree <code>m</code> of the reduction polynomial 8858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>f(z)</code>. 8868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 8878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getM() 8888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 8898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.m; 8908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 8918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 8928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 8938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 8948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k</sup> + 1</code> represents the reduction polynomial 8958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>f(z)</code>.<br> 8968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 8978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 8988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 8998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 9008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getK1() 9018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 9028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.k1; 9038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 9048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 9058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 9068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return TPB: Always returns <code>0</code><br> 9078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 9088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 9098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 9108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 9118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getK2() 9128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 9138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.k2; 9148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 9158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 9168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 9178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return TPB: Always set to <code>0</code><br> 9188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 9198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 9208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 9218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 9228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getK3() 9238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 9248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.k3; 9258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 9268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 9278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public boolean equals(Object anObject) 9288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 9298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (anObject == this) 9308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 9318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return true; 9328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 9338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 9348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (!(anObject instanceof ECFieldElement.F2m)) 9358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 9368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return false; 9378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 9388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 9398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement.F2m b = (ECFieldElement.F2m)anObject; 9408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 9418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2) 9428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// && (this.k3 == b.k3) 9438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// && (this.representation == b.representation) 9448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// && (this.x.equals(b.x))); 9458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 9468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 9478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int hashCode() 9488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 9498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return x.hashCode() ^ m ^ k1 ^ k2 ^ k3; 9508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 9518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 9528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 9548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Class representing the Elements of the finite field 9558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB) 9568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial 9578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * basis representations are supported. Gaussian normal basis (GNB) 9588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * representation is not supported. 9598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 9608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static class F2m extends ECFieldElement 9618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 9638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Indicates gaussian normal basis representation (GNB). Number chosen 9648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * according to X9.62. GNB is not implemented at present. 9658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 9668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final int GNB = 1; 9678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 9698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Indicates trinomial basis representation (TPB). Number chosen 9708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * according to X9.62. 9718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 9728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final int TPB = 2; 9738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 9758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Indicates pentanomial basis representation (PPB). Number chosen 9768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * according to X9.62. 9778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 9788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final int PPB = 3; 9798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 9818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * TPB or PPB. 9828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 9838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int representation; 9848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 9868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. 9878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 9888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int m; 9898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// /** 9915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 9925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * x<sup>k</sup> + 1</code> represents the reduction polynomial 9935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * <code>f(z)</code>.<br> 9945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 9955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 9965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * represents the reduction polynomial <code>f(z)</code>.<br> 9975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// */ 9985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private int k1; 9995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 10005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// /** 10015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * TPB: Always set to <code>0</code><br> 10025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 10035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 10045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * represents the reduction polynomial <code>f(z)</code>.<br> 10055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// */ 10065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private int k2; 10075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 10085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// /** 10095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * TPB: Always set to <code>0</code><br> 10105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 10115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 10125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * represents the reduction polynomial <code>f(z)</code>.<br> 10135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// */ 10145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private int k3; 10158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private int[] ks; 10178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 10195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * The <code>LongArray</code> holding the bits. 10208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 10215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private LongArray x; 10228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 10248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Constructor for PPB. 10258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param m The exponent <code>m</code> of 10268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code>. 10278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 10288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 10298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>. 10308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 10318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 10328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>. 10338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 10348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 10358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>. 10368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param x The BigInteger representing the value of the field element. 10375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * @deprecated Use ECCurve.fromBigInteger to construct field elements 10388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 10398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public F2m( 10408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int m, 10418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int k1, 10428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int k2, 10438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int k3, 10448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger x) 10458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((k2 == 0) && (k3 == 0)) 10478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.representation = TPB; 10495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this.ks = new int[]{ k1 }; 10508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 10528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (k2 >= k3) 10548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException( 10568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom "k2 must be smaller than k3"); 10578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (k2 <= 0) 10598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException( 10618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom "k2 must be larger than 0"); 10628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.representation = PPB; 10645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this.ks = new int[]{ k1, k2, k3 }; 10658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.m = m; 10685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this.x = new LongArray(x); 10698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 10728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Constructor for TPB. 10738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param m The exponent <code>m</code> of 10748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code>. 10758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 10768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k</sup> + 1</code> represents the reduction 10778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * polynomial <code>f(z)</code>. 10788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param x The BigInteger representing the value of the field element. 10795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * @deprecated Use ECCurve.fromBigInteger to construct field elements 10808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 10818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public F2m(int m, int k, BigInteger x) 10828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Set k1 to k, and set k2 and k3 to 0 10848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this(m, k, 0, 0, x); 10858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private F2m(int m, int[] ks, LongArray x) 10888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.m = m; 10905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this.representation = (ks.length == 1) ? TPB : PPB; 10915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this.ks = ks; 10925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root this.x = x; 10935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public int bitLength() 10965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return x.degree(); 10985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public boolean isZero() 11015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return x.isZero(); 11035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 11048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public boolean testBitZero() 11065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return x.testBitZero(); 11088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public BigInteger toBigInteger() 11118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return x.toBigInteger(); 11138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public String getFieldName() 11168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return "F2m"; 11188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getFieldSize() 11218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return m; 11238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 11268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Checks, if the ECFieldElements <code>a</code> and <code>b</code> 11278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code> 11288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * (having the same representation). 11298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param a field element. 11308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param b field element to be compared. 11318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @throws IllegalArgumentException if <code>a</code> and <code>b</code> 11328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * are not elements of the same field 11338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code> (having the same 11348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * representation). 11358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 11368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static void checkFieldElements( 11378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement a, 11388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement b) 11398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((!(a instanceof F2m)) || (!(b instanceof F2m))) 11418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("Field elements are not " 11438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom + "both instances of ECFieldElement.F2m"); 11448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a; 11478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b; 11488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aF2m.representation != bF2m.representation) 11508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // Should never occur 11525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root throw new IllegalArgumentException("One of the F2m field elements has incorrect representation"); 11538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if ((aF2m.m != bF2m.m) || !Arrays.areEqual(aF2m.ks, bF2m.ks)) 11568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root throw new IllegalArgumentException("Field elements are not elements of the same field F2m"); 11588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement add(final ECFieldElement b) 11628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // No check performed here for performance reasons. Instead the 11648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // elements involved are checked in ECPoint.F2m 11658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // checkFieldElements(this, b); 11665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray iarrClone = (LongArray)this.x.clone(); 11678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom F2m bF2m = (F2m)b; 11685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root iarrClone.addShiftedByWords(bF2m.x, 0); 11695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new F2m(m, ks, iarrClone); 11705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 11715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public ECFieldElement addOne() 11735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new F2m(m, ks, x.addOne()); 11758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement subtract(final ECFieldElement b) 11788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Addition and subtraction are the same in F2m 11808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return add(b); 11818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement multiply(final ECFieldElement b) 11848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // Right-to-left comb multiplication in the LongArray 11868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Input: Binary polynomials a(z) and b(z) of degree at most m-1 11878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Output: c(z) = a(z) * b(z) mod f(z) 11888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // No check performed here for performance reasons. Instead the 11908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // elements involved are checked in ECPoint.F2m 11918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // checkFieldElements(this, b); 11925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new F2m(m, ks, x.modMultiply(((F2m)b).x, m, ks)); 11938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement divide(final ECFieldElement b) 11968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // There may be more efficient implementations 11988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement bInv = b.invert(); 11998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return multiply(bInv); 12008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement negate() 12038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // -x == x holds for all x in F2m 12058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this; 12068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement square() 12098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new F2m(m, ks, x.modSquare(m, ks)); 12118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement invert() 12148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new ECFieldElement.F2m(this.m, this.ks, this.x.modInverse(m, ks)); 12168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement sqrt() 12198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new RuntimeException("Not implemented"); 12218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 12248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return the representation of the field 12258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code>, either of 12268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * TPB (trinomial 12278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * basis representation) or 12288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB (pentanomial 12298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * basis representation). 12308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 12318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getRepresentation() 12328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this.representation; 12348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 12378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return the degree <code>m</code> of the reduction polynomial 12388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>f(z)</code>. 12398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 12408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getM() 12418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this.m; 12438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 12468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 12478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k</sup> + 1</code> represents the reduction polynomial 12488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>f(z)</code>.<br> 12498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 12508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 12518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 12528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 12538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getK1() 12548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this.ks[0]; 12568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 12598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return TPB: Always returns <code>0</code><br> 12608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 12618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 12628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 12638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 12648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getK2() 12658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this.ks.length >= 2 ? this.ks[1] : 0; 12678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 12708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return TPB: Always set to <code>0</code><br> 12718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 12728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 12738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 12748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 12758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getK3() 12768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this.ks.length >= 3 ? this.ks[2] : 0; 12788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public boolean equals(Object anObject) 12818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (anObject == this) 12838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return true; 12858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!(anObject instanceof ECFieldElement.F2m)) 12888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 12898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return false; 12908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement.F2m b = (ECFieldElement.F2m)anObject; 12938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 12945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return ((this.m == b.m) 12958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom && (this.representation == b.representation) 12965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root && Arrays.areEqual(this.ks, b.ks) 12978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom && (this.x.equals(b.x))); 12988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 12998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 13008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int hashCode() 13018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 13025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return x.hashCode() ^ m ^ Arrays.hashCode(ks); 13038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 13048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 13058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom} 1306