18212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrompackage org.bouncycastle.math.ec; 28212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 38212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromimport java.math.BigInteger; 48212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromimport java.util.Random; 58212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 68212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrompublic abstract class ECFieldElement 78212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom implements ECConstants 88212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom{ 98212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract BigInteger toBigInteger(); 118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract String getFieldName(); 128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract int getFieldSize(); 138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement add(ECFieldElement b); 148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement subtract(ECFieldElement b); 158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement multiply(ECFieldElement b); 168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement divide(ECFieldElement b); 178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement negate(); 188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement square(); 198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement invert(); 208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public abstract ECFieldElement sqrt(); 218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public String toString() 238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this.toBigInteger().toString(2); 258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static class Fp extends ECFieldElement 288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger x; 308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger q; 328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public Fp(BigInteger q, BigInteger x) 348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.x = x; 368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (x.compareTo(q) >= 0) 388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("x value too large in field element"); 408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.q = q; 438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public BigInteger toBigInteger() 468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return x; 488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * return the field name for this field. 528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return the string "Fp". 548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public String getFieldName() 568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return "Fp"; 588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getFieldSize() 618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q.bitLength(); 638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public BigInteger getQ() 668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q; 688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement add(ECFieldElement b) 718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new Fp(q, x.add(b.toBigInteger()).mod(q)); 738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement subtract(ECFieldElement b) 768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new Fp(q, x.subtract(b.toBigInteger()).mod(q)); 788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement multiply(ECFieldElement b) 818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new Fp(q, x.multiply(b.toBigInteger()).mod(q)); 838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement divide(ECFieldElement b) 868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new Fp(q, x.multiply(b.toBigInteger().modInverse(q)).mod(q)); 888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement negate() 918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new Fp(q, x.negate().mod(q)); 938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement square() 968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new Fp(q, x.multiply(x).mod(q)); 988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement invert() 1018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new Fp(q, x.modInverse(q)); 1038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // D.1.4 91 1068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 1078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * return a sqrt root - the routine verifies that the calculation 1088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * returns the right value - if none exists it returns null. 1098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 1108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement sqrt() 1118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!q.testBit(0)) 1138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new RuntimeException("not done yet"); 1158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // note: even though this class implements ECConstants don't be tempted to 1188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // remove the explicit declaration, some J2ME environments don't cope. 1198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // p mod 4 == 3 1208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (q.testBit(1)) 1218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // z = g^(u+1) + p, p = 4u + 3 1238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement z = new Fp(q, x.modPow(q.shiftRight(2).add(ECConstants.ONE), q)); 1248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return z.square().equals(this) ? z : null; 1268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // p mod 4 == 1 1298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger qMinusOne = q.subtract(ECConstants.ONE); 1308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger legendreExponent = qMinusOne.shiftRight(1); 1328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) 1338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return null; 1358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger u = qMinusOne.shiftRight(2); 1388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger k = u.shiftLeft(1).add(ECConstants.ONE); 1398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Q = this.x; 1418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger fourQ = Q.shiftLeft(2).mod(q); 1428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger U, V; 1448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Random rand = new Random(); 1458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom do 1468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger P; 1488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom do 1498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom P = new BigInteger(q.bitLength(), rand); 1518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (P.compareTo(q) >= 0 1538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, q).equals(qMinusOne))); 1548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger[] result = lucasSequence(q, P, Q, k); 1568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom U = result[0]; 1578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom V = result[1]; 1588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (V.multiply(V).mod(q).equals(fourQ)) 1608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Integer division by 2, mod q 1628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (V.testBit(0)) 1638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom V = V.add(q); 1658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom V = V.shiftRight(1); 1688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom //assert V.multiply(V).mod(q).equals(x); 1708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new ECFieldElement.Fp(q, V); 1728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (U.equals(ECConstants.ONE) || U.equals(qMinusOne)); 1758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return null; 1778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger qMinusOne = q.subtract(ECConstants.ONE); 1798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO); 1808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE))) 1818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 1828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return null; 1838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 1848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 1858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// Random rand = new Random(); 1868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger fourX = x.shiftLeft(2); 1878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 1888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger r; 1898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// do 1908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 1918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// r = new BigInteger(q.bitLength(), rand); 1928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 1938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// while (r.compareTo(q) >= 0 1948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne))); 1958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 1968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR); 1978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR); 1988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 1998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger wOne = WOne(r, x, q); 2008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q); 2018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r); 2028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 2038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q) 2048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// .multiply(x).mod(q) 2058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// .multiply(wSum).mod(q); 2068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 2078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return new Fp(q, root); 2088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p) 2118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 2128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (n.equals(ECConstants.ONE)) 2138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 2148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return wOne; 2158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 2168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// boolean isEven = !n.testBit(0); 2178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// n = n.shiftRight(1);//divide(ECConstants.TWO); 2188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (isEven) 2198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 2208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger w = W(n, wOne, p); 2218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return w.multiply(w).subtract(ECConstants.TWO).mod(p); 2228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 2238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p); 2248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger w2 = W(n, wOne, p); 2258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return w1.multiply(w2).subtract(wOne).mod(p); 2268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 2278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 2288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p) 2298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 2308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p); 2318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 2328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private static BigInteger[] lucasSequence( 2348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger p, 2358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger P, 2368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Q, 2378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger k) 2388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int n = k.bitLength(); 2408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int s = k.getLowestSetBit(); 2418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Uh = ECConstants.ONE; 2438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Vl = ECConstants.TWO; 2448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Vh = P; 2458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Ql = ECConstants.ONE; 2468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger Qh = ECConstants.ONE; 2478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = n - 1; j >= s + 1; --j) 2498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Ql = Ql.multiply(Qh).mod(p); 2518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (k.testBit(j)) 2538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Qh = Ql.multiply(Q).mod(p); 2558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Uh = Uh.multiply(Vh).mod(p); 2568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); 2578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Vh = Vh.multiply(Vh).subtract(Qh.shiftLeft(1)).mod(p); 2588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 2608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Qh = Ql; 2628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Uh = Uh.multiply(Vl).subtract(Ql).mod(p); 2638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Vh = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); 2648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p); 2658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Ql = Ql.multiply(Qh).mod(p); 2698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Qh = Ql.multiply(Q).mod(p); 2708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Uh = Uh.multiply(Vl).subtract(Ql).mod(p); 2718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p); 2728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Ql = Ql.multiply(Qh).mod(p); 2738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = 1; j <= s; ++j) 2758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Uh = Uh.multiply(Vl).mod(p); 2778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p); 2788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom Ql = Ql.multiply(Ql).mod(p); 2798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new BigInteger[]{ Uh, Vl }; 2828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public boolean equals(Object other) 2858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (other == this) 2878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return true; 2898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!(other instanceof ECFieldElement.Fp)) 2928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return false; 2948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement.Fp o = (ECFieldElement.Fp)other; 2978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q.equals(o.q) && x.equals(o.x); 2988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int hashCode() 3018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q.hashCode() ^ x.hashCode(); 3038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Class representing the Elements of the finite field 3088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB) 3098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial 3108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * basis representations are supported. Gaussian normal basis (GNB) 3118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * representation is not supported. 3128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static class F2m extends ECFieldElement 3148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 3158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger x; 3168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Indicates gaussian normal basis representation (GNB). Number chosen 3198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * according to X9.62. GNB is not implemented at present. 3208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static final int GNB = 1; 3228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Indicates trinomial basis representation (TPB). Number chosen 3258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * according to X9.62. 3268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static final int TPB = 2; 3288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Indicates pentanomial basis representation (PPB). Number chosen 3318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * according to X9.62. 3328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static final int PPB = 3; 3348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB or PPB. 3378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int representation; 3398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. 3428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int m; 3448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 3478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k</sup> + 1</code> represents the reduction polynomial 3488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>f(z)</code>.<br> 3498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 3508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 3518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 3528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int k1; 3548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB: Always set to <code>0</code><br> 3578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 3588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 3598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 3608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int k2; 3628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB: Always set to <code>0</code><br> 3658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 3668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 3678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 3688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private int k3; 3708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 3728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Constructor for PPB. 3738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param m The exponent <code>m</code> of 3748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code>. 3758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 3768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 3778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>. 3788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 3798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 3808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>. 3818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 3828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 3838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>. 3848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param x The BigInteger representing the value of the field element. 3858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 3868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public F2m( 3878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int m, 3888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int k1, 3898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int k2, 3908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int k3, 3918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger x) 3928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 3938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// super(x); 3948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.x = x; 3958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 3968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if ((k2 == 0) && (k3 == 0)) 3978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 3988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.representation = TPB; 3998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// else 4018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (k2 >= k3) 4038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException( 4058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "k2 must be smaller than k3"); 4068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (k2 <= 0) 4088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException( 4108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "k2 must be larger than 0"); 4118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.representation = PPB; 4138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (x.signum() < 0) 4168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException("x value cannot be negative"); 4188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.m = m; 4218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.k1 = k1; 4228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.k2 = k2; 4238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.k3 = k3; 4248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 4278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Constructor for TPB. 4288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param m The exponent <code>m</code> of 4298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code>. 4308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 4318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k</sup> + 1</code> represents the reduction 4328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * polynomial <code>f(z)</code>. 4338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param x The BigInteger representing the value of the field element. 4348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 4358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public F2m(int m, int k, BigInteger x) 4368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Set k1 to k, and set k2 and k3 to 0 4388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this(m, k, 0, 0, x); 4398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public BigInteger toBigInteger() 4428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return x; 4448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public String getFieldName() 4478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return "F2m"; 4498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getFieldSize() 4528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return m; 4548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 4578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Checks, if the ECFieldElements <code>a</code> and <code>b</code> 4588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code> 4598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * (having the same representation). 4608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param a field element. 4618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param b field element to be compared. 4628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @throws IllegalArgumentException if <code>a</code> and <code>b</code> 4638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * are not elements of the same field 4648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code> (having the same 4658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * representation). 4668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 4678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public static void checkFieldElements( 4688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement a, 4698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement b) 4708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if ((!(a instanceof F2m)) || (!(b instanceof F2m))) 4728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException("Field elements are not " 4748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// + "both instances of ECFieldElement.F2m"); 4758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if ((a.toBigInteger().signum() < 0) || (b.toBigInteger().signum() < 0)) 4788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException( 4808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "x value may not be negative"); 4818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a; 4848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b; 4858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1) 4878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3)) 4888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException("Field elements are not " 4908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// + "elements of the same field F2m"); 4918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 4928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 4938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (aF2m.representation != bF2m.representation) 4948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 4958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Should never occur 4968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new IllegalArgumentException( 4978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "One of the field " 4988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// + "elements are not elements has incorrect representation"); 4998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 5038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * Computes <code>z * a(z) mod f(z)</code>, where <code>f(z)</code> is 5048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * the reduction polynomial of <code>this</code>. 5058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @param a The polynomial <code>a(z)</code> to be multiplied by 5068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>z mod f(z)</code>. 5078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return <code>z * a(z) mod f(z)</code> 5088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 5098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// private BigInteger multZModF(final BigInteger a) 5108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Left-shift of a(z) 5128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger az = a.shiftLeft(1); 5138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (az.testBit(this.m)) 5148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // If the coefficient of z^m in a(z) equals 1, reduction 5168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // modulo f(z) is performed: Add f(z) to to a(z): 5178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Step 1: Unset mth coeffient of a(z) 5188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.clearBit(this.m); 5198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Step 2: Add r(z) to a(z), where r(z) is defined as 5218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // f(z) = z^m + r(z), and k1, k2, k3 are the positions of 5228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // the non-zero coefficients in r(z) 5238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.flipBit(0); 5248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.flipBit(this.k1); 5258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (this.representation == PPB) 5268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.flipBit(this.k2); 5288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// az = az.flipBit(this.k3); 5298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return az; 5328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement add(final ECFieldElement b) 5358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // No check performed here for performance reasons. Instead the 5378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // elements involved are checked in ECPoint.F2m 5388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // checkFieldElements(this, b); 5398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (b.toBigInteger().signum() == 0) 5408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this; 5428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.toBigInteger())); 5458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement subtract(final ECFieldElement b) 5488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Addition and subtraction are the same in F2m 5508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return add(b); 5518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement multiply(final ECFieldElement b) 5558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Left-to-right shift-and-add field multiplication in F2m 5578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Input: Binary polynomials a(z) and b(z) of degree at most m-1 5588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Output: c(z) = a(z) * b(z) mod f(z) 5598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // No check performed here for performance reasons. Instead the 5618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // elements involved are checked in ECPoint.F2m 5628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // checkFieldElements(this, b); 5638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// final BigInteger az = this.x; 5648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger bz = b.toBigInteger(); 5658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger cz; 5668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Compute c(z) = a(z) * b(z) mod f(z) 5688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (az.testBit(0)) 5698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// cz = bz; 5718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// else 5738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// cz = ECConstants.ZERO; 5758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// for (int i = 1; i < this.m; i++) 5788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // b(z) := z * b(z) mod f(z) 5808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// bz = multZModF(bz); 5818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (az.testBit(i)) 5838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // If the coefficient of x^i in a(z) equals 1, b(z) is added 5858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // to c(z) 5868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// cz = cz.xor(bz); 5878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz); 5908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 5938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement divide(final ECFieldElement b) 5948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 5958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // There may be more efficient implementations 5968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement bInv = b.invert(); 5978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return multiply(bInv); 5988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 5998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement negate() 6018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // -x == x holds for all x in F2m 6038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this; 6048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement square() 6078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Naive implementation, can probably be speeded up using modular 6098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // reduction 6108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return multiply(this); 6118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement invert() 6148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Inversion in F2m using the extended Euclidean algorithm 6168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Input: A nonzero polynomial a(z) of degree at most m-1 6178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Output: a(z)^(-1) mod f(z) 6188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // u(z) := a(z) 6208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger uz = this.x; 6218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (uz.signum() <= 0) 6228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new ArithmeticException("x is zero or negative, " + 6248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// "inversion is impossible"); 6258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // v(z) := f(z) 6288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger vz = ECConstants.ZERO.setBit(m); 6298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = vz.setBit(0); 6308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = vz.setBit(this.k1); 6318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (this.representation == PPB) 6328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = vz.setBit(this.k2); 6348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = vz.setBit(this.k3); 6358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // g1(z) := 1, g2(z) := 0 6388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger g1z = ECConstants.ONE; 6398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// BigInteger g2z = ECConstants.ZERO; 6408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // while u != 1 6428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// while (!(uz.equals(ECConstants.ZERO))) 6438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // j := deg(u(z)) - deg(v(z)) 6458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// int j = uz.bitLength() - vz.bitLength(); 6468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j 6488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (j < 0) 6498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// final BigInteger uzCopy = uz; 6518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// uz = vz; 6528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// vz = uzCopy; 6538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// final BigInteger g1zCopy = g1z; 6558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// g1z = g2z; 6568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// g2z = g1zCopy; 6578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// j = -j; 6598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // u(z) := u(z) + z^j * v(z) 6628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // Note, that no reduction modulo f(z) is required, because 6638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z))) 6648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z)) 6658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // = deg(u(z)) 6668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// uz = uz.xor(vz.shiftLeft(j)); 6678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// // g1(z) := g1(z) + z^j * g2(z) 6698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// g1z = g1z.xor(g2z.shiftLeft(j)); 6708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// if (g1z.bitLength() > this.m) { 6718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// throw new ArithmeticException( 6728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// "deg(g1z) >= m, g1z = " + g1z.toString(2)); 6738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom//// } 6748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return new ECFieldElement.F2m( 6768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// this.m, this.k1, this.k2, this.k3, g2z); 6778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public ECFieldElement sqrt() 6808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// throw new RuntimeException("Not implemented"); 6828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 6858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return the representation of the field 6868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>F<sub>2<sup>m</sup></sub></code>, either of 6878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * TPB (trinomial 6888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * basis representation) or 6898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB (pentanomial 6908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * basis representation). 6918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 6928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getRepresentation() 6938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 6948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.representation; 6958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 6968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 6978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 6988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return the degree <code>m</code> of the reduction polynomial 6998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>f(z)</code>. 7008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 7018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getM() 7028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.m; 7048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 7078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 7088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k</sup> + 1</code> represents the reduction polynomial 7098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * <code>f(z)</code>.<br> 7108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 7118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 7128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 7138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 7148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getK1() 7158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.k1; 7178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 7208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return TPB: Always returns <code>0</code><br> 7218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 7228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 7238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 7248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 7258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getK2() 7268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.k2; 7288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// /** 7318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * @return TPB: Always set to <code>0</code><br> 7328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 7338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 7348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// * represents the reduction polynomial <code>f(z)</code>.<br> 7358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// */ 7368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int getK3() 7378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return this.k3; 7398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public boolean equals(Object anObject) 7428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (anObject == this) 7448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return true; 7468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// if (!(anObject instanceof ECFieldElement.F2m)) 7498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return false; 7518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// ECFieldElement.F2m b = (ECFieldElement.F2m)anObject; 7548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2) 7568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// && (this.k3 == b.k3) 7578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// && (this.representation == b.representation) 7588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// && (this.x.equals(b.x))); 7598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// 7618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// public int hashCode() 7628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// { 7638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// return x.hashCode() ^ m ^ k1 ^ k2 ^ k3; 7648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// } 7668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 7688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Class representing the Elements of the finite field 7698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB) 7708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial 7718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * basis representations are supported. Gaussian normal basis (GNB) 7728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * representation is not supported. 7738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 7748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static class F2m extends ECFieldElement 7758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 7778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Indicates gaussian normal basis representation (GNB). Number chosen 7788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * according to X9.62. GNB is not implemented at present. 7798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 7808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final int GNB = 1; 7818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 7838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Indicates trinomial basis representation (TPB). Number chosen 7848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * according to X9.62. 7858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 7868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final int TPB = 2; 7878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 7898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Indicates pentanomial basis representation (PPB). Number chosen 7908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * according to X9.62. 7918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 7928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final int PPB = 3; 7938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 7958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * TPB or PPB. 7968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 7978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int representation; 7988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>. 8018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 8028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int m; 8038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 8068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k</sup> + 1</code> represents the reduction polynomial 8078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>f(z)</code>.<br> 8088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 8098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 8108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 8118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 8128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int k1; 8138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * TPB: Always set to <code>0</code><br> 8168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 8178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 8188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 8198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 8208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int k2; 8218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * TPB: Always set to <code>0</code><br> 8248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 8258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 8268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 8278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 8288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int k3; 8298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The <code>IntArray</code> holding the bits. 8328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 8338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private IntArray x; 8348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The number of <code>int</code>s required to hold <code>m</code> bits. 8378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 8388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int t; 8398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Constructor for PPB. 8428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param m The exponent <code>m</code> of 8438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code>. 8448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> + 8458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 8468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>. 8478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> + 8488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 8498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>. 8508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> + 8518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 8528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>. 8538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param x The BigInteger representing the value of the field element. 8548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 8558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public F2m( 8568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int m, 8578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int k1, 8588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int k2, 8598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int k3, 8608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger x) 8618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // t = m / 32 rounded up to the next integer 8638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom t = (m + 31) >> 5; 8648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.x = new IntArray(x, t); 8658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((k2 == 0) && (k3 == 0)) 8678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.representation = TPB; 8698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 8718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (k2 >= k3) 8738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException( 8758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom "k2 must be smaller than k3"); 8768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (k2 <= 0) 8788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException( 8808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom "k2 must be larger than 0"); 8818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.representation = PPB; 8838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (x.signum() < 0) 8868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("x value cannot be negative"); 8888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.m = m; 8918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.k1 = k1; 8928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.k2 = k2; 8938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.k3 = k3; 8948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Constructor for TPB. 8988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param m The exponent <code>m</code> of 8998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code>. 9008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k The integer <code>k</code> where <code>x<sup>m</sup> + 9018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k</sup> + 1</code> represents the reduction 9028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * polynomial <code>f(z)</code>. 9038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param x The BigInteger representing the value of the field element. 9048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 9058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public F2m(int m, int k, BigInteger x) 9068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Set k1 to k, and set k2 and k3 to 0 9088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this(m, k, 0, 0, x); 9098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private F2m(int m, int k1, int k2, int k3, IntArray x) 9128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom t = (m + 31) >> 5; 9148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.x = x; 9158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.m = m; 9168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.k1 = k1; 9178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.k2 = k2; 9188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.k3 = k3; 9198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((k2 == 0) && (k3 == 0)) 9218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.representation = TPB; 9238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 9258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.representation = PPB; 9278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public BigInteger toBigInteger() 9328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return x.toBigInteger(); 9348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public String getFieldName() 9378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return "F2m"; 9398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getFieldSize() 9428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return m; 9448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 9478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Checks, if the ECFieldElements <code>a</code> and <code>b</code> 9488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code> 9498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * (having the same representation). 9508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param a field element. 9518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param b field element to be compared. 9528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @throws IllegalArgumentException if <code>a</code> and <code>b</code> 9538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * are not elements of the same field 9548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code> (having the same 9558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * representation). 9568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 9578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static void checkFieldElements( 9588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement a, 9598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement b) 9608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((!(a instanceof F2m)) || (!(b instanceof F2m))) 9628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("Field elements are not " 9648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom + "both instances of ECFieldElement.F2m"); 9658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a; 9688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b; 9698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1) 9718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3)) 9728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("Field elements are not " 9748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom + "elements of the same field F2m"); 9758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (aF2m.representation != bF2m.representation) 9788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Should never occur 9808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException( 9818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom "One of the field " 9828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom + "elements are not elements has incorrect representation"); 9838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement add(final ECFieldElement b) 9878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // No check performed here for performance reasons. Instead the 9898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // elements involved are checked in ECPoint.F2m 9908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // checkFieldElements(this, b); 9918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray iarrClone = (IntArray)this.x.clone(); 9928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom F2m bF2m = (F2m)b; 9938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom iarrClone.addShifted(bF2m.x, 0); 9948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new F2m(m, k1, k2, k3, iarrClone); 9958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 9968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 9978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement subtract(final ECFieldElement b) 9988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 9998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Addition and subtraction are the same in F2m 10008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return add(b); 10018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement multiply(final ECFieldElement b) 10048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Right-to-left comb multiplication in the IntArray 10068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Input: Binary polynomials a(z) and b(z) of degree at most m-1 10078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Output: c(z) = a(z) * b(z) mod f(z) 10088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // No check performed here for performance reasons. Instead the 10108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // elements involved are checked in ECPoint.F2m 10118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // checkFieldElements(this, b); 10128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom F2m bF2m = (F2m)b; 10138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray mult = x.multiply(bF2m.x, m); 10148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom mult.reduce(m, new int[]{k1, k2, k3}); 10158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new F2m(m, k1, k2, k3, mult); 10168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement divide(final ECFieldElement b) 10198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // There may be more efficient implementations 10218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement bInv = b.invert(); 10228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return multiply(bInv); 10238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement negate() 10268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // -x == x holds for all x in F2m 10288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this; 10298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement square() 10328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray squared = x.square(m); 10348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom squared.reduce(m, new int[]{k1, k2, k3}); 10358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new F2m(m, k1, k2, k3, squared); 10368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement invert() 10408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Inversion in F2m using the extended Euclidean algorithm 10428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Input: A nonzero polynomial a(z) of degree at most m-1 10438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Output: a(z)^(-1) mod f(z) 10448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // u(z) := a(z) 10468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray uz = (IntArray)this.x.clone(); 10478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // v(z) := f(z) 10498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray vz = new IntArray(t); 10508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom vz.setBit(m); 10518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom vz.setBit(0); 10528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom vz.setBit(this.k1); 10538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (this.representation == PPB) 10548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom vz.setBit(this.k2); 10568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom vz.setBit(this.k3); 10578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // g1(z) := 1, g2(z) := 0 10608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray g1z = new IntArray(t); 10618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom g1z.setBit(0); 10628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray g2z = new IntArray(t); 10638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // while u != 0 10658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (!uz.isZero()) 10668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// while (uz.getUsedLength() > 0) 10678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// while (uz.bitLength() > 1) 10688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // j := deg(u(z)) - deg(v(z)) 10708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int j = uz.bitLength() - vz.bitLength(); 10718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j 10738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (j < 0) 10748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 10758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom final IntArray uzCopy = uz; 10768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom uz = vz; 10778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom vz = uzCopy; 10788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom final IntArray g1zCopy = g1z; 10808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom g1z = g2z; 10818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom g2z = g1zCopy; 10828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom j = -j; 10848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 10858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // u(z) := u(z) + z^j * v(z) 10878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Note, that no reduction modulo f(z) is required, because 10888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z))) 10898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z)) 10908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // = deg(u(z)) 10918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // uz = uz.xor(vz.shiftLeft(j)); 10928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // jInt = n / 32 10938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int jInt = j >> 5; 10948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // jInt = n % 32 10958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int jBit = j & 0x1F; 10968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray vzShift = vz.shiftLeft(jBit); 10978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom uz.addShifted(vzShift, jInt); 10988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 10998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // g1(z) := g1(z) + z^j * g2(z) 11008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// g1z = g1z.xor(g2z.shiftLeft(j)); 11018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray g2zShift = g2z.shiftLeft(jBit); 11028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom g1z.addShifted(g2zShift, jInt); 11038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new ECFieldElement.F2m( 11068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this.m, this.k1, this.k2, this.k3, g2z); 11078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public ECFieldElement sqrt() 11108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new RuntimeException("Not implemented"); 11128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 11158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return the representation of the field 11168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>F<sub>2<sup>m</sup></sub></code>, either of 11178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * TPB (trinomial 11188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * basis representation) or 11198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB (pentanomial 11208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * basis representation). 11218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 11228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getRepresentation() 11238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this.representation; 11258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 11288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return the degree <code>m</code> of the reduction polynomial 11298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>f(z)</code>. 11308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 11318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getM() 11328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this.m; 11348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 11378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> + 11388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k</sup> + 1</code> represents the reduction polynomial 11398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>f(z)</code>.<br> 11408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> + 11418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 11428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 11438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 11448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getK1() 11458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this.k1; 11478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 11508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return TPB: Always returns <code>0</code><br> 11518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> + 11528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 11538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 11548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 11558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getK2() 11568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this.k2; 11588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 11618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return TPB: Always set to <code>0</code><br> 11628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> + 11638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code> 11648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * represents the reduction polynomial <code>f(z)</code>.<br> 11658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 11668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getK3() 11678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this.k3; 11698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public boolean equals(Object anObject) 11728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (anObject == this) 11748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return true; 11768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!(anObject instanceof ECFieldElement.F2m)) 11798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return false; 11818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECFieldElement.F2m b = (ECFieldElement.F2m)anObject; 11848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2) 11868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom && (this.k3 == b.k3) 11878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom && (this.representation == b.representation) 11888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom && (this.x.equals(b.x))); 11898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 11918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int hashCode() 11928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 11938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return x.hashCode() ^ m ^ k1 ^ k2 ^ k3; 11948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 11968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom} 1197