|
1 /* |
|
2 * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved. |
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
|
4 * |
|
5 * This code is free software; you can redistribute it and/or modify it |
|
6 * under the terms of the GNU General Public License version 2 only, as |
|
7 * published by the Free Software Foundation. Oracle designates this |
|
8 * particular file as subject to the "Classpath" exception as provided |
|
9 * by Oracle in the LICENSE file that accompanied this code. |
|
10 * |
|
11 * This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 * version 2 for more details (a copy is included in the LICENSE file that |
|
15 * accompanied this code). |
|
16 * |
|
17 * You should have received a copy of the GNU General Public License version |
|
18 * 2 along with this work; if not, write to the Free Software Foundation, |
|
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 * |
|
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
22 * or visit www.oracle.com if you need additional information or have any |
|
23 * questions. |
|
24 */ |
|
25 |
|
26 package sun.security.util.math.intpoly; |
|
27 |
|
28 import java.math.BigInteger; |
|
29 |
|
30 public class IntegerPolynomial448 extends IntegerPolynomial { |
|
31 |
|
32 private static final int POWER = 448; |
|
33 private static final int NUM_LIMBS = 16; |
|
34 private static final int BITS_PER_LIMB = 28; |
|
35 public static final BigInteger MODULUS |
|
36 = TWO.pow(POWER).subtract(TWO.pow(POWER / 2)) |
|
37 .subtract(BigInteger.valueOf(1)); |
|
38 |
|
39 public IntegerPolynomial448() { |
|
40 super(BITS_PER_LIMB, NUM_LIMBS, MODULUS); |
|
41 } |
|
42 |
|
43 @Override |
|
44 protected void mult(long[] a, long[] b, long[] r) { |
|
45 |
|
46 // Use grade-school multiplication into primitives to avoid the |
|
47 // temporary array allocation. This is equivalent to the following |
|
48 // code: |
|
49 // long[] c = new long[2 * NUM_LIMBS - 1]; |
|
50 // for(int i = 0; i < NUM_LIMBS; i++) { |
|
51 // for(int j - 0; j < NUM_LIMBS; j++) { |
|
52 // c[i + j] += a[i] * b[j] |
|
53 // } |
|
54 // } |
|
55 |
|
56 long c0 = (a[0] * b[0]); |
|
57 long c1 = (a[0] * b[1]) + (a[1] * b[0]); |
|
58 long c2 = (a[0] * b[2]) + (a[1] * b[1]) + (a[2] * b[0]); |
|
59 long c3 = (a[0] * b[3]) + (a[1] * b[2]) + (a[2] * b[1]) + (a[3] * b[0]); |
|
60 long c4 = (a[0] * b[4]) + (a[1] * b[3]) + (a[2] * b[2]) + (a[3] * b[1]) + (a[4] * b[0]); |
|
61 long c5 = (a[0] * b[5]) + (a[1] * b[4]) + (a[2] * b[3]) + (a[3] * b[2]) + (a[4] * b[1]) + (a[5] * b[0]); |
|
62 long c6 = (a[0] * b[6]) + (a[1] * b[5]) + (a[2] * b[4]) + (a[3] * b[3]) + (a[4] * b[2]) + (a[5] * b[1]) + (a[6] * b[0]); |
|
63 long c7 = (a[0] * b[7]) + (a[1] * b[6]) + (a[2] * b[5]) + (a[3] * b[4]) + (a[4] * b[3]) + (a[5] * b[2]) + (a[6] * b[1]) + (a[7] * b[0]); |
|
64 long c8 = (a[0] * b[8]) + (a[1] * b[7]) + (a[2] * b[6]) + (a[3] * b[5]) + (a[4] * b[4]) + (a[5] * b[3]) + (a[6] * b[2]) + (a[7] * b[1]) + (a[8] * b[0]); |
|
65 long c9 = (a[0] * b[9]) + (a[1] * b[8]) + (a[2] * b[7]) + (a[3] * b[6]) + (a[4] * b[5]) + (a[5] * b[4]) + (a[6] * b[3]) + (a[7] * b[2]) + (a[8] * b[1]) + (a[9] * b[0]); |
|
66 long c10 = (a[0] * b[10]) + (a[1] * b[9]) + (a[2] * b[8]) + (a[3] * b[7]) + (a[4] * b[6]) + (a[5] * b[5]) + (a[6] * b[4]) + (a[7] * b[3]) + (a[8] * b[2]) + (a[9] * b[1]) + (a[10] * b[0]); |
|
67 long c11 = (a[0] * b[11]) + (a[1] * b[10]) + (a[2] * b[9]) + (a[3] * b[8]) + (a[4] * b[7]) + (a[5] * b[6]) + (a[6] * b[5]) + (a[7] * b[4]) + (a[8] * b[3]) + (a[9] * b[2]) + (a[10] * b[1]) + (a[11] * b[0]); |
|
68 long c12 = (a[0] * b[12]) + (a[1] * b[11]) + (a[2] * b[10]) + (a[3] * b[9]) + (a[4] * b[8]) + (a[5] * b[7]) + (a[6] * b[6]) + (a[7] * b[5]) + (a[8] * b[4]) + (a[9] * b[3]) + (a[10] * b[2]) + (a[11] * b[1]) + (a[12] * b[0]); |
|
69 long c13 = (a[0] * b[13]) + (a[1] * b[12]) + (a[2] * b[11]) + (a[3] * b[10]) + (a[4] * b[9]) + (a[5] * b[8]) + (a[6] * b[7]) + (a[7] * b[6]) + (a[8] * b[5]) + (a[9] * b[4]) + (a[10] * b[3]) + (a[11] * b[2]) + (a[12] * b[1]) + (a[13] * b[0]); |
|
70 long c14 = (a[0] * b[14]) + (a[1] * b[13]) + (a[2] * b[12]) + (a[3] * b[11]) + (a[4] * b[10]) + (a[5] * b[9]) + (a[6] * b[8]) + (a[7] * b[7]) + (a[8] * b[6]) + (a[9] * b[5]) + (a[10] * b[4]) + (a[11] * b[3]) + (a[12] * b[2]) + (a[13] * b[1]) + (a[14] * b[0]); |
|
71 long c15 = (a[0] * b[15]) + (a[1] * b[14]) + (a[2] * b[13]) + (a[3] * b[12]) + (a[4] * b[11]) + (a[5] * b[10]) + (a[6] * b[9]) + (a[7] * b[8]) + (a[8] * b[7]) + (a[9] * b[6]) + (a[10] * b[5]) + (a[11] * b[4]) + (a[12] * b[3]) + (a[13] * b[2]) + (a[14] * b[1]) + (a[15] * b[0]); |
|
72 long c16 = (a[1] * b[15]) + (a[2] * b[14]) + (a[3] * b[13]) + (a[4] * b[12]) + (a[5] * b[11]) + (a[6] * b[10]) + (a[7] * b[9]) + (a[8] * b[8]) + (a[9] * b[7]) + (a[10] * b[6]) + (a[11] * b[5]) + (a[12] * b[4]) + (a[13] * b[3]) + (a[14] * b[2]) + (a[15] * b[1]); |
|
73 long c17 = (a[2] * b[15]) + (a[3] * b[14]) + (a[4] * b[13]) + (a[5] * b[12]) + (a[6] * b[11]) + (a[7] * b[10]) + (a[8] * b[9]) + (a[9] * b[8]) + (a[10] * b[7]) + (a[11] * b[6]) + (a[12] * b[5]) + (a[13] * b[4]) + (a[14] * b[3]) + (a[15] * b[2]); |
|
74 long c18 = (a[3] * b[15]) + (a[4] * b[14]) + (a[5] * b[13]) + (a[6] * b[12]) + (a[7] * b[11]) + (a[8] * b[10]) + (a[9] * b[9]) + (a[10] * b[8]) + (a[11] * b[7]) + (a[12] * b[6]) + (a[13] * b[5]) + (a[14] * b[4]) + (a[15] * b[3]); |
|
75 long c19 = (a[4] * b[15]) + (a[5] * b[14]) + (a[6] * b[13]) + (a[7] * b[12]) + (a[8] * b[11]) + (a[9] * b[10]) + (a[10] * b[9]) + (a[11] * b[8]) + (a[12] * b[7]) + (a[13] * b[6]) + (a[14] * b[5]) + (a[15] * b[4]); |
|
76 long c20 = (a[5] * b[15]) + (a[6] * b[14]) + (a[7] * b[13]) + (a[8] * b[12]) + (a[9] * b[11]) + (a[10] * b[10]) + (a[11] * b[9]) + (a[12] * b[8]) + (a[13] * b[7]) + (a[14] * b[6]) + (a[15] * b[5]); |
|
77 long c21 = (a[6] * b[15]) + (a[7] * b[14]) + (a[8] * b[13]) + (a[9] * b[12]) + (a[10] * b[11]) + (a[11] * b[10]) + (a[12] * b[9]) + (a[13] * b[8]) + (a[14] * b[7]) + (a[15] * b[6]); |
|
78 long c22 = (a[7] * b[15]) + (a[8] * b[14]) + (a[9] * b[13]) + (a[10] * b[12]) + (a[11] * b[11]) + (a[12] * b[10]) + (a[13] * b[9]) + (a[14] * b[8]) + (a[15] * b[7]); |
|
79 long c23 = (a[8] * b[15]) + (a[9] * b[14]) + (a[10] * b[13]) + (a[11] * b[12]) + (a[12] * b[11]) + (a[13] * b[10]) + (a[14] * b[9]) + (a[15] * b[8]); |
|
80 long c24 = (a[9] * b[15]) + (a[10] * b[14]) + (a[11] * b[13]) + (a[12] * b[12]) + (a[13] * b[11]) + (a[14] * b[10]) + (a[15] * b[9]); |
|
81 long c25 = (a[10] * b[15]) + (a[11] * b[14]) + (a[12] * b[13]) + (a[13] * b[12]) + (a[14] * b[11]) + (a[15] * b[10]); |
|
82 long c26 = (a[11] * b[15]) + (a[12] * b[14]) + (a[13] * b[13]) + (a[14] * b[12]) + (a[15] * b[11]); |
|
83 long c27 = (a[12] * b[15]) + (a[13] * b[14]) + (a[14] * b[13]) + (a[15] * b[12]); |
|
84 long c28 = (a[13] * b[15]) + (a[14] * b[14]) + (a[15] * b[13]); |
|
85 long c29 = (a[14] * b[15]) + (a[15] * b[14]); |
|
86 long c30 = (a[15] * b[15]); |
|
87 |
|
88 carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, |
|
89 c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, |
|
90 c26, c27, c28, c29, c30); |
|
91 } |
|
92 |
|
93 private void carryReduce(long[] r, long c0, long c1, long c2, long c3, |
|
94 long c4, long c5, long c6, long c7, long c8, |
|
95 long c9, long c10, long c11, long c12, long c13, |
|
96 long c14, long c15, long c16, long c17, long c18, |
|
97 long c19, long c20, long c21, long c22, long c23, |
|
98 long c24, long c25, long c26, long c27, long c28, |
|
99 long c29, long c30) { |
|
100 |
|
101 // reduce(8, 7) |
|
102 c8 += c24; |
|
103 c16 += c24; |
|
104 |
|
105 c9 += c25; |
|
106 c17 += c25; |
|
107 |
|
108 c10 += c26; |
|
109 c18 += c26; |
|
110 |
|
111 c11 += c27; |
|
112 c19 += c27; |
|
113 |
|
114 c12 += c28; |
|
115 c20 += c28; |
|
116 |
|
117 c13 += c29; |
|
118 c21 += c29; |
|
119 |
|
120 c14 += c30; |
|
121 c22 += c30; |
|
122 |
|
123 // reduce(4, 4) |
|
124 r[4] = c4 + c20; |
|
125 r[12] = c12 + c20; |
|
126 |
|
127 r[5] = c5 + c21; |
|
128 r[13] = c13 + c21; |
|
129 |
|
130 r[6] = c6 + c22; |
|
131 c14 += c22; |
|
132 |
|
133 r[7] = c7 + c23; |
|
134 c15 += c23; |
|
135 |
|
136 //carry(14, 2) |
|
137 long carry14 = carryValue(c14); |
|
138 r[14] = c14 - (carry14 << BITS_PER_LIMB); |
|
139 c15 += carry14; |
|
140 |
|
141 long carry15 = carryValue(c15); |
|
142 r[15] = c15 - (carry15 << BITS_PER_LIMB); |
|
143 c16 += carry15; |
|
144 |
|
145 // reduce(0, 4) |
|
146 r[0] = c0 + c16; |
|
147 r[8] = c8 + c16; |
|
148 |
|
149 r[1] = c1 + c17; |
|
150 r[9] = c9 + c17; |
|
151 |
|
152 r[2] = c2 + c18; |
|
153 r[10] = c10 + c18; |
|
154 |
|
155 r[3] = c3 + c19; |
|
156 r[11] = c11 + c19; |
|
157 |
|
158 // carry(0, 15) |
|
159 carry(r, 0, 15); |
|
160 } |
|
161 |
|
162 protected void multByInt(long[] a, long b, long[] r) { |
|
163 for (int i = 0; i < a.length; i++) { |
|
164 r[i] = a[i] * b; |
|
165 } |
|
166 |
|
167 // carry(14, 2) |
|
168 long carry14 = carryValue(r[14]); |
|
169 r[14] -= (carry14 << BITS_PER_LIMB); |
|
170 r[15] += carry14; |
|
171 |
|
172 long carry15 = carryValue(r[15]); |
|
173 r[15] -= (carry15 << BITS_PER_LIMB); |
|
174 |
|
175 // reduce(0, 1) |
|
176 r[0] += carry15; |
|
177 r[8] += carry15; |
|
178 |
|
179 // carry(0, 15) |
|
180 carry(r, 0, 15); |
|
181 } |
|
182 |
|
183 @Override |
|
184 protected void square(long[] a, long[] r) { |
|
185 |
|
186 // Use grade-school multiplication with a simple squaring optimization. |
|
187 // Multiply into primitives to avoid the temporary array allocation. |
|
188 // This is equivalent to the following code: |
|
189 // long[] c = new long[2 * NUM_LIMBS - 1]; |
|
190 // for(int i = 0; i < NUM_LIMBS; i++) { |
|
191 // c[2 * i] = a[i] * a[i]; |
|
192 // for(int j = i + 1; j < NUM_LIMBS; j++) { |
|
193 // c[i + j] += 2 * a[i] * a[j] |
|
194 // } |
|
195 // } |
|
196 |
|
197 long c0 = a[0] * a[0]; |
|
198 long c1 = 2 * a[0] * a[1]; |
|
199 long c2 = a[1] * a[1] + 2 * a[0] * a[2]; |
|
200 long c3 = 2 * (a[0] * a[3] + a[1] * a[2]); |
|
201 long c4 = a[2] * a[2] + 2 * (a[0] * a[4] + a[1] * a[3]); |
|
202 long c5 = 2 * (a[0] * a[5] + a[1] * a[4] + a[2] * a[3]); |
|
203 long c6 = a[3] * a[3] + 2 * (a[0] * a[6] + a[1] * a[5] + a[2] * a[4]); |
|
204 long c7 = 2 * (a[0] * a[7] + a[1] * a[6] + a[2] * a[5] + a[3] * a[4]); |
|
205 long c8 = a[4] * a[4] + 2 * (a[0] * a[8] + a[1] * a[7] + a[2] * a[6] + a[3] * a[5]); |
|
206 long c9 = 2 * (a[0] * a[9] + a[1] * a[8] + a[2] * a[7] + a[3] * a[6] + a[4] * a[5]); |
|
207 long c10 = a[5] * a[5] + 2 * (a[0] * a[10] + a[1] * a[9] + a[2] * a[8] + a[3] * a[7] + a[4] * a[6]); |
|
208 long c11 = 2 * (a[0] * a[11] + a[1] * a[10] + a[2] * a[9] + a[3] * a[8] + a[4] * a[7] + a[5] * a[6]); |
|
209 long c12 = a[6] * a[6] + 2 * (a[0] * a[12] + a[1] * a[11] + a[2] * a[10] + a[3] * a[9] + a[4] * a[8] + a[5] * a[7]); |
|
210 long c13 = 2 * (a[0] * a[13] + a[1] * a[12] + a[2] * a[11] + a[3] * a[10] + a[4] * a[9] + a[5] * a[8] + a[6] * a[7]); |
|
211 long c14 = a[7] * a[7] + 2 * (a[0] * a[14] + a[1] * a[13] + a[2] * a[12] + a[3] * a[11] + a[4] * a[10] + a[5] * a[9] + a[6] * a[8]); |
|
212 long c15 = 2 * (a[0] * a[15] + a[1] * a[14] + a[2] * a[13] + a[3] * a[12] + a[4] * a[11] + a[5] * a[10] + a[6] * a[9] + a[7] * a[8]); |
|
213 long c16 = a[8] * a[8] + 2 * (a[1] * a[15] + a[2] * a[14] + a[3] * a[13] + a[4] * a[12] + a[5] * a[11] + a[6] * a[10] + a[7] * a[9]); |
|
214 long c17 = 2 * (a[2] * a[15] + a[3] * a[14] + a[4] * a[13] + a[5] * a[12] + a[6] * a[11] + a[7] * a[10] + a[8] * a[9]); |
|
215 long c18 = a[9] * a[9] + 2 * (a[3] * a[15] + a[4] * a[14] + a[5] * a[13] + a[6] * a[12] + a[7] * a[11] + a[8] * a[10]); |
|
216 long c19 = 2 * (a[4] * a[15] + a[5] * a[14] + a[6] * a[13] + a[7] * a[12] + a[8] * a[11] + a[9] * a[10]); |
|
217 long c20 = a[10] * a[10] + 2 * (a[5] * a[15] + a[6] * a[14] + a[7] * a[13] + a[8] * a[12] + a[9] * a[11]); |
|
218 long c21 = 2 * (a[6] * a[15] + a[7] * a[14] + a[8] * a[13] + a[9] * a[12] + a[10] * a[11]); |
|
219 long c22 = a[11] * a[11] + 2 * (a[7] * a[15] + a[8] * a[14] + a[9] * a[13] + a[10] * a[12]); |
|
220 long c23 = 2 * (a[8] * a[15] + a[9] * a[14] + a[10] * a[13] + a[11] * a[12]); |
|
221 long c24 = a[12] * a[12] + 2 * (a[9] * a[15] + a[10] * a[14] + a[11] * a[13]); |
|
222 long c25 = 2 * (a[10] * a[15] + a[11] * a[14] + a[12] * a[13]); |
|
223 long c26 = a[13] * a[13] + 2 * (a[11] * a[15] + a[12] * a[14]); |
|
224 long c27 = 2 * (a[12] * a[15] + a[13] * a[14]); |
|
225 long c28 = a[14] * a[14] + 2 * a[13] * a[15]; |
|
226 long c29 = 2 * a[14] * a[15]; |
|
227 long c30 = a[15] * a[15]; |
|
228 |
|
229 carryReduce(r, c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, |
|
230 c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, |
|
231 c26, c27, c28, c29, c30); |
|
232 |
|
233 } |
|
234 |
|
235 |
|
236 } |