18212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrompackage org.bouncycastle.math.ec; 28212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 38212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromimport java.math.BigInteger; 48212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 58212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom/** 68212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Class holding methods for point multiplication based on the window 78212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * τ-adic nonadjacent form (WTNAF). The algorithms are based on the 88212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * paper "Improved Algorithms for Arithmetic on Anomalous Binary Curves" 98212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * by Jerome A. Solinas. The paper first appeared in the Proceedings of 108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Crypto 1997. 118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromclass Tnaf 138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom{ 148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private static final BigInteger MINUS_ONE = ECConstants.ONE.negate(); 158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private static final BigInteger MINUS_TWO = ECConstants.TWO.negate(); 168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private static final BigInteger MINUS_THREE = ECConstants.THREE.negate(); 178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The window width of WTNAF. The standard value of 4 is slightly less 208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * than optimal for running time, but keeps space requirements for 218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * precomputation low. For typical curves, a value of 5 or 6 results in 228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * a better running time. When changing this value, the 238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>α<sub>u</sub></code>'s must be computed differently, see 248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * e.g. "Guide to Elliptic Curve Cryptography", Darrel Hankerson, 258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Alfred Menezes, Scott Vanstone, Springer-Verlag New York Inc., 2004, 268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * p. 121-122 278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final byte WIDTH = 4; 298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 2<sup>4</sup> 328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final byte POW_2_WIDTH = 16; 348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array 378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * of <code>ZTauElement</code>s. 388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final ZTauElement[] alpha0 = { 408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom null, 418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom new ZTauElement(ECConstants.ONE, ECConstants.ZERO), null, 428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom new ZTauElement(MINUS_THREE, MINUS_ONE), null, 438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom new ZTauElement(MINUS_ONE, MINUS_ONE), null, 448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom new ZTauElement(ECConstants.ONE, MINUS_ONE), null 458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom }; 468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array 498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * of TNAFs. 508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final byte[][] alpha0Tnaf = { 528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom null, {1}, null, {-1, 0, 1}, null, {1, 0, 1}, null, {-1, 0, 0, 1} 538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom }; 548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array 578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * of <code>ZTauElement</code>s. 588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final ZTauElement[] alpha1 = {null, 608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom new ZTauElement(ECConstants.ONE, ECConstants.ZERO), null, 618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom new ZTauElement(MINUS_THREE, ECConstants.ONE), null, 628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom new ZTauElement(MINUS_ONE, ECConstants.ONE), null, 638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom new ZTauElement(ECConstants.ONE, ECConstants.ONE), null 648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom }; 658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array 688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * of TNAFs. 698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static final byte[][] alpha1Tnaf = { 718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom null, {1}, null, {-1, 0, 1}, null, {1, 0, 1}, null, {-1, 0, 0, -1} 728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom }; 738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Computes the norm of an element <code>λ</code> of 768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>Z</b>[τ]</code>. 778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param mu The parameter <code>μ</code> of the elliptic curve. 788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param lambda The element <code>λ</code> of 798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>Z</b>[τ]</code>. 808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return The norm of <code>λ</code>. 818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static BigInteger norm(final byte mu, ZTauElement lambda) 838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger norm; 858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // s1 = u^2 878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger s1 = lambda.u.multiply(lambda.u); 888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // s2 = u * v 908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger s2 = lambda.u.multiply(lambda.v); 918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // s3 = 2 * v^2 938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger s3 = lambda.v.multiply(lambda.v).shiftLeft(1); 948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom norm = s1.add(s2).add(s3); 988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else if (mu == -1) 1008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom norm = s1.subtract(s2).add(s3); 1028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 1048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("mu must be 1 or -1"); 1068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return norm; 1098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 1128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Computes the norm of an element <code>λ</code> of 1138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>R</b>[τ]</code>, where <code>λ = u + vτ</code> 1148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * and <code>u</code> and <code>u</code> are real numbers (elements of 1158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>R</b></code>). 1168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param mu The parameter <code>μ</code> of the elliptic curve. 1178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param u The real part of the element <code>λ</code> of 1188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>R</b>[τ]</code>. 1198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param v The <code>τ</code>-adic part of the element 1208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>λ</code> of <code><b>R</b>[τ]</code>. 1218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return The norm of <code>λ</code>. 1228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 1238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static SimpleBigDecimal norm(final byte mu, SimpleBigDecimal u, 1248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal v) 1258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal norm; 1278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // s1 = u^2 1298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal s1 = u.multiply(u); 1308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // s2 = u * v 1328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal s2 = u.multiply(v); 1338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // s3 = 2 * v^2 1358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal s3 = v.multiply(v).shiftLeft(1); 1368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 1388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom norm = s1.add(s2).add(s3); 1408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else if (mu == -1) 1428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom norm = s1.subtract(s2).add(s3); 1448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 1468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("mu must be 1 or -1"); 1488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return norm; 1518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 1548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Rounds an element <code>λ</code> of <code><b>R</b>[τ]</code> 1558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * to an element of <code><b>Z</b>[τ]</code>, such that their difference 1568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * has minimal norm. <code>λ</code> is given as 1578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>λ = λ<sub>0</sub> + λ<sub>1</sub>τ</code>. 1588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param lambda0 The component <code>λ<sub>0</sub></code>. 1598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param lambda1 The component <code>λ<sub>1</sub></code>. 1608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param mu The parameter <code>μ</code> of the elliptic curve. Must 1618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * equal 1 or -1. 1628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return The rounded element of <code><b>Z</b>[τ]</code>. 1638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @throws IllegalArgumentException if <code>lambda0</code> and 1648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>lambda1</code> do not have same scale. 1658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 1668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ZTauElement round(SimpleBigDecimal lambda0, 1678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal lambda1, byte mu) 1688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int scale = lambda0.getScale(); 1708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (lambda1.getScale() != scale) 1718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("lambda0 and lambda1 do not " + 1738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom "have same scale"); 1748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!((mu == 1) || (mu == -1))) 1778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("mu must be 1 or -1"); 1798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger f0 = lambda0.round(); 1828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger f1 = lambda1.round(); 1838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal eta0 = lambda0.subtract(f0); 1858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal eta1 = lambda1.subtract(f1); 1868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // eta = 2*eta0 + mu*eta1 1888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal eta = eta0.add(eta0); 1898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 1908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom eta = eta.add(eta1); 1928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 1948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // mu == -1 1968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom eta = eta.subtract(eta1); 1978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // check1 = eta0 - 3*mu*eta1 2008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // check2 = eta0 + 4*mu*eta1 2018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal threeEta1 = eta1.add(eta1).add(eta1); 2028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal fourEta1 = threeEta1.add(eta1); 2038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal check1; 2048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal check2; 2058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 2068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom check1 = eta0.subtract(threeEta1); 2088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom check2 = eta0.add(fourEta1); 2098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 2118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // mu == -1 2138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom check1 = eta0.add(threeEta1); 2148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom check2 = eta0.subtract(fourEta1); 2158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte h0 = 0; 2188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte h1 = 0; 2198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // if eta >= 1 2218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (eta.compareTo(ECConstants.ONE) >= 0) 2228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (check1.compareTo(MINUS_ONE) < 0) 2248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom h1 = mu; 2268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 2288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom h0 = 1; 2308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 2338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // eta < 1 2358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (check2.compareTo(ECConstants.TWO) >= 0) 2368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom h1 = mu; 2388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // if eta < -1 2428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (eta.compareTo(MINUS_ONE) < 0) 2438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (check1.compareTo(ECConstants.ONE) >= 0) 2458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom h1 = (byte)-mu; 2478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 2498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom h0 = -1; 2518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 2548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // eta >= -1 2568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (check2.compareTo(MINUS_TWO) < 0) 2578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom h1 = (byte)-mu; 2598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger q0 = f0.add(BigInteger.valueOf(h0)); 2638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger q1 = f1.add(BigInteger.valueOf(h1)); 2648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new ZTauElement(q0, q1); 2658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 2688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Approximate division by <code>n</code>. For an integer 2698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>k</code>, the value <code>λ = s k / n</code> is 2708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * computed to <code>c</code> bits of accuracy. 2718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k The parameter <code>k</code>. 2728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param s The curve parameter <code>s<sub>0</sub></code> or 2738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>s<sub>1</sub></code>. 2748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param vm The Lucas Sequence element <code>V<sub>m</sub></code>. 2758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param a The parameter <code>a</code> of the elliptic curve. 2768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param m The bit length of the finite field 2778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>F</b><sub>m</sub></code>. 2788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param c The number of bits of accuracy, i.e. the scale of the returned 2798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>SimpleBigDecimal</code>. 2808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return The value <code>λ = s k / n</code> computed to 2818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>c</code> bits of accuracy. 2828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 2838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static SimpleBigDecimal approximateDivisionByN(BigInteger k, 2848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger s, BigInteger vm, byte a, int m, int c) 2858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int _k = (m + 5)/2 + c; 2878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger ns = k.shiftRight(m - _k - 2 + a); 2888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger gs = s.multiply(ns); 2908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger hs = gs.shiftRight(m); 2928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger js = vm.multiply(hs); 2948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger gsPlusJs = gs.add(js); 2968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger ls = gsPlusJs.shiftRight(_k-c); 2978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (gsPlusJs.testBit(_k-c-1)) 2988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // round up 3008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ls = ls.add(ECConstants.ONE); 3018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new SimpleBigDecimal(ls, c); 3048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 3078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Computes the <code>τ</code>-adic NAF (non-adjacent form) of an 3088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * element <code>λ</code> of <code><b>Z</b>[τ]</code>. 3098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param mu The parameter <code>μ</code> of the elliptic curve. 3108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param lambda The element <code>λ</code> of 3118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>Z</b>[τ]</code>. 3128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return The <code>τ</code>-adic NAF of <code>λ</code>. 3138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 3148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static byte[] tauAdicNaf(byte mu, ZTauElement lambda) 3158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!((mu == 1) || (mu == -1))) 3178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("mu must be 1 or -1"); 3198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger norm = norm(mu, lambda); 3228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Ceiling of log2 of the norm 3248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int log2Norm = norm.bitLength(); 3258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52 3278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int maxLength = log2Norm > 30 ? log2Norm + 4 : 34; 3288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // The array holding the TNAF 3308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte[] u = new byte[maxLength]; 3318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int i = 0; 3328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // The actual length of the TNAF 3348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int length = 0; 3358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger r0 = lambda.u; 3378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger r1 = lambda.v; 3388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while(!((r0.equals(ECConstants.ZERO)) && (r1.equals(ECConstants.ZERO)))) 3408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // If r0 is odd 3428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (r0.testBit(0)) 3438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u[i] = (byte) ECConstants.TWO.subtract((r0.subtract(r1.shiftLeft(1))).mod(ECConstants.FOUR)).intValue(); 3458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // r0 = r0 - u[i] 3478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (u[i] == 1) 3488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r0 = r0.clearBit(0); 3508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 3528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // u[i] == -1 3548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r0 = r0.add(ECConstants.ONE); 3558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom length = i; 3578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 3598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u[i] = 0; 3618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger t = r0; 3648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger s = r0.shiftRight(1); 3658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 3668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r0 = r1.add(s); 3688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 3708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // mu == -1 3728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r0 = r1.subtract(s); 3738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r1 = t.shiftRight(1).negate(); 3768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom i++; 3778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom length++; 3808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Reduce the TNAF array to its actual length 3828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte[] tnaf = new byte[length]; 3838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom System.arraycopy(u, 0, tnaf, 0, length); 3848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return tnaf; 3858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 3888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Applies the operation <code>τ()</code> to an 3898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>ECPoint.F2m</code>. 3908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param p The ECPoint.F2m to which <code>τ()</code> is applied. 3918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return <code>τ(p)</code> 3928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 3938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ECPoint.F2m tau(ECPoint.F2m p) 3948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return p.tau(); 3968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 3998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Returns the parameter <code>μ</code> of the elliptic curve. 4008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param curve The elliptic curve from which to obtain <code>μ</code>. 4018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * The curve must be a Koblitz curve, i.e. <code>a</code> equals 4028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>0</code> or <code>1</code> and <code>b</code> equals 4038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>1</code>. 4048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return <code>μ</code> of the elliptic curve. 4058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @throws IllegalArgumentException if the given ECCurve is not a Koblitz 4068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * curve. 4078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 4088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static byte getMu(ECCurve.F2m curve) 4098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (!curve.isKoblitz()) 4118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root throw new IllegalArgumentException("No Koblitz curve (ABC), TNAF multiplication not possible"); 4138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (curve.getA().isZero()) 4168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return -1; 4188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return 1; 4218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 4248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Calculates the Lucas Sequence elements <code>U<sub>k-1</sub></code> and 4258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> and 4268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>V<sub>k</sub></code>. 4278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param mu The parameter <code>μ</code> of the elliptic curve. 4288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k The index of the second element of the Lucas Sequence to be 4298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * returned. 4308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param doV If set to true, computes <code>V<sub>k-1</sub></code> and 4318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>V<sub>k</sub></code>, otherwise <code>U<sub>k-1</sub></code> and 4328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>U<sub>k</sub></code>. 4338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return An array with 2 elements, containing <code>U<sub>k-1</sub></code> 4348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * and <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> 4358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * and <code>V<sub>k</sub></code>. 4368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 4378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static BigInteger[] getLucas(byte mu, int k, boolean doV) 4388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!((mu == 1) || (mu == -1))) 4408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("mu must be 1 or -1"); 4428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger u0; 4458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger u1; 4468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger u2; 4478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (doV) 4498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u0 = ECConstants.TWO; 4518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u1 = BigInteger.valueOf(mu); 4528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 4548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u0 = ECConstants.ZERO; 4568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u1 = ECConstants.ONE; 4578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 1; i < k; i++) 4608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // u2 = mu*u1 - 2*u0; 4628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger s = null; 4638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 4648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom s = u1; 4668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 4688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // mu == -1 4708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom s = u1.negate(); 4718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u2 = s.subtract(u0.shiftLeft(1)); 4748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u0 = u1; 4758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u1 = u2; 4768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// System.out.println(i + ": " + u2); 4778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// System.out.println(); 4788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger[] retVal = {u0, u1}; 4818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return retVal; 4828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 4858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Computes the auxiliary value <code>t<sub>w</sub></code>. If the width is 4868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * 4, then for <code>mu = 1</code>, <code>t<sub>w</sub> = 6</code> and for 4878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>mu = -1</code>, <code>t<sub>w</sub> = 10</code> 4888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param mu The parameter <code>μ</code> of the elliptic curve. 4898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param w The window width of the WTNAF. 4908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return the auxiliary value <code>t<sub>w</sub></code> 4918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 4928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static BigInteger getTw(byte mu, int w) 4938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (w == 4) 4958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 4978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return BigInteger.valueOf(6); 4998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 5018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // mu == -1 5038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return BigInteger.valueOf(10); 5048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 5078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // For w <> 4, the values must be computed 5098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger[] us = getLucas(mu, w, false); 5108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger twoToW = ECConstants.ZERO.setBit(w); 5118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger u1invert = us[1].modInverse(twoToW); 5128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger tw; 5138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom tw = ECConstants.TWO.multiply(us[0]).multiply(u1invert).mod(twoToW); 5148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// System.out.println("mu = " + mu); 5158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom// System.out.println("tw = " + tw); 5168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return tw; 5178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 5218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Computes the auxiliary values <code>s<sub>0</sub></code> and 5228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>s<sub>1</sub></code> used for partial modular reduction. 5238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param curve The elliptic curve for which to compute 5248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>s<sub>0</sub></code> and <code>s<sub>1</sub></code>. 5258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @throws IllegalArgumentException if <code>curve</code> is not a 5268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Koblitz curve (Anomalous Binary Curve, ABC). 5278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 5288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static BigInteger[] getSi(ECCurve.F2m curve) 5298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!curve.isKoblitz()) 5318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("si is defined for Koblitz curves only"); 5338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int m = curve.getM(); 5368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int a = curve.getA().toBigInteger().intValue(); 5378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte mu = curve.getMu(); 5388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int h = curve.getH().intValue(); 5398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int index = m + 3 - a; 5408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger[] ui = getLucas(mu, index, false); 5418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger dividend0; 5438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger dividend1; 5448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 5458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom dividend0 = ECConstants.ONE.subtract(ui[1]); 5478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom dividend1 = ECConstants.ONE.subtract(ui[0]); 5488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else if (mu == -1) 5508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom dividend0 = ECConstants.ONE.add(ui[1]); 5528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom dividend1 = ECConstants.ONE.add(ui[0]); 5538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 5558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("mu must be 1 or -1"); 5578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger[] si = new BigInteger[2]; 5608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (h == 2) 5628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom si[0] = dividend0.shiftRight(1); 5648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom si[1] = dividend1.shiftRight(1).negate(); 5658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else if (h == 4) 5678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom si[0] = dividend0.shiftRight(2); 5698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom si[1] = dividend1.shiftRight(2).negate(); 5708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 5728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("h (Cofactor) must be 2 or 4"); 5748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return si; 5778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 5808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Partial modular reduction modulo 5818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>(τ<sup>m</sup> - 1)/(τ - 1)</code>. 5828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k The integer to be reduced. 5838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param m The bitlength of the underlying finite field. 5848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param a The parameter <code>a</code> of the elliptic curve. 5858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param s The auxiliary values <code>s<sub>0</sub></code> and 5868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>s<sub>1</sub></code>. 5878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param mu The parameter μ of the elliptic curve. 5888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param c The precision (number of bits of accuracy) of the partial 5898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * modular reduction. 5908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return <code>ρ := k partmod (τ<sup>m</sup> - 1)/(τ - 1)</code> 5918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 5928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ZTauElement partModReduction(BigInteger k, int m, byte a, 5938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger[] s, byte mu, byte c) 5948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // d0 = s[0] + mu*s[1]; mu is either 1 or -1 5968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger d0; 5978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 5988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom d0 = s[0].add(s[1]); 6008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 6028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 6038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom d0 = s[0].subtract(s[1]); 6048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger[] v = getLucas(mu, m, true); 6078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger vm = v[1]; 6088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal lambda0 = approximateDivisionByN( 6108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom k, s[0], vm, a, m, c); 6118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom SimpleBigDecimal lambda1 = approximateDivisionByN( 6138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom k, s[1], vm, a, m, c); 6148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ZTauElement q = round(lambda0, lambda1, mu); 6168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // r0 = n - d0*q0 - 2*s1*q1 6188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger r0 = k.subtract(d0.multiply(q.u)).subtract( 6198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger.valueOf(2).multiply(s[1]).multiply(q.v)); 6208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // r1 = s1*q0 - s0*q1 6228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger r1 = s[1].multiply(q.u).subtract(s[0].multiply(q.v)); 6238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new ZTauElement(r0, r1); 6258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 6288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m} 6298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * by a <code>BigInteger</code> using the reduced <code>τ</code>-adic 6308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * NAF (RTNAF) method. 6318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param p The ECPoint.F2m to multiply. 6328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param k The <code>BigInteger</code> by which to multiply <code>p</code>. 6338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return <code>k * p</code> 6348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 6358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ECPoint.F2m multiplyRTnaf(ECPoint.F2m p, BigInteger k) 6368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 6378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECCurve.F2m curve = (ECCurve.F2m) p.getCurve(); 6388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int m = curve.getM(); 6398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte a = (byte) curve.getA().toBigInteger().intValue(); 6408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte mu = curve.getMu(); 6418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger[] s = curve.getSi(); 6428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ZTauElement rho = partModReduction(k, m, a, s, mu, (byte)10); 6438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return multiplyTnaf(p, rho); 6458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 6488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m} 6498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> 6508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * using the <code>τ</code>-adic NAF (TNAF) method. 6518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param p The ECPoint.F2m to multiply. 6528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param lambda The element <code>λ</code> of 6538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>Z</b>[τ]</code>. 6548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return <code>λ * p</code> 6558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 6568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ECPoint.F2m multiplyTnaf(ECPoint.F2m p, ZTauElement lambda) 6578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 6588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECCurve.F2m curve = (ECCurve.F2m)p.getCurve(); 6598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte mu = curve.getMu(); 6608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte[] u = tauAdicNaf(mu, lambda); 6618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECPoint.F2m q = multiplyFromTnaf(p, u); 6638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q; 6658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 6688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.F2m ECPoint.F2m} 6698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> 6708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * using the <code>τ</code>-adic NAF (TNAF) method, given the TNAF 6718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * of <code>λ</code>. 6728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param p The ECPoint.F2m to multiply. 6738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param u The the TNAF of <code>λ</code>.. 6748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return <code>λ * p</code> 6758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 6768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ECPoint.F2m multiplyFromTnaf(ECPoint.F2m p, byte[] u) 6778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 6788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECCurve.F2m curve = (ECCurve.F2m)p.getCurve(); 6798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECPoint.F2m q = (ECPoint.F2m) curve.getInfinity(); 6808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = u.length - 1; i >= 0; i--) 6818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 6828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom q = tau(q); 6838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (u[i] == 1) 6848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 6858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom q = (ECPoint.F2m)q.addSimple(p); 6868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else if (u[i] == -1) 6888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 6898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom q = (ECPoint.F2m)q.subtractSimple(p); 6908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return q; 6938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 6948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 6958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 6968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Computes the <code>[τ]</code>-adic window NAF of an element 6978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>λ</code> of <code><b>Z</b>[τ]</code>. 6988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param mu The parameter μ of the elliptic curve. 6998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param lambda The element <code>λ</code> of 7008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code><b>Z</b>[τ]</code> of which to compute the 7018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>[τ]</code>-adic NAF. 7028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param width The window width of the resulting WNAF. 7038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param pow2w 2<sup>width</sup>. 7048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param tw The auxiliary value <code>t<sub>w</sub></code>. 7058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param alpha The <code>α<sub>u</sub></code>'s for the window width. 7068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return The <code>[τ]</code>-adic window NAF of 7078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * <code>λ</code>. 7088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 7098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static byte[] tauAdicWNaf(byte mu, ZTauElement lambda, 7108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha) 7118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!((mu == 1) || (mu == -1))) 7138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("mu must be 1 or -1"); 7158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger norm = norm(mu, lambda); 7188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Ceiling of log2 of the norm 7208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int log2Norm = norm.bitLength(); 7218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52 7238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int maxLength = log2Norm > 30 ? log2Norm + 4 + width : 34 + width; 7248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // The array holding the TNAF 7268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte[] u = new byte[maxLength]; 7278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // 2^(width - 1) 7298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger pow2wMin1 = pow2w.shiftRight(1); 7308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Split lambda into two BigIntegers to simplify calculations 7328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger r0 = lambda.u; 7338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger r1 = lambda.v; 7348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int i = 0; 7358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // while lambda <> (0, 0) 7378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (!((r0.equals(ECConstants.ZERO))&&(r1.equals(ECConstants.ZERO)))) 7388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // if r0 is odd 7408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (r0.testBit(0)) 7418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // uUnMod = r0 + r1*tw mod 2^width 7438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger uUnMod 7448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom = r0.add(r1.multiply(tw)).mod(pow2w); 7458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte uLocal; 7478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // if uUnMod >= 2^(width - 1) 7488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (uUnMod.compareTo(pow2wMin1) >= 0) 7498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom uLocal = (byte) uUnMod.subtract(pow2w).intValue(); 7518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 7538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom uLocal = (byte) uUnMod.intValue(); 7558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // uLocal is now in [-2^(width-1), 2^(width-1)-1] 7578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u[i] = uLocal; 7598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom boolean s = true; 7608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (uLocal < 0) 7618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom s = false; 7638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom uLocal = (byte)-uLocal; 7648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // uLocal is now >= 0 7668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (s) 7688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r0 = r0.subtract(alpha[uLocal].u); 7708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r1 = r1.subtract(alpha[uLocal].v); 7718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 7738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r0 = r0.add(alpha[uLocal].u); 7758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r1 = r1.add(alpha[uLocal].v); 7768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 7798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom u[i] = 0; 7818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom BigInteger t = r0; 7848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 7858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (mu == 1) 7868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r0 = r1.add(r0.shiftRight(1)); 7888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 7908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 7918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // mu == -1 7928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r0 = r1.subtract(r0.shiftRight(1)); 7938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom r1 = t.shiftRight(1).negate(); 7958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom i++; 7968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return u; 7988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 7998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom /** 8018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * Does the precomputation for WTNAF multiplication. 8028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param p The <code>ECPoint</code> for which to do the precomputation. 8038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @param a The parameter <code>a</code> of the elliptic curve. 8048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom * @return The precomputation array for <code>p</code>. 8058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom */ 8068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public static ECPoint.F2m[] getPreComp(ECPoint.F2m p, byte a) 8078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ECPoint.F2m[] pu; 8098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom pu = new ECPoint.F2m[16]; 8108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom pu[1] = p; 8118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte[][] alphaTnaf; 8128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (a == 0) 8138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom alphaTnaf = Tnaf.alpha0Tnaf; 8158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 8178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // a == 1 8198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom alphaTnaf = Tnaf.alpha1Tnaf; 8208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 8228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int precompLen = alphaTnaf.length; 8238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 3; i < precompLen; i = i + 2) 8248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 8258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom pu[i] = Tnaf.multiplyFromTnaf(p, alphaTnaf[i]); 8268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root p.getCurve().normalizeAll(pu); 8295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return pu; 8318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 8328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom} 833