1package org.bouncycastle.math.ec; 2 3import org.bouncycastle.util.Arrays; 4 5import java.math.BigInteger; 6 7class LongArray 8{ 9// private static long DEINTERLEAVE_MASK = 0x5555555555555555L; 10 11 /* 12 * This expands 8 bit indices into 16 bit contents (high bit 14), by inserting 0s between bits. 13 * In a binary field, this operation is the same as squaring an 8 bit number. 14 */ 15 private static final int[] INTERLEAVE2_TABLE = new int[] 16 { 17 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, 18 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 19 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, 20 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, 21 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, 22 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, 23 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, 24 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, 25 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, 26 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, 27 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, 28 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, 29 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, 30 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, 31 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, 32 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, 33 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, 34 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, 35 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, 36 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, 37 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, 38 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, 39 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, 40 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, 41 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, 42 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, 43 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, 44 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, 45 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, 46 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, 47 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, 48 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 49 }; 50 51 /* 52 * This expands 7 bit indices into 21 bit contents (high bit 18), by inserting 0s between bits. 53 */ 54 private static final int[] INTERLEAVE3_TABLE = new int[] 55 { 56 0x00000, 0x00001, 0x00008, 0x00009, 0x00040, 0x00041, 0x00048, 0x00049, 57 0x00200, 0x00201, 0x00208, 0x00209, 0x00240, 0x00241, 0x00248, 0x00249, 58 0x01000, 0x01001, 0x01008, 0x01009, 0x01040, 0x01041, 0x01048, 0x01049, 59 0x01200, 0x01201, 0x01208, 0x01209, 0x01240, 0x01241, 0x01248, 0x01249, 60 0x08000, 0x08001, 0x08008, 0x08009, 0x08040, 0x08041, 0x08048, 0x08049, 61 0x08200, 0x08201, 0x08208, 0x08209, 0x08240, 0x08241, 0x08248, 0x08249, 62 0x09000, 0x09001, 0x09008, 0x09009, 0x09040, 0x09041, 0x09048, 0x09049, 63 0x09200, 0x09201, 0x09208, 0x09209, 0x09240, 0x09241, 0x09248, 0x09249, 64 0x40000, 0x40001, 0x40008, 0x40009, 0x40040, 0x40041, 0x40048, 0x40049, 65 0x40200, 0x40201, 0x40208, 0x40209, 0x40240, 0x40241, 0x40248, 0x40249, 66 0x41000, 0x41001, 0x41008, 0x41009, 0x41040, 0x41041, 0x41048, 0x41049, 67 0x41200, 0x41201, 0x41208, 0x41209, 0x41240, 0x41241, 0x41248, 0x41249, 68 0x48000, 0x48001, 0x48008, 0x48009, 0x48040, 0x48041, 0x48048, 0x48049, 69 0x48200, 0x48201, 0x48208, 0x48209, 0x48240, 0x48241, 0x48248, 0x48249, 70 0x49000, 0x49001, 0x49008, 0x49009, 0x49040, 0x49041, 0x49048, 0x49049, 71 0x49200, 0x49201, 0x49208, 0x49209, 0x49240, 0x49241, 0x49248, 0x49249 72 }; 73 74 /* 75 * This expands 8 bit indices into 32 bit contents (high bit 28), by inserting 0s between bits. 76 */ 77 private static final int[] INTERLEAVE4_TABLE = new int[] 78 { 79 0x00000000, 0x00000001, 0x00000010, 0x00000011, 0x00000100, 0x00000101, 0x00000110, 0x00000111, 80 0x00001000, 0x00001001, 0x00001010, 0x00001011, 0x00001100, 0x00001101, 0x00001110, 0x00001111, 81 0x00010000, 0x00010001, 0x00010010, 0x00010011, 0x00010100, 0x00010101, 0x00010110, 0x00010111, 82 0x00011000, 0x00011001, 0x00011010, 0x00011011, 0x00011100, 0x00011101, 0x00011110, 0x00011111, 83 0x00100000, 0x00100001, 0x00100010, 0x00100011, 0x00100100, 0x00100101, 0x00100110, 0x00100111, 84 0x00101000, 0x00101001, 0x00101010, 0x00101011, 0x00101100, 0x00101101, 0x00101110, 0x00101111, 85 0x00110000, 0x00110001, 0x00110010, 0x00110011, 0x00110100, 0x00110101, 0x00110110, 0x00110111, 86 0x00111000, 0x00111001, 0x00111010, 0x00111011, 0x00111100, 0x00111101, 0x00111110, 0x00111111, 87 0x01000000, 0x01000001, 0x01000010, 0x01000011, 0x01000100, 0x01000101, 0x01000110, 0x01000111, 88 0x01001000, 0x01001001, 0x01001010, 0x01001011, 0x01001100, 0x01001101, 0x01001110, 0x01001111, 89 0x01010000, 0x01010001, 0x01010010, 0x01010011, 0x01010100, 0x01010101, 0x01010110, 0x01010111, 90 0x01011000, 0x01011001, 0x01011010, 0x01011011, 0x01011100, 0x01011101, 0x01011110, 0x01011111, 91 0x01100000, 0x01100001, 0x01100010, 0x01100011, 0x01100100, 0x01100101, 0x01100110, 0x01100111, 92 0x01101000, 0x01101001, 0x01101010, 0x01101011, 0x01101100, 0x01101101, 0x01101110, 0x01101111, 93 0x01110000, 0x01110001, 0x01110010, 0x01110011, 0x01110100, 0x01110101, 0x01110110, 0x01110111, 94 0x01111000, 0x01111001, 0x01111010, 0x01111011, 0x01111100, 0x01111101, 0x01111110, 0x01111111, 95 0x10000000, 0x10000001, 0x10000010, 0x10000011, 0x10000100, 0x10000101, 0x10000110, 0x10000111, 96 0x10001000, 0x10001001, 0x10001010, 0x10001011, 0x10001100, 0x10001101, 0x10001110, 0x10001111, 97 0x10010000, 0x10010001, 0x10010010, 0x10010011, 0x10010100, 0x10010101, 0x10010110, 0x10010111, 98 0x10011000, 0x10011001, 0x10011010, 0x10011011, 0x10011100, 0x10011101, 0x10011110, 0x10011111, 99 0x10100000, 0x10100001, 0x10100010, 0x10100011, 0x10100100, 0x10100101, 0x10100110, 0x10100111, 100 0x10101000, 0x10101001, 0x10101010, 0x10101011, 0x10101100, 0x10101101, 0x10101110, 0x10101111, 101 0x10110000, 0x10110001, 0x10110010, 0x10110011, 0x10110100, 0x10110101, 0x10110110, 0x10110111, 102 0x10111000, 0x10111001, 0x10111010, 0x10111011, 0x10111100, 0x10111101, 0x10111110, 0x10111111, 103 0x11000000, 0x11000001, 0x11000010, 0x11000011, 0x11000100, 0x11000101, 0x11000110, 0x11000111, 104 0x11001000, 0x11001001, 0x11001010, 0x11001011, 0x11001100, 0x11001101, 0x11001110, 0x11001111, 105 0x11010000, 0x11010001, 0x11010010, 0x11010011, 0x11010100, 0x11010101, 0x11010110, 0x11010111, 106 0x11011000, 0x11011001, 0x11011010, 0x11011011, 0x11011100, 0x11011101, 0x11011110, 0x11011111, 107 0x11100000, 0x11100001, 0x11100010, 0x11100011, 0x11100100, 0x11100101, 0x11100110, 0x11100111, 108 0x11101000, 0x11101001, 0x11101010, 0x11101011, 0x11101100, 0x11101101, 0x11101110, 0x11101111, 109 0x11110000, 0x11110001, 0x11110010, 0x11110011, 0x11110100, 0x11110101, 0x11110110, 0x11110111, 110 0x11111000, 0x11111001, 0x11111010, 0x11111011, 0x11111100, 0x11111101, 0x11111110, 0x11111111 111 }; 112 113 /* 114 * This expands 7 bit indices into 35 bit contents (high bit 30), by inserting 0s between bits. 115 */ 116 private static final int[] INTERLEAVE5_TABLE = new int[] { 117 0x00000000, 0x00000001, 0x00000020, 0x00000021, 0x00000400, 0x00000401, 0x00000420, 0x00000421, 118 0x00008000, 0x00008001, 0x00008020, 0x00008021, 0x00008400, 0x00008401, 0x00008420, 0x00008421, 119 0x00100000, 0x00100001, 0x00100020, 0x00100021, 0x00100400, 0x00100401, 0x00100420, 0x00100421, 120 0x00108000, 0x00108001, 0x00108020, 0x00108021, 0x00108400, 0x00108401, 0x00108420, 0x00108421, 121 0x02000000, 0x02000001, 0x02000020, 0x02000021, 0x02000400, 0x02000401, 0x02000420, 0x02000421, 122 0x02008000, 0x02008001, 0x02008020, 0x02008021, 0x02008400, 0x02008401, 0x02008420, 0x02008421, 123 0x02100000, 0x02100001, 0x02100020, 0x02100021, 0x02100400, 0x02100401, 0x02100420, 0x02100421, 124 0x02108000, 0x02108001, 0x02108020, 0x02108021, 0x02108400, 0x02108401, 0x02108420, 0x02108421, 125 0x40000000, 0x40000001, 0x40000020, 0x40000021, 0x40000400, 0x40000401, 0x40000420, 0x40000421, 126 0x40008000, 0x40008001, 0x40008020, 0x40008021, 0x40008400, 0x40008401, 0x40008420, 0x40008421, 127 0x40100000, 0x40100001, 0x40100020, 0x40100021, 0x40100400, 0x40100401, 0x40100420, 0x40100421, 128 0x40108000, 0x40108001, 0x40108020, 0x40108021, 0x40108400, 0x40108401, 0x40108420, 0x40108421, 129 0x42000000, 0x42000001, 0x42000020, 0x42000021, 0x42000400, 0x42000401, 0x42000420, 0x42000421, 130 0x42008000, 0x42008001, 0x42008020, 0x42008021, 0x42008400, 0x42008401, 0x42008420, 0x42008421, 131 0x42100000, 0x42100001, 0x42100020, 0x42100021, 0x42100400, 0x42100401, 0x42100420, 0x42100421, 132 0x42108000, 0x42108001, 0x42108020, 0x42108021, 0x42108400, 0x42108401, 0x42108420, 0x42108421 133 }; 134 135 /* 136 * This expands 9 bit indices into 63 bit (long) contents (high bit 56), by inserting 0s between bits. 137 */ 138 private static final long[] INTERLEAVE7_TABLE = new long[] 139 { 140 0x0000000000000000L, 0x0000000000000001L, 0x0000000000000080L, 0x0000000000000081L, 141 0x0000000000004000L, 0x0000000000004001L, 0x0000000000004080L, 0x0000000000004081L, 142 0x0000000000200000L, 0x0000000000200001L, 0x0000000000200080L, 0x0000000000200081L, 143 0x0000000000204000L, 0x0000000000204001L, 0x0000000000204080L, 0x0000000000204081L, 144 0x0000000010000000L, 0x0000000010000001L, 0x0000000010000080L, 0x0000000010000081L, 145 0x0000000010004000L, 0x0000000010004001L, 0x0000000010004080L, 0x0000000010004081L, 146 0x0000000010200000L, 0x0000000010200001L, 0x0000000010200080L, 0x0000000010200081L, 147 0x0000000010204000L, 0x0000000010204001L, 0x0000000010204080L, 0x0000000010204081L, 148 0x0000000800000000L, 0x0000000800000001L, 0x0000000800000080L, 0x0000000800000081L, 149 0x0000000800004000L, 0x0000000800004001L, 0x0000000800004080L, 0x0000000800004081L, 150 0x0000000800200000L, 0x0000000800200001L, 0x0000000800200080L, 0x0000000800200081L, 151 0x0000000800204000L, 0x0000000800204001L, 0x0000000800204080L, 0x0000000800204081L, 152 0x0000000810000000L, 0x0000000810000001L, 0x0000000810000080L, 0x0000000810000081L, 153 0x0000000810004000L, 0x0000000810004001L, 0x0000000810004080L, 0x0000000810004081L, 154 0x0000000810200000L, 0x0000000810200001L, 0x0000000810200080L, 0x0000000810200081L, 155 0x0000000810204000L, 0x0000000810204001L, 0x0000000810204080L, 0x0000000810204081L, 156 0x0000040000000000L, 0x0000040000000001L, 0x0000040000000080L, 0x0000040000000081L, 157 0x0000040000004000L, 0x0000040000004001L, 0x0000040000004080L, 0x0000040000004081L, 158 0x0000040000200000L, 0x0000040000200001L, 0x0000040000200080L, 0x0000040000200081L, 159 0x0000040000204000L, 0x0000040000204001L, 0x0000040000204080L, 0x0000040000204081L, 160 0x0000040010000000L, 0x0000040010000001L, 0x0000040010000080L, 0x0000040010000081L, 161 0x0000040010004000L, 0x0000040010004001L, 0x0000040010004080L, 0x0000040010004081L, 162 0x0000040010200000L, 0x0000040010200001L, 0x0000040010200080L, 0x0000040010200081L, 163 0x0000040010204000L, 0x0000040010204001L, 0x0000040010204080L, 0x0000040010204081L, 164 0x0000040800000000L, 0x0000040800000001L, 0x0000040800000080L, 0x0000040800000081L, 165 0x0000040800004000L, 0x0000040800004001L, 0x0000040800004080L, 0x0000040800004081L, 166 0x0000040800200000L, 0x0000040800200001L, 0x0000040800200080L, 0x0000040800200081L, 167 0x0000040800204000L, 0x0000040800204001L, 0x0000040800204080L, 0x0000040800204081L, 168 0x0000040810000000L, 0x0000040810000001L, 0x0000040810000080L, 0x0000040810000081L, 169 0x0000040810004000L, 0x0000040810004001L, 0x0000040810004080L, 0x0000040810004081L, 170 0x0000040810200000L, 0x0000040810200001L, 0x0000040810200080L, 0x0000040810200081L, 171 0x0000040810204000L, 0x0000040810204001L, 0x0000040810204080L, 0x0000040810204081L, 172 0x0002000000000000L, 0x0002000000000001L, 0x0002000000000080L, 0x0002000000000081L, 173 0x0002000000004000L, 0x0002000000004001L, 0x0002000000004080L, 0x0002000000004081L, 174 0x0002000000200000L, 0x0002000000200001L, 0x0002000000200080L, 0x0002000000200081L, 175 0x0002000000204000L, 0x0002000000204001L, 0x0002000000204080L, 0x0002000000204081L, 176 0x0002000010000000L, 0x0002000010000001L, 0x0002000010000080L, 0x0002000010000081L, 177 0x0002000010004000L, 0x0002000010004001L, 0x0002000010004080L, 0x0002000010004081L, 178 0x0002000010200000L, 0x0002000010200001L, 0x0002000010200080L, 0x0002000010200081L, 179 0x0002000010204000L, 0x0002000010204001L, 0x0002000010204080L, 0x0002000010204081L, 180 0x0002000800000000L, 0x0002000800000001L, 0x0002000800000080L, 0x0002000800000081L, 181 0x0002000800004000L, 0x0002000800004001L, 0x0002000800004080L, 0x0002000800004081L, 182 0x0002000800200000L, 0x0002000800200001L, 0x0002000800200080L, 0x0002000800200081L, 183 0x0002000800204000L, 0x0002000800204001L, 0x0002000800204080L, 0x0002000800204081L, 184 0x0002000810000000L, 0x0002000810000001L, 0x0002000810000080L, 0x0002000810000081L, 185 0x0002000810004000L, 0x0002000810004001L, 0x0002000810004080L, 0x0002000810004081L, 186 0x0002000810200000L, 0x0002000810200001L, 0x0002000810200080L, 0x0002000810200081L, 187 0x0002000810204000L, 0x0002000810204001L, 0x0002000810204080L, 0x0002000810204081L, 188 0x0002040000000000L, 0x0002040000000001L, 0x0002040000000080L, 0x0002040000000081L, 189 0x0002040000004000L, 0x0002040000004001L, 0x0002040000004080L, 0x0002040000004081L, 190 0x0002040000200000L, 0x0002040000200001L, 0x0002040000200080L, 0x0002040000200081L, 191 0x0002040000204000L, 0x0002040000204001L, 0x0002040000204080L, 0x0002040000204081L, 192 0x0002040010000000L, 0x0002040010000001L, 0x0002040010000080L, 0x0002040010000081L, 193 0x0002040010004000L, 0x0002040010004001L, 0x0002040010004080L, 0x0002040010004081L, 194 0x0002040010200000L, 0x0002040010200001L, 0x0002040010200080L, 0x0002040010200081L, 195 0x0002040010204000L, 0x0002040010204001L, 0x0002040010204080L, 0x0002040010204081L, 196 0x0002040800000000L, 0x0002040800000001L, 0x0002040800000080L, 0x0002040800000081L, 197 0x0002040800004000L, 0x0002040800004001L, 0x0002040800004080L, 0x0002040800004081L, 198 0x0002040800200000L, 0x0002040800200001L, 0x0002040800200080L, 0x0002040800200081L, 199 0x0002040800204000L, 0x0002040800204001L, 0x0002040800204080L, 0x0002040800204081L, 200 0x0002040810000000L, 0x0002040810000001L, 0x0002040810000080L, 0x0002040810000081L, 201 0x0002040810004000L, 0x0002040810004001L, 0x0002040810004080L, 0x0002040810004081L, 202 0x0002040810200000L, 0x0002040810200001L, 0x0002040810200080L, 0x0002040810200081L, 203 0x0002040810204000L, 0x0002040810204001L, 0x0002040810204080L, 0x0002040810204081L, 204 0x0100000000000000L, 0x0100000000000001L, 0x0100000000000080L, 0x0100000000000081L, 205 0x0100000000004000L, 0x0100000000004001L, 0x0100000000004080L, 0x0100000000004081L, 206 0x0100000000200000L, 0x0100000000200001L, 0x0100000000200080L, 0x0100000000200081L, 207 0x0100000000204000L, 0x0100000000204001L, 0x0100000000204080L, 0x0100000000204081L, 208 0x0100000010000000L, 0x0100000010000001L, 0x0100000010000080L, 0x0100000010000081L, 209 0x0100000010004000L, 0x0100000010004001L, 0x0100000010004080L, 0x0100000010004081L, 210 0x0100000010200000L, 0x0100000010200001L, 0x0100000010200080L, 0x0100000010200081L, 211 0x0100000010204000L, 0x0100000010204001L, 0x0100000010204080L, 0x0100000010204081L, 212 0x0100000800000000L, 0x0100000800000001L, 0x0100000800000080L, 0x0100000800000081L, 213 0x0100000800004000L, 0x0100000800004001L, 0x0100000800004080L, 0x0100000800004081L, 214 0x0100000800200000L, 0x0100000800200001L, 0x0100000800200080L, 0x0100000800200081L, 215 0x0100000800204000L, 0x0100000800204001L, 0x0100000800204080L, 0x0100000800204081L, 216 0x0100000810000000L, 0x0100000810000001L, 0x0100000810000080L, 0x0100000810000081L, 217 0x0100000810004000L, 0x0100000810004001L, 0x0100000810004080L, 0x0100000810004081L, 218 0x0100000810200000L, 0x0100000810200001L, 0x0100000810200080L, 0x0100000810200081L, 219 0x0100000810204000L, 0x0100000810204001L, 0x0100000810204080L, 0x0100000810204081L, 220 0x0100040000000000L, 0x0100040000000001L, 0x0100040000000080L, 0x0100040000000081L, 221 0x0100040000004000L, 0x0100040000004001L, 0x0100040000004080L, 0x0100040000004081L, 222 0x0100040000200000L, 0x0100040000200001L, 0x0100040000200080L, 0x0100040000200081L, 223 0x0100040000204000L, 0x0100040000204001L, 0x0100040000204080L, 0x0100040000204081L, 224 0x0100040010000000L, 0x0100040010000001L, 0x0100040010000080L, 0x0100040010000081L, 225 0x0100040010004000L, 0x0100040010004001L, 0x0100040010004080L, 0x0100040010004081L, 226 0x0100040010200000L, 0x0100040010200001L, 0x0100040010200080L, 0x0100040010200081L, 227 0x0100040010204000L, 0x0100040010204001L, 0x0100040010204080L, 0x0100040010204081L, 228 0x0100040800000000L, 0x0100040800000001L, 0x0100040800000080L, 0x0100040800000081L, 229 0x0100040800004000L, 0x0100040800004001L, 0x0100040800004080L, 0x0100040800004081L, 230 0x0100040800200000L, 0x0100040800200001L, 0x0100040800200080L, 0x0100040800200081L, 231 0x0100040800204000L, 0x0100040800204001L, 0x0100040800204080L, 0x0100040800204081L, 232 0x0100040810000000L, 0x0100040810000001L, 0x0100040810000080L, 0x0100040810000081L, 233 0x0100040810004000L, 0x0100040810004001L, 0x0100040810004080L, 0x0100040810004081L, 234 0x0100040810200000L, 0x0100040810200001L, 0x0100040810200080L, 0x0100040810200081L, 235 0x0100040810204000L, 0x0100040810204001L, 0x0100040810204080L, 0x0100040810204081L, 236 0x0102000000000000L, 0x0102000000000001L, 0x0102000000000080L, 0x0102000000000081L, 237 0x0102000000004000L, 0x0102000000004001L, 0x0102000000004080L, 0x0102000000004081L, 238 0x0102000000200000L, 0x0102000000200001L, 0x0102000000200080L, 0x0102000000200081L, 239 0x0102000000204000L, 0x0102000000204001L, 0x0102000000204080L, 0x0102000000204081L, 240 0x0102000010000000L, 0x0102000010000001L, 0x0102000010000080L, 0x0102000010000081L, 241 0x0102000010004000L, 0x0102000010004001L, 0x0102000010004080L, 0x0102000010004081L, 242 0x0102000010200000L, 0x0102000010200001L, 0x0102000010200080L, 0x0102000010200081L, 243 0x0102000010204000L, 0x0102000010204001L, 0x0102000010204080L, 0x0102000010204081L, 244 0x0102000800000000L, 0x0102000800000001L, 0x0102000800000080L, 0x0102000800000081L, 245 0x0102000800004000L, 0x0102000800004001L, 0x0102000800004080L, 0x0102000800004081L, 246 0x0102000800200000L, 0x0102000800200001L, 0x0102000800200080L, 0x0102000800200081L, 247 0x0102000800204000L, 0x0102000800204001L, 0x0102000800204080L, 0x0102000800204081L, 248 0x0102000810000000L, 0x0102000810000001L, 0x0102000810000080L, 0x0102000810000081L, 249 0x0102000810004000L, 0x0102000810004001L, 0x0102000810004080L, 0x0102000810004081L, 250 0x0102000810200000L, 0x0102000810200001L, 0x0102000810200080L, 0x0102000810200081L, 251 0x0102000810204000L, 0x0102000810204001L, 0x0102000810204080L, 0x0102000810204081L, 252 0x0102040000000000L, 0x0102040000000001L, 0x0102040000000080L, 0x0102040000000081L, 253 0x0102040000004000L, 0x0102040000004001L, 0x0102040000004080L, 0x0102040000004081L, 254 0x0102040000200000L, 0x0102040000200001L, 0x0102040000200080L, 0x0102040000200081L, 255 0x0102040000204000L, 0x0102040000204001L, 0x0102040000204080L, 0x0102040000204081L, 256 0x0102040010000000L, 0x0102040010000001L, 0x0102040010000080L, 0x0102040010000081L, 257 0x0102040010004000L, 0x0102040010004001L, 0x0102040010004080L, 0x0102040010004081L, 258 0x0102040010200000L, 0x0102040010200001L, 0x0102040010200080L, 0x0102040010200081L, 259 0x0102040010204000L, 0x0102040010204001L, 0x0102040010204080L, 0x0102040010204081L, 260 0x0102040800000000L, 0x0102040800000001L, 0x0102040800000080L, 0x0102040800000081L, 261 0x0102040800004000L, 0x0102040800004001L, 0x0102040800004080L, 0x0102040800004081L, 262 0x0102040800200000L, 0x0102040800200001L, 0x0102040800200080L, 0x0102040800200081L, 263 0x0102040800204000L, 0x0102040800204001L, 0x0102040800204080L, 0x0102040800204081L, 264 0x0102040810000000L, 0x0102040810000001L, 0x0102040810000080L, 0x0102040810000081L, 265 0x0102040810004000L, 0x0102040810004001L, 0x0102040810004080L, 0x0102040810004081L, 266 0x0102040810200000L, 0x0102040810200001L, 0x0102040810200080L, 0x0102040810200081L, 267 0x0102040810204000L, 0x0102040810204001L, 0x0102040810204080L, 0x0102040810204081L 268 }; 269 270 // For toString(); must have length 64 271 private static final String ZEROES = "0000000000000000000000000000000000000000000000000000000000000000"; 272 273 final static byte[] bitLengths = 274 { 275 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 276 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 277 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 278 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 279 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 280 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 281 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 282 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 283 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 284 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 285 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 286 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 287 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 288 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 289 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 290 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 291 }; 292 293 // TODO make m fixed for the LongArray, and hence compute T once and for all 294 295 private long[] m_ints; 296 297 public LongArray(int intLen) 298 { 299 m_ints = new long[intLen]; 300 } 301 302 public LongArray(long[] ints) 303 { 304 m_ints = ints; 305 } 306 307 public LongArray(long[] ints, int off, int len) 308 { 309 if (off == 0 && len == ints.length) 310 { 311 m_ints = ints; 312 } 313 else 314 { 315 m_ints = new long[len]; 316 System.arraycopy(ints, off, m_ints, 0, len); 317 } 318 } 319 320 public LongArray(BigInteger bigInt) 321 { 322 if (bigInt == null || bigInt.signum() < 0) 323 { 324 throw new IllegalArgumentException("invalid F2m field value"); 325 } 326 327 if (bigInt.signum() == 0) 328 { 329 m_ints = new long[] { 0L }; 330 return; 331 } 332 333 byte[] barr = bigInt.toByteArray(); 334 int barrLen = barr.length; 335 int barrStart = 0; 336 if (barr[0] == 0) 337 { 338 // First byte is 0 to enforce highest (=sign) bit is zero. 339 // In this case ignore barr[0]. 340 barrLen--; 341 barrStart = 1; 342 } 343 int intLen = (barrLen + 7) / 8; 344 m_ints = new long[intLen]; 345 346 int iarrJ = intLen - 1; 347 int rem = barrLen % 8 + barrStart; 348 long temp = 0; 349 int barrI = barrStart; 350 if (barrStart < rem) 351 { 352 for (; barrI < rem; barrI++) 353 { 354 temp <<= 8; 355 int barrBarrI = barr[barrI] & 0xFF; 356 temp |= barrBarrI; 357 } 358 m_ints[iarrJ--] = temp; 359 } 360 361 for (; iarrJ >= 0; iarrJ--) 362 { 363 temp = 0; 364 for (int i = 0; i < 8; i++) 365 { 366 temp <<= 8; 367 int barrBarrI = barr[barrI++] & 0xFF; 368 temp |= barrBarrI; 369 } 370 m_ints[iarrJ] = temp; 371 } 372 } 373 374 public boolean isZero() 375 { 376 long[] a = m_ints; 377 for (int i = 0; i < a.length; ++i) 378 { 379 if (a[i] != 0L) 380 { 381 return false; 382 } 383 } 384 return true; 385 } 386 387 public int getUsedLength() 388 { 389 return getUsedLengthFrom(m_ints.length); 390 } 391 392 public int getUsedLengthFrom(int from) 393 { 394 long[] a = m_ints; 395 from = Math.min(from, a.length); 396 397 if (from < 1) 398 { 399 return 0; 400 } 401 402 // Check if first element will act as sentinel 403 if (a[0] != 0) 404 { 405 while (a[--from] == 0) 406 { 407 } 408 return from + 1; 409 } 410 411 do 412 { 413 if (a[--from] != 0) 414 { 415 return from + 1; 416 } 417 } 418 while (from > 0); 419 420 return 0; 421 } 422 423 public int degree() 424 { 425 int i = m_ints.length; 426 long w; 427 do 428 { 429 if (i == 0) 430 { 431 return 0; 432 } 433 w = m_ints[--i]; 434 } 435 while (w == 0); 436 437 return (i << 6) + bitLength(w); 438 } 439 440 private int degreeFrom(int limit) 441 { 442 int i = (limit + 62) >>> 6; 443 long w; 444 do 445 { 446 if (i == 0) 447 { 448 return 0; 449 } 450 w = m_ints[--i]; 451 } 452 while (w == 0); 453 454 return (i << 6) + bitLength(w); 455 } 456 457// private int lowestCoefficient() 458// { 459// for (int i = 0; i < m_ints.length; ++i) 460// { 461// long mi = m_ints[i]; 462// if (mi != 0) 463// { 464// int j = 0; 465// while ((mi & 0xFFL) == 0) 466// { 467// j += 8; 468// mi >>>= 8; 469// } 470// while ((mi & 1L) == 0) 471// { 472// ++j; 473// mi >>>= 1; 474// } 475// return (i << 6) + j; 476// } 477// } 478// return -1; 479// } 480 481 private static int bitLength(long w) 482 { 483 int u = (int)(w >>> 32), b; 484 if (u == 0) 485 { 486 u = (int)w; 487 b = 0; 488 } 489 else 490 { 491 b = 32; 492 } 493 494 int t = u >>> 16, k; 495 if (t == 0) 496 { 497 t = u >>> 8; 498 k = (t == 0) ? bitLengths[u] : 8 + bitLengths[t]; 499 } 500 else 501 { 502 int v = t >>> 8; 503 k = (v == 0) ? 16 + bitLengths[t] : 24 + bitLengths[v]; 504 } 505 506 return b + k; 507 } 508 509 private long[] resizedInts(int newLen) 510 { 511 long[] newInts = new long[newLen]; 512 System.arraycopy(m_ints, 0, newInts, 0, Math.min(m_ints.length, newLen)); 513 return newInts; 514 } 515 516 public BigInteger toBigInteger() 517 { 518 int usedLen = getUsedLength(); 519 if (usedLen == 0) 520 { 521 return ECConstants.ZERO; 522 } 523 524 long highestInt = m_ints[usedLen - 1]; 525 byte[] temp = new byte[8]; 526 int barrI = 0; 527 boolean trailingZeroBytesDone = false; 528 for (int j = 7; j >= 0; j--) 529 { 530 byte thisByte = (byte)(highestInt >>> (8 * j)); 531 if (trailingZeroBytesDone || (thisByte != 0)) 532 { 533 trailingZeroBytesDone = true; 534 temp[barrI++] = thisByte; 535 } 536 } 537 538 int barrLen = 8 * (usedLen - 1) + barrI; 539 byte[] barr = new byte[barrLen]; 540 for (int j = 0; j < barrI; j++) 541 { 542 barr[j] = temp[j]; 543 } 544 // Highest value int is done now 545 546 for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) 547 { 548 long mi = m_ints[iarrJ]; 549 for (int j = 7; j >= 0; j--) 550 { 551 barr[barrI++] = (byte)(mi >>> (8 * j)); 552 } 553 } 554 return new BigInteger(1, barr); 555 } 556 557// private static long shiftUp(long[] x, int xOff, int count) 558// { 559// long prev = 0; 560// for (int i = 0; i < count; ++i) 561// { 562// long next = x[xOff + i]; 563// x[xOff + i] = (next << 1) | prev; 564// prev = next >>> 63; 565// } 566// return prev; 567// } 568 569 private static long shiftUp(long[] x, int xOff, int count, int shift) 570 { 571 int shiftInv = 64 - shift; 572 long prev = 0; 573 for (int i = 0; i < count; ++i) 574 { 575 long next = x[xOff + i]; 576 x[xOff + i] = (next << shift) | prev; 577 prev = next >>> shiftInv; 578 } 579 return prev; 580 } 581 582 private static long shiftUp(long[] x, int xOff, long[] z, int zOff, int count, int shift) 583 { 584 int shiftInv = 64 - shift; 585 long prev = 0; 586 for (int i = 0; i < count; ++i) 587 { 588 long next = x[xOff + i]; 589 z[zOff + i] = (next << shift) | prev; 590 prev = next >>> shiftInv; 591 } 592 return prev; 593 } 594 595 public LongArray addOne() 596 { 597 if (m_ints.length == 0) 598 { 599 return new LongArray(new long[]{ 1L }); 600 } 601 602 int resultLen = Math.max(1, getUsedLength()); 603 long[] ints = resizedInts(resultLen); 604 ints[0] ^= 1L; 605 return new LongArray(ints); 606 } 607 608// private void addShiftedByBits(LongArray other, int bits) 609// { 610// int words = bits >>> 6; 611// int shift = bits & 0x3F; 612// 613// if (shift == 0) 614// { 615// addShiftedByWords(other, words); 616// return; 617// } 618// 619// int otherUsedLen = other.getUsedLength(); 620// if (otherUsedLen == 0) 621// { 622// return; 623// } 624// 625// int minLen = otherUsedLen + words + 1; 626// if (minLen > m_ints.length) 627// { 628// m_ints = resizedInts(minLen); 629// } 630// 631// long carry = addShiftedByBits(m_ints, words, other.m_ints, 0, otherUsedLen, shift); 632// m_ints[otherUsedLen + words] ^= carry; 633// } 634 635 private void addShiftedByBitsSafe(LongArray other, int otherDegree, int bits) 636 { 637 int otherLen = (otherDegree + 63) >>> 6; 638 639 int words = bits >>> 6; 640 int shift = bits & 0x3F; 641 642 if (shift == 0) 643 { 644 add(m_ints, words, other.m_ints, 0, otherLen); 645 return; 646 } 647 648 long carry = addShiftedUp(m_ints, words, other.m_ints, 0, otherLen, shift); 649 if (carry != 0L) 650 { 651 m_ints[otherLen + words] ^= carry; 652 } 653 } 654 655 private static long addShiftedUp(long[] x, int xOff, long[] y, int yOff, int count, int shift) 656 { 657 int shiftInv = 64 - shift; 658 long prev = 0; 659 for (int i = 0; i < count; ++i) 660 { 661 long next = y[yOff + i]; 662 x[xOff + i] ^= (next << shift) | prev; 663 prev = next >>> shiftInv; 664 } 665 return prev; 666 } 667 668 private static long addShiftedDown(long[] x, int xOff, long[] y, int yOff, int count, int shift) 669 { 670 int shiftInv = 64 - shift; 671 long prev = 0; 672 int i = count; 673 while (--i >= 0) 674 { 675 long next = y[yOff + i]; 676 x[xOff + i] ^= (next >>> shift) | prev; 677 prev = next << shiftInv; 678 } 679 return prev; 680 } 681 682 public void addShiftedByWords(LongArray other, int words) 683 { 684 int otherUsedLen = other.getUsedLength(); 685 if (otherUsedLen == 0) 686 { 687 return; 688 } 689 690 int minLen = otherUsedLen + words; 691 if (minLen > m_ints.length) 692 { 693 m_ints = resizedInts(minLen); 694 } 695 696 add(m_ints, words, other.m_ints, 0, otherUsedLen); 697 } 698 699 private static void add(long[] x, int xOff, long[] y, int yOff, int count) 700 { 701 for (int i = 0; i < count; ++i) 702 { 703 x[xOff + i] ^= y[yOff + i]; 704 } 705 } 706 707 private static void add(long[] x, int xOff, long[] y, int yOff, long[] z, int zOff, int count) 708 { 709 for (int i = 0; i < count; ++i) 710 { 711 z[zOff + i] = x[xOff + i] ^ y[yOff + i]; 712 } 713 } 714 715 private static void addBoth(long[] x, int xOff, long[] y1, int y1Off, long[] y2, int y2Off, int count) 716 { 717 for (int i = 0; i < count; ++i) 718 { 719 x[xOff + i] ^= y1[y1Off + i] ^ y2[y2Off + i]; 720 } 721 } 722 723 private static void distribute(long[] x, int src, int dst1, int dst2, int count) 724 { 725 for (int i = 0; i < count; ++i) 726 { 727 long v = x[src + i]; 728 x[dst1 + i] ^= v; 729 x[dst2 + i] ^= v; 730 } 731 } 732 733 public int getLength() 734 { 735 return m_ints.length; 736 } 737 738 private static void flipWord(long[] buf, int off, int bit, long word) 739 { 740 int n = off + (bit >>> 6); 741 int shift = bit & 0x3F; 742 if (shift == 0) 743 { 744 buf[n] ^= word; 745 } 746 else 747 { 748 buf[n] ^= word << shift; 749 word >>>= (64 - shift); 750 if (word != 0) 751 { 752 buf[++n] ^= word; 753 } 754 } 755 } 756 757// private static long getWord(long[] buf, int off, int len, int bit) 758// { 759// int n = off + (bit >>> 6); 760// int shift = bit & 0x3F; 761// if (shift == 0) 762// { 763// return buf[n]; 764// } 765// long result = buf[n] >>> shift; 766// if (++n < len) 767// { 768// result |= buf[n] << (64 - shift); 769// } 770// return result; 771// } 772 773 public boolean testBitZero() 774 { 775 return m_ints.length > 0 && (m_ints[0] & 1L) != 0; 776 } 777 778 private static boolean testBit(long[] buf, int off, int n) 779 { 780 // theInt = n / 64 781 int theInt = n >>> 6; 782 // theBit = n % 64 783 int theBit = n & 0x3F; 784 long tester = 1L << theBit; 785 return (buf[off + theInt] & tester) != 0; 786 } 787 788 private static void flipBit(long[] buf, int off, int n) 789 { 790 // theInt = n / 64 791 int theInt = n >>> 6; 792 // theBit = n % 64 793 int theBit = n & 0x3F; 794 long flipper = 1L << theBit; 795 buf[off + theInt] ^= flipper; 796 } 797 798// private static void setBit(long[] buf, int off, int n) 799// { 800// // theInt = n / 64 801// int theInt = n >>> 6; 802// // theBit = n % 64 803// int theBit = n & 0x3F; 804// long setter = 1L << theBit; 805// buf[off + theInt] |= setter; 806// } 807// 808// private static void clearBit(long[] buf, int off, int n) 809// { 810// // theInt = n / 64 811// int theInt = n >>> 6; 812// // theBit = n % 64 813// int theBit = n & 0x3F; 814// long setter = 1L << theBit; 815// buf[off + theInt] &= ~setter; 816// } 817 818 private static void multiplyWord(long a, long[] b, int bLen, long[] c, int cOff) 819 { 820 if ((a & 1L) != 0L) 821 { 822 add(c, cOff, b, 0, bLen); 823 } 824 int k = 1; 825 while ((a >>>= 1) != 0) 826 { 827 if ((a & 1L) != 0L) 828 { 829 long carry = addShiftedUp(c, cOff, b, 0, bLen, k); 830 if (carry != 0) 831 { 832 c[cOff + bLen] ^= carry; 833 } 834 } 835 ++k; 836 } 837 } 838 839 public LongArray modMultiplyLD(LongArray other, int m, int[] ks) 840 { 841 /* 842 * Find out the degree of each argument and handle the zero cases 843 */ 844 int aDeg = degree(); 845 if (aDeg == 0) 846 { 847 return this; 848 } 849 int bDeg = other.degree(); 850 if (bDeg == 0) 851 { 852 return other; 853 } 854 855 /* 856 * Swap if necessary so that A is the smaller argument 857 */ 858 LongArray A = this, B = other; 859 if (aDeg > bDeg) 860 { 861 A = other; B = this; 862 int tmp = aDeg; aDeg = bDeg; bDeg = tmp; 863 } 864 865 /* 866 * Establish the word lengths of the arguments and result 867 */ 868 int aLen = (aDeg + 63) >>> 6; 869 int bLen = (bDeg + 63) >>> 6; 870 int cLen = (aDeg + bDeg + 62) >>> 6; 871 872 if (aLen == 1) 873 { 874 long a = A.m_ints[0]; 875 if (a == 1L) 876 { 877 return B; 878 } 879 880 /* 881 * Fast path for small A, with performance dependent only on the number of set bits 882 */ 883 long[] c = new long[cLen]; 884 multiplyWord(a, B.m_ints, bLen, c, 0); 885 886 /* 887 * Reduce the raw answer against the reduction coefficients 888 */ 889 return reduceResult(c, 0, cLen, m, ks); 890 } 891 892 /* 893 * Determine if B will get bigger during shifting 894 */ 895 int bMax = (bDeg + 7 + 63) >>> 6; 896 897 /* 898 * Lookup table for the offset of each B in the tables 899 */ 900 int[] ti = new int[16]; 901 902 /* 903 * Precompute table of all 4-bit products of B 904 */ 905 long[] T0 = new long[bMax << 4]; 906 int tOff = bMax; 907 ti[1] = tOff; 908 System.arraycopy(B.m_ints, 0, T0, tOff, bLen); 909 for (int i = 2; i < 16; ++i) 910 { 911 ti[i] = (tOff += bMax); 912 if ((i & 1) == 0) 913 { 914 shiftUp(T0, tOff >>> 1, T0, tOff, bMax, 1); 915 } 916 else 917 { 918 add(T0, bMax, T0, tOff - bMax, T0, tOff, bMax); 919 } 920 } 921 922 /* 923 * Second table with all 4-bit products of B shifted 4 bits 924 */ 925 long[] T1 = new long[T0.length]; 926 shiftUp(T0, 0, T1, 0, T0.length, 4); 927// shiftUp(T0, bMax, T1, bMax, tOff, 4); 928 929 long[] a = A.m_ints; 930 long[] c = new long[cLen]; 931 932 int MASK = 0xF; 933 934 /* 935 * Lopez-Dahab algorithm 936 */ 937 938 for (int k = 56; k >= 0; k -= 8) 939 { 940 for (int j = 1; j < aLen; j += 2) 941 { 942 int aVal = (int)(a[j] >>> k); 943 int u = aVal & MASK; 944 int v = (aVal >>> 4) & MASK; 945 addBoth(c, j - 1, T0, ti[u], T1, ti[v], bMax); 946 } 947 shiftUp(c, 0, cLen, 8); 948 } 949 950 for (int k = 56; k >= 0; k -= 8) 951 { 952 for (int j = 0; j < aLen; j += 2) 953 { 954 int aVal = (int)(a[j] >>> k); 955 int u = aVal & MASK; 956 int v = (aVal >>> 4) & MASK; 957 addBoth(c, j, T0, ti[u], T1, ti[v], bMax); 958 } 959 if (k > 0) 960 { 961 shiftUp(c, 0, cLen, 8); 962 } 963 } 964 965 /* 966 * Finally the raw answer is collected, reduce it against the reduction coefficients 967 */ 968 return reduceResult(c, 0, cLen, m, ks); 969 } 970 971 public LongArray modMultiply(LongArray other, int m, int[] ks) 972 { 973 /* 974 * Find out the degree of each argument and handle the zero cases 975 */ 976 int aDeg = degree(); 977 if (aDeg == 0) 978 { 979 return this; 980 } 981 int bDeg = other.degree(); 982 if (bDeg == 0) 983 { 984 return other; 985 } 986 987 /* 988 * Swap if necessary so that A is the smaller argument 989 */ 990 LongArray A = this, B = other; 991 if (aDeg > bDeg) 992 { 993 A = other; B = this; 994 int tmp = aDeg; aDeg = bDeg; bDeg = tmp; 995 } 996 997 /* 998 * Establish the word lengths of the arguments and result 999 */ 1000 int aLen = (aDeg + 63) >>> 6; 1001 int bLen = (bDeg + 63) >>> 6; 1002 int cLen = (aDeg + bDeg + 62) >>> 6; 1003 1004 if (aLen == 1) 1005 { 1006 long a = A.m_ints[0]; 1007 if (a == 1L) 1008 { 1009 return B; 1010 } 1011 1012 /* 1013 * Fast path for small A, with performance dependent only on the number of set bits 1014 */ 1015 long[] c = new long[cLen]; 1016 multiplyWord(a, B.m_ints, bLen, c, 0); 1017 1018 /* 1019 * Reduce the raw answer against the reduction coefficients 1020 */ 1021 return reduceResult(c, 0, cLen, m, ks); 1022 } 1023 1024 /* 1025 * Determine if B will get bigger during shifting 1026 */ 1027 int bMax = (bDeg + 7 + 63) >>> 6; 1028 1029 /* 1030 * Lookup table for the offset of each B in the tables 1031 */ 1032 int[] ti = new int[16]; 1033 1034 /* 1035 * Precompute table of all 4-bit products of B 1036 */ 1037 long[] T0 = new long[bMax << 4]; 1038 int tOff = bMax; 1039 ti[1] = tOff; 1040 System.arraycopy(B.m_ints, 0, T0, tOff, bLen); 1041 for (int i = 2; i < 16; ++i) 1042 { 1043 ti[i] = (tOff += bMax); 1044 if ((i & 1) == 0) 1045 { 1046 shiftUp(T0, tOff >>> 1, T0, tOff, bMax, 1); 1047 } 1048 else 1049 { 1050 add(T0, bMax, T0, tOff - bMax, T0, tOff, bMax); 1051 } 1052 } 1053 1054 /* 1055 * Second table with all 4-bit products of B shifted 4 bits 1056 */ 1057 long[] T1 = new long[T0.length]; 1058 shiftUp(T0, 0, T1, 0, T0.length, 4); 1059// shiftUp(T0, bMax, T1, bMax, tOff, 4); 1060 1061 long[] a = A.m_ints; 1062 long[] c = new long[cLen << 3]; 1063 1064 int MASK = 0xF; 1065 1066 /* 1067 * Lopez-Dahab (Modified) algorithm 1068 */ 1069 1070 for (int aPos = 0; aPos < aLen; ++aPos) 1071 { 1072 long aVal = a[aPos]; 1073 int cOff = aPos; 1074 for (;;) 1075 { 1076 int u = (int)aVal & MASK; 1077 aVal >>>= 4; 1078 int v = (int)aVal & MASK; 1079 addBoth(c, cOff, T0, ti[u], T1, ti[v], bMax); 1080 if ((aVal >>>= 4) == 0L) 1081 { 1082 break; 1083 } 1084 cOff += cLen; 1085 } 1086 } 1087 1088 int cOff = c.length; 1089 while ((cOff -= cLen) != 0) 1090 { 1091 addShiftedUp(c, cOff - cLen, c, cOff, cLen, 8); 1092 } 1093 1094 /* 1095 * Finally the raw answer is collected, reduce it against the reduction coefficients 1096 */ 1097 return reduceResult(c, 0, cLen, m, ks); 1098 } 1099 1100 public LongArray modMultiplyAlt(LongArray other, int m, int[] ks) 1101 { 1102 /* 1103 * Find out the degree of each argument and handle the zero cases 1104 */ 1105 int aDeg = degree(); 1106 if (aDeg == 0) 1107 { 1108 return this; 1109 } 1110 int bDeg = other.degree(); 1111 if (bDeg == 0) 1112 { 1113 return other; 1114 } 1115 1116 /* 1117 * Swap if necessary so that A is the smaller argument 1118 */ 1119 LongArray A = this, B = other; 1120 if (aDeg > bDeg) 1121 { 1122 A = other; B = this; 1123 int tmp = aDeg; aDeg = bDeg; bDeg = tmp; 1124 } 1125 1126 /* 1127 * Establish the word lengths of the arguments and result 1128 */ 1129 int aLen = (aDeg + 63) >>> 6; 1130 int bLen = (bDeg + 63) >>> 6; 1131 int cLen = (aDeg + bDeg + 62) >>> 6; 1132 1133 if (aLen == 1) 1134 { 1135 long a = A.m_ints[0]; 1136 if (a == 1L) 1137 { 1138 return B; 1139 } 1140 1141 /* 1142 * Fast path for small A, with performance dependent only on the number of set bits 1143 */ 1144 long[] c = new long[cLen]; 1145 multiplyWord(a, B.m_ints, bLen, c, 0); 1146 1147 /* 1148 * Reduce the raw answer against the reduction coefficients 1149 */ 1150 return reduceResult(c, 0, cLen, m, ks); 1151 } 1152 1153 // NOTE: This works, but is slower than width 4 processing 1154// if (aLen == 2) 1155// { 1156// /* 1157// * Use common-multiplicand optimization to save ~1/4 of the adds 1158// */ 1159// long a1 = A.m_ints[0], a2 = A.m_ints[1]; 1160// long aa = a1 & a2; a1 ^= aa; a2 ^= aa; 1161// 1162// long[] b = B.m_ints; 1163// long[] c = new long[cLen]; 1164// multiplyWord(aa, b, bLen, c, 1); 1165// add(c, 0, c, 1, cLen - 1); 1166// multiplyWord(a1, b, bLen, c, 0); 1167// multiplyWord(a2, b, bLen, c, 1); 1168// 1169// /* 1170// * Reduce the raw answer against the reduction coefficients 1171// */ 1172// return reduceResult(c, 0, cLen, m, ks); 1173// } 1174 1175 /* 1176 * Determine the parameters of the interleaved window algorithm: the 'width' in bits to 1177 * process together, the number of evaluation 'positions' implied by that width, and the 1178 * 'top' position at which the regular window algorithm stops. 1179 */ 1180 int width, positions, top, banks; 1181 1182 // NOTE: width 4 is the fastest over the entire range of sizes used in current crypto 1183// width = 1; positions = 64; top = 64; banks = 4; 1184// width = 2; positions = 32; top = 64; banks = 4; 1185// width = 3; positions = 21; top = 63; banks = 3; 1186 width = 4; positions = 16; top = 64; banks = 8; 1187// width = 5; positions = 13; top = 65; banks = 7; 1188// width = 7; positions = 9; top = 63; banks = 9; 1189// width = 8; positions = 8; top = 64; banks = 8; 1190 1191 /* 1192 * Determine if B will get bigger during shifting 1193 */ 1194 int shifts = top < 64 ? positions : positions - 1; 1195 int bMax = (bDeg + shifts + 63) >>> 6; 1196 1197 int bTotal = bMax * banks, stride = width * banks; 1198 1199 /* 1200 * Create a single temporary buffer, with an offset table to find the positions of things in it 1201 */ 1202 int[] ci = new int[1 << width]; 1203 int cTotal = aLen; 1204 { 1205 ci[0] = cTotal; 1206 cTotal += bTotal; 1207 ci[1] = cTotal; 1208 for (int i = 2; i < ci.length; ++i) 1209 { 1210 cTotal += cLen; 1211 ci[i] = cTotal; 1212 } 1213 cTotal += cLen; 1214 } 1215 // NOTE: Provide a safe dump for "high zeroes" since we are adding 'bMax' and not 'bLen' 1216 ++cTotal; 1217 1218 long[] c = new long[cTotal]; 1219 1220 // Prepare A in interleaved form, according to the chosen width 1221 interleave(A.m_ints, 0, c, 0, aLen, width); 1222 1223 // Make a working copy of B, since we will be shifting it 1224 { 1225 int bOff = aLen; 1226 System.arraycopy(B.m_ints, 0, c, bOff, bLen); 1227 for (int bank = 1; bank < banks; ++bank) 1228 { 1229 shiftUp(c, aLen, c, bOff += bMax, bMax, bank); 1230 } 1231 } 1232 1233 /* 1234 * The main loop analyzes the interleaved windows in A, and for each non-zero window 1235 * a single word-array XOR is performed to a carefully selected slice of 'c'. The loop is 1236 * breadth-first, checking the lowest window in each word, then looping again for the 1237 * next higher window position. 1238 */ 1239 int MASK = (1 << width) - 1; 1240 1241 int k = 0; 1242 for (;;) 1243 { 1244 int aPos = 0; 1245 do 1246 { 1247 long aVal = c[aPos] >>> k; 1248 int bank = 0, bOff = aLen; 1249 for (;;) 1250 { 1251 int index = (int)(aVal) & MASK; 1252 if (index != 0) 1253 { 1254 /* 1255 * Add to a 'c' buffer based on the bit-pattern of 'index'. Since A is in 1256 * interleaved form, the bits represent the current B shifted by 0, 'positions', 1257 * 'positions' * 2, ..., 'positions' * ('width' - 1) 1258 */ 1259 add(c, aPos + ci[index], c, bOff, bMax); 1260 } 1261 if (++bank == banks) 1262 { 1263 break; 1264 } 1265 bOff += bMax; 1266 aVal >>>= width; 1267 } 1268 } 1269 while (++aPos < aLen); 1270 1271 if ((k += stride) >= top) 1272 { 1273 if (k >= 64) 1274 { 1275 break; 1276 } 1277 1278 /* 1279 * Adjustment for window setups with top == 63, the final bit (if any) is processed 1280 * as the top-bit of a window 1281 */ 1282 k = 64 - width; 1283 MASK &= MASK << (top - k); 1284 } 1285 1286 /* 1287 * After each position has been checked for all words of A, B is shifted up 1 place 1288 */ 1289 shiftUp(c, aLen, bTotal, banks); 1290 } 1291 1292 int ciPos = ci.length; 1293 while (--ciPos > 1) 1294 { 1295 if ((ciPos & 1L) == 0L) 1296 { 1297 /* 1298 * For even numbers, shift contents and add to the half-position 1299 */ 1300 addShiftedUp(c, ci[ciPos >>> 1], c, ci[ciPos], cLen, positions); 1301 } 1302 else 1303 { 1304 /* 1305 * For odd numbers, 'distribute' contents to the result and the next-lowest position 1306 */ 1307 distribute(c, ci[ciPos], ci[ciPos - 1], ci[1], cLen); 1308 } 1309 } 1310 1311 /* 1312 * Finally the raw answer is collected, reduce it against the reduction coefficients 1313 */ 1314 return reduceResult(c, ci[1], cLen, m, ks); 1315 } 1316 1317 private static LongArray reduceResult(long[] buf, int off, int len, int m, int[] ks) 1318 { 1319 int rLen = reduceInPlace(buf, off, len, m, ks); 1320 return new LongArray(buf, off, rLen); 1321 } 1322 1323// private static void deInterleave(long[] x, int xOff, long[] z, int zOff, int count, int rounds) 1324// { 1325// for (int i = 0; i < count; ++i) 1326// { 1327// z[zOff + i] = deInterleave(x[zOff + i], rounds); 1328// } 1329// } 1330// 1331// private static long deInterleave(long x, int rounds) 1332// { 1333// while (--rounds >= 0) 1334// { 1335// x = deInterleave32(x & DEINTERLEAVE_MASK) | (deInterleave32((x >>> 1) & DEINTERLEAVE_MASK) << 32); 1336// } 1337// return x; 1338// } 1339// 1340// private static long deInterleave32(long x) 1341// { 1342// x = (x | (x >>> 1)) & 0x3333333333333333L; 1343// x = (x | (x >>> 2)) & 0x0F0F0F0F0F0F0F0FL; 1344// x = (x | (x >>> 4)) & 0x00FF00FF00FF00FFL; 1345// x = (x | (x >>> 8)) & 0x0000FFFF0000FFFFL; 1346// x = (x | (x >>> 16)) & 0x00000000FFFFFFFFL; 1347// return x; 1348// } 1349 1350 private static int reduceInPlace(long[] buf, int off, int len, int m, int[] ks) 1351 { 1352 int mLen = (m + 63) >>> 6; 1353 if (len < mLen) 1354 { 1355 return len; 1356 } 1357 1358 int numBits = Math.min(len << 6, (m << 1) - 1); // TODO use actual degree? 1359 int excessBits = (len << 6) - numBits; 1360 while (excessBits >= 64) 1361 { 1362 --len; 1363 excessBits -= 64; 1364 } 1365 1366 int kLen = ks.length, kMax = ks[kLen - 1], kNext = kLen > 1 ? ks[kLen - 2] : 0; 1367 int wordWiseLimit = Math.max(m, kMax + 64); 1368 int vectorableWords = (excessBits + Math.min(numBits - wordWiseLimit, m - kNext)) >> 6; 1369 if (vectorableWords > 1) 1370 { 1371 int vectorWiseWords = len - vectorableWords; 1372 reduceVectorWise(buf, off, len, vectorWiseWords, m, ks); 1373 while (len > vectorWiseWords) 1374 { 1375 buf[off + --len] = 0L; 1376 } 1377 numBits = vectorWiseWords << 6; 1378 } 1379 1380 if (numBits > wordWiseLimit) 1381 { 1382 reduceWordWise(buf, off, len, wordWiseLimit, m, ks); 1383 numBits = wordWiseLimit; 1384 } 1385 1386 if (numBits > m) 1387 { 1388 reduceBitWise(buf, off, numBits, m, ks); 1389 } 1390 1391 return mLen; 1392 } 1393 1394 private static void reduceBitWise(long[] buf, int off, int bitlength, int m, int[] ks) 1395 { 1396 while (--bitlength >= m) 1397 { 1398 if (testBit(buf, off, bitlength)) 1399 { 1400 reduceBit(buf, off, bitlength, m, ks); 1401 } 1402 } 1403 } 1404 1405 private static void reduceBit(long[] buf, int off, int bit, int m, int[] ks) 1406 { 1407 flipBit(buf, off, bit); 1408 int base = bit - m; 1409 int j = ks.length; 1410 while (--j >= 0) 1411 { 1412 flipBit(buf, off, ks[j] + base); 1413 } 1414 flipBit(buf, off, base); 1415 } 1416 1417 private static void reduceWordWise(long[] buf, int off, int len, int toBit, int m, int[] ks) 1418 { 1419 int toPos = toBit >>> 6; 1420 1421 while (--len > toPos) 1422 { 1423 long word = buf[off + len]; 1424 if (word != 0) 1425 { 1426 buf[off + len] = 0; 1427 reduceWord(buf, off, (len << 6), word, m, ks); 1428 } 1429 } 1430 1431 int partial = toBit & 0x3F; 1432 long word = buf[off + toPos] >>> partial; 1433 if (word != 0) 1434 { 1435 buf[off + toPos] ^= word << partial; 1436 reduceWord(buf, off, toBit, word, m, ks); 1437 } 1438 } 1439 1440 private static void reduceWord(long[] buf, int off, int bit, long word, int m, int[] ks) 1441 { 1442 int offset = bit - m; 1443 int j = ks.length; 1444 while (--j >= 0) 1445 { 1446 flipWord(buf, off, offset + ks[j], word); 1447 } 1448 flipWord(buf, off, offset, word); 1449 } 1450 1451 private static void reduceVectorWise(long[] buf, int off, int len, int words, int m, int[] ks) 1452 { 1453 /* 1454 * NOTE: It's important we go from highest coefficient to lowest, because for the highest 1455 * one (only) we allow the ranges to partially overlap, and therefore any changes must take 1456 * effect for the subsequent lower coefficients. 1457 */ 1458 int baseBit = (words << 6) - m; 1459 int j = ks.length; 1460 while (--j >= 0) 1461 { 1462 flipVector(buf, off, buf, off + words, len - words, baseBit + ks[j]); 1463 } 1464 flipVector(buf, off, buf, off + words, len - words, baseBit); 1465 } 1466 1467 private static void flipVector(long[] x, int xOff, long[] y, int yOff, int yLen, int bits) 1468 { 1469 xOff += bits >>> 6; 1470 bits &= 0x3F; 1471 1472 if (bits == 0) 1473 { 1474 add(x, xOff, y, yOff, yLen); 1475 } 1476 else 1477 { 1478 long carry = addShiftedDown(x, xOff + 1, y, yOff, yLen, 64 - bits); 1479 x[xOff] ^= carry; 1480 } 1481 } 1482 1483 public LongArray modSquare(int m, int[] ks) 1484 { 1485 int len = getUsedLength(); 1486 if (len == 0) 1487 { 1488 return this; 1489 } 1490 1491 int _2len = len << 1; 1492 long[] r = new long[_2len]; 1493 1494 int pos = 0; 1495 while (pos < _2len) 1496 { 1497 long mi = m_ints[pos >>> 1]; 1498 r[pos++] = interleave2_32to64((int)mi); 1499 r[pos++] = interleave2_32to64((int)(mi >>> 32)); 1500 } 1501 1502 return new LongArray(r, 0, reduceInPlace(r, 0, r.length, m, ks)); 1503 } 1504 1505// private LongArray modSquareN(int n, int m, int[] ks) 1506// { 1507// int len = getUsedLength(); 1508// if (len == 0) 1509// { 1510// return this; 1511// } 1512// 1513// int mLen = (m + 63) >>> 6; 1514// long[] r = new long[mLen << 1]; 1515// System.arraycopy(m_ints, 0, r, 0, len); 1516// 1517// while (--n >= 0) 1518// { 1519// squareInPlace(r, len, m, ks); 1520// len = reduceInPlace(r, 0, r.length, m, ks); 1521// } 1522// 1523// return new LongArray(r, 0, len); 1524// } 1525// 1526// private static void squareInPlace(long[] x, int xLen, int m, int[] ks) 1527// { 1528// int pos = xLen << 1; 1529// while (--xLen >= 0) 1530// { 1531// long xVal = x[xLen]; 1532// x[--pos] = interleave2_32to64((int)(xVal >>> 32)); 1533// x[--pos] = interleave2_32to64((int)xVal); 1534// } 1535// } 1536 1537 private static void interleave(long[] x, int xOff, long[] z, int zOff, int count, int width) 1538 { 1539 switch (width) 1540 { 1541 case 3: 1542 interleave3(x, xOff, z, zOff, count); 1543 break; 1544 case 5: 1545 interleave5(x, xOff, z, zOff, count); 1546 break; 1547 case 7: 1548 interleave7(x, xOff, z, zOff, count); 1549 break; 1550 default: 1551 interleave2_n(x, xOff, z, zOff, count, bitLengths[width] - 1); 1552 break; 1553 } 1554 } 1555 1556 private static void interleave3(long[] x, int xOff, long[] z, int zOff, int count) 1557 { 1558 for (int i = 0; i < count; ++i) 1559 { 1560 z[zOff + i] = interleave3(x[xOff + i]); 1561 } 1562 } 1563 1564 private static long interleave3(long x) 1565 { 1566 long z = x & (1L << 63); 1567 return z 1568 | interleave3_21to63((int)x & 0x1FFFFF) 1569 | interleave3_21to63((int)(x >>> 21) & 0x1FFFFF) << 1 1570 | interleave3_21to63((int)(x >>> 42) & 0x1FFFFF) << 2; 1571 1572// int zPos = 0, wPos = 0, xPos = 0; 1573// for (;;) 1574// { 1575// z |= ((x >>> xPos) & 1L) << zPos; 1576// if (++zPos == 63) 1577// { 1578// String sz2 = Long.toBinaryString(z); 1579// return z; 1580// } 1581// if ((xPos += 21) >= 63) 1582// { 1583// xPos = ++wPos; 1584// } 1585// } 1586 } 1587 1588 private static long interleave3_21to63(int x) 1589 { 1590 int r00 = INTERLEAVE3_TABLE[x & 0x7F]; 1591 int r21 = INTERLEAVE3_TABLE[(x >>> 7) & 0x7F]; 1592 int r42 = INTERLEAVE3_TABLE[x >>> 14]; 1593 return (r42 & 0xFFFFFFFFL) << 42 | (r21 & 0xFFFFFFFFL) << 21 | (r00 & 0xFFFFFFFFL); 1594 } 1595 1596 private static void interleave5(long[] x, int xOff, long[] z, int zOff, int count) 1597 { 1598 for (int i = 0; i < count; ++i) 1599 { 1600 z[zOff + i] = interleave5(x[xOff + i]); 1601 } 1602 } 1603 1604 private static long interleave5(long x) 1605 { 1606 return interleave3_13to65((int)x & 0x1FFF) 1607 | interleave3_13to65((int)(x >>> 13) & 0x1FFF) << 1 1608 | interleave3_13to65((int)(x >>> 26) & 0x1FFF) << 2 1609 | interleave3_13to65((int)(x >>> 39) & 0x1FFF) << 3 1610 | interleave3_13to65((int)(x >>> 52) & 0x1FFF) << 4; 1611 1612// long z = 0; 1613// int zPos = 0, wPos = 0, xPos = 0; 1614// for (;;) 1615// { 1616// z |= ((x >>> xPos) & 1L) << zPos; 1617// if (++zPos == 64) 1618// { 1619// return z; 1620// } 1621// if ((xPos += 13) >= 64) 1622// { 1623// xPos = ++wPos; 1624// } 1625// } 1626 } 1627 1628 private static long interleave3_13to65(int x) 1629 { 1630 int r00 = INTERLEAVE5_TABLE[x & 0x7F]; 1631 int r35 = INTERLEAVE5_TABLE[x >>> 7]; 1632 return (r35 & 0xFFFFFFFFL) << 35 | (r00 & 0xFFFFFFFFL); 1633 } 1634 1635 private static void interleave7(long[] x, int xOff, long[] z, int zOff, int count) 1636 { 1637 for (int i = 0; i < count; ++i) 1638 { 1639 z[zOff + i] = interleave7(x[xOff + i]); 1640 } 1641 } 1642 1643 private static long interleave7(long x) 1644 { 1645 long z = x & (1L << 63); 1646 return z 1647 | INTERLEAVE7_TABLE[(int)x & 0x1FF] 1648 | INTERLEAVE7_TABLE[(int)(x >>> 9) & 0x1FF] << 1 1649 | INTERLEAVE7_TABLE[(int)(x >>> 18) & 0x1FF] << 2 1650 | INTERLEAVE7_TABLE[(int)(x >>> 27) & 0x1FF] << 3 1651 | INTERLEAVE7_TABLE[(int)(x >>> 36) & 0x1FF] << 4 1652 | INTERLEAVE7_TABLE[(int)(x >>> 45) & 0x1FF] << 5 1653 | INTERLEAVE7_TABLE[(int)(x >>> 54) & 0x1FF] << 6; 1654 1655// int zPos = 0, wPos = 0, xPos = 0; 1656// for (;;) 1657// { 1658// z |= ((x >>> xPos) & 1L) << zPos; 1659// if (++zPos == 63) 1660// { 1661// return z; 1662// } 1663// if ((xPos += 9) >= 63) 1664// { 1665// xPos = ++wPos; 1666// } 1667// } 1668 } 1669 1670 private static void interleave2_n(long[] x, int xOff, long[] z, int zOff, int count, int rounds) 1671 { 1672 for (int i = 0; i < count; ++i) 1673 { 1674 z[zOff + i] = interleave2_n(x[xOff + i], rounds); 1675 } 1676 } 1677 1678 private static long interleave2_n(long x, int rounds) 1679 { 1680 while (rounds > 1) 1681 { 1682 rounds -= 2; 1683 x = interleave4_16to64((int)x & 0xFFFF) 1684 | interleave4_16to64((int)(x >>> 16) & 0xFFFF) << 1 1685 | interleave4_16to64((int)(x >>> 32) & 0xFFFF) << 2 1686 | interleave4_16to64((int)(x >>> 48) & 0xFFFF) << 3; 1687 } 1688 if (rounds > 0) 1689 { 1690 x = interleave2_32to64((int)x) | interleave2_32to64((int)(x >>> 32)) << 1; 1691 } 1692 return x; 1693 } 1694 1695 private static long interleave4_16to64(int x) 1696 { 1697 int r00 = INTERLEAVE4_TABLE[x & 0xFF]; 1698 int r32 = INTERLEAVE4_TABLE[x >>> 8]; 1699 return (r32 & 0xFFFFFFFFL) << 32 | (r00 & 0xFFFFFFFFL); 1700 } 1701 1702 private static long interleave2_32to64(int x) 1703 { 1704 int r00 = INTERLEAVE2_TABLE[x & 0xFF] | INTERLEAVE2_TABLE[(x >>> 8) & 0xFF] << 16; 1705 int r32 = INTERLEAVE2_TABLE[(x >>> 16) & 0xFF] | INTERLEAVE2_TABLE[x >>> 24] << 16; 1706 return (r32 & 0xFFFFFFFFL) << 32 | (r00 & 0xFFFFFFFFL); 1707 } 1708 1709// private static LongArray expItohTsujii2(LongArray B, int n, int m, int[] ks) 1710// { 1711// LongArray t1 = B, t3 = new LongArray(new long[]{ 1L }); 1712// int scale = 1; 1713// 1714// int numTerms = n; 1715// while (numTerms > 1) 1716// { 1717// if ((numTerms & 1) != 0) 1718// { 1719// t3 = t3.modMultiply(t1, m, ks); 1720// t1 = t1.modSquareN(scale, m, ks); 1721// } 1722// 1723// LongArray t2 = t1.modSquareN(scale, m, ks); 1724// t1 = t1.modMultiply(t2, m, ks); 1725// numTerms >>>= 1; scale <<= 1; 1726// } 1727// 1728// return t3.modMultiply(t1, m, ks); 1729// } 1730// 1731// private static LongArray expItohTsujii23(LongArray B, int n, int m, int[] ks) 1732// { 1733// LongArray t1 = B, t3 = new LongArray(new long[]{ 1L }); 1734// int scale = 1; 1735// 1736// int numTerms = n; 1737// while (numTerms > 1) 1738// { 1739// boolean m03 = numTerms % 3 == 0; 1740// boolean m14 = !m03 && (numTerms & 1) != 0; 1741// 1742// if (m14) 1743// { 1744// t3 = t3.modMultiply(t1, m, ks); 1745// t1 = t1.modSquareN(scale, m, ks); 1746// } 1747// 1748// LongArray t2 = t1.modSquareN(scale, m, ks); 1749// t1 = t1.modMultiply(t2, m, ks); 1750// 1751// if (m03) 1752// { 1753// t2 = t2.modSquareN(scale, m, ks); 1754// t1 = t1.modMultiply(t2, m, ks); 1755// numTerms /= 3; scale *= 3; 1756// } 1757// else 1758// { 1759// numTerms >>>= 1; scale <<= 1; 1760// } 1761// } 1762// 1763// return t3.modMultiply(t1, m, ks); 1764// } 1765// 1766// private static LongArray expItohTsujii235(LongArray B, int n, int m, int[] ks) 1767// { 1768// LongArray t1 = B, t4 = new LongArray(new long[]{ 1L }); 1769// int scale = 1; 1770// 1771// int numTerms = n; 1772// while (numTerms > 1) 1773// { 1774// if (numTerms % 5 == 0) 1775// { 1776//// t1 = expItohTsujii23(t1, 5, m, ks); 1777// 1778// LongArray t3 = t1; 1779// t1 = t1.modSquareN(scale, m, ks); 1780// 1781// LongArray t2 = t1.modSquareN(scale, m, ks); 1782// t1 = t1.modMultiply(t2, m, ks); 1783// t2 = t1.modSquareN(scale << 1, m, ks); 1784// t1 = t1.modMultiply(t2, m, ks); 1785// 1786// t1 = t1.modMultiply(t3, m, ks); 1787// 1788// numTerms /= 5; scale *= 5; 1789// continue; 1790// } 1791// 1792// boolean m03 = numTerms % 3 == 0; 1793// boolean m14 = !m03 && (numTerms & 1) != 0; 1794// 1795// if (m14) 1796// { 1797// t4 = t4.modMultiply(t1, m, ks); 1798// t1 = t1.modSquareN(scale, m, ks); 1799// } 1800// 1801// LongArray t2 = t1.modSquareN(scale, m, ks); 1802// t1 = t1.modMultiply(t2, m, ks); 1803// 1804// if (m03) 1805// { 1806// t2 = t2.modSquareN(scale, m, ks); 1807// t1 = t1.modMultiply(t2, m, ks); 1808// numTerms /= 3; scale *= 3; 1809// } 1810// else 1811// { 1812// numTerms >>>= 1; scale <<= 1; 1813// } 1814// } 1815// 1816// return t4.modMultiply(t1, m, ks); 1817// } 1818 1819 public LongArray modInverse(int m, int[] ks) 1820 { 1821 /* 1822 * Fermat's Little Theorem 1823 */ 1824// LongArray A = this; 1825// LongArray B = A.modSquare(m, ks); 1826// LongArray R0 = B, R1 = B; 1827// for (int i = 2; i < m; ++i) 1828// { 1829// R1 = R1.modSquare(m, ks); 1830// R0 = R0.modMultiply(R1, m, ks); 1831// } 1832// 1833// return R0; 1834 1835 /* 1836 * Itoh-Tsujii 1837 */ 1838// LongArray B = modSquare(m, ks); 1839// switch (m) 1840// { 1841// case 409: 1842// return expItohTsujii23(B, m - 1, m, ks); 1843// case 571: 1844// return expItohTsujii235(B, m - 1, m, ks); 1845// case 163: 1846// case 233: 1847// case 283: 1848// default: 1849// return expItohTsujii2(B, m - 1, m, ks); 1850// } 1851 1852 /* 1853 * Inversion in F2m using the extended Euclidean algorithm 1854 * 1855 * Input: A nonzero polynomial a(z) of degree at most m-1 1856 * Output: a(z)^(-1) mod f(z) 1857 */ 1858 int uzDegree = degree(); 1859 if (uzDegree == 1) 1860 { 1861 return this; 1862 } 1863 1864 // u(z) := a(z) 1865 LongArray uz = (LongArray)clone(); 1866 1867 int t = (m + 63) >>> 6; 1868 1869 // v(z) := f(z) 1870 LongArray vz = new LongArray(t); 1871 reduceBit(vz.m_ints, 0, m, m, ks); 1872 1873 // g1(z) := 1, g2(z) := 0 1874 LongArray g1z = new LongArray(t); 1875 g1z.m_ints[0] = 1L; 1876 LongArray g2z = new LongArray(t); 1877 1878 int[] uvDeg = new int[]{ uzDegree, m + 1 }; 1879 LongArray[] uv = new LongArray[]{ uz, vz }; 1880 1881 int[] ggDeg = new int[]{ 1, 0 }; 1882 LongArray[] gg = new LongArray[]{ g1z, g2z }; 1883 1884 int b = 1; 1885 int duv1 = uvDeg[b]; 1886 int dgg1 = ggDeg[b]; 1887 int j = duv1 - uvDeg[1 - b]; 1888 1889 for (;;) 1890 { 1891 if (j < 0) 1892 { 1893 j = -j; 1894 uvDeg[b] = duv1; 1895 ggDeg[b] = dgg1; 1896 b = 1 - b; 1897 duv1 = uvDeg[b]; 1898 dgg1 = ggDeg[b]; 1899 } 1900 1901 uv[b].addShiftedByBitsSafe(uv[1 - b], uvDeg[1 - b], j); 1902 1903 int duv2 = uv[b].degreeFrom(duv1); 1904 if (duv2 == 0) 1905 { 1906 return gg[1 - b]; 1907 } 1908 1909 { 1910 int dgg2 = ggDeg[1 - b]; 1911 gg[b].addShiftedByBitsSafe(gg[1 - b], dgg2, j); 1912 dgg2 += j; 1913 1914 if (dgg2 > dgg1) 1915 { 1916 dgg1 = dgg2; 1917 } 1918 else if (dgg2 == dgg1) 1919 { 1920 dgg1 = gg[b].degreeFrom(dgg1); 1921 } 1922 } 1923 1924 j += (duv2 - duv1); 1925 duv1 = duv2; 1926 } 1927 } 1928 1929 public boolean equals(Object o) 1930 { 1931 if (!(o instanceof LongArray)) 1932 { 1933 return false; 1934 } 1935 LongArray other = (LongArray) o; 1936 int usedLen = getUsedLength(); 1937 if (other.getUsedLength() != usedLen) 1938 { 1939 return false; 1940 } 1941 for (int i = 0; i < usedLen; i++) 1942 { 1943 if (m_ints[i] != other.m_ints[i]) 1944 { 1945 return false; 1946 } 1947 } 1948 return true; 1949 } 1950 1951 public int hashCode() 1952 { 1953 int usedLen = getUsedLength(); 1954 int hash = 1; 1955 for (int i = 0; i < usedLen; i++) 1956 { 1957 long mi = m_ints[i]; 1958 hash *= 31; 1959 hash ^= (int)mi; 1960 hash *= 31; 1961 hash ^= (int)(mi >>> 32); 1962 } 1963 return hash; 1964 } 1965 1966 public Object clone() 1967 { 1968 return new LongArray(Arrays.clone(m_ints)); 1969 } 1970 1971 public String toString() 1972 { 1973 int i = getUsedLength(); 1974 if (i == 0) 1975 { 1976 return "0"; 1977 } 1978 1979 StringBuffer sb = new StringBuffer(Long.toBinaryString(m_ints[--i])); 1980 while (--i >= 0) 1981 { 1982 String s = Long.toBinaryString(m_ints[i]); 1983 1984 // Add leading zeroes, except for highest significant word 1985 int len = s.length(); 1986 if (len < 64) 1987 { 1988 sb.append(ZEROES.substring(len)); 1989 } 1990 1991 sb.append(s); 1992 } 1993 return sb.toString(); 1994 } 1995}