blob: f8764c68092041272be7ee79a40aeeb56bf0f7ff (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
package org.spongycastle.pqc.math.ntru.polynomial;
import org.spongycastle.util.Arrays;
/**
* A polynomial class that combines five coefficients into one <code>long</code> value for
* faster multiplication by a ternary polynomial.<br>
* Coefficients can be between 0 and 2047 and are stored in bits 0..11, 12..23, ..., 48..59 of a <code>long</code> number.
*/
public class LongPolynomial5
{
private long[] coeffs; // groups of 5 coefficients
private int numCoeffs;
/**
* Constructs a <code>LongPolynomial5</code> from a <code>IntegerPolynomial</code>. The two polynomials are independent of each other.
*
* @param p the original polynomial. Coefficients must be between 0 and 2047.
*/
public LongPolynomial5(IntegerPolynomial p)
{
numCoeffs = p.coeffs.length;
coeffs = new long[(numCoeffs + 4) / 5];
int cIdx = 0;
int shift = 0;
for (int i = 0; i < numCoeffs; i++)
{
coeffs[cIdx] |= ((long)p.coeffs[i]) << shift;
shift += 12;
if (shift >= 60)
{
shift = 0;
cIdx++;
}
}
}
private LongPolynomial5(long[] coeffs, int numCoeffs)
{
this.coeffs = coeffs;
this.numCoeffs = numCoeffs;
}
/**
* Multiplies the polynomial with a <code>TernaryPolynomial</code>, taking the indices mod N and the values mod 2048.
*/
public LongPolynomial5 mult(TernaryPolynomial poly2)
{
long[][] prod = new long[5][coeffs.length + (poly2.size() + 4) / 5 - 1]; // intermediate results, the subarrays are shifted by 0,...,4 coefficients
// multiply ones
int[] ones = poly2.getOnes();
for (int idx = 0; idx != ones.length; idx++)
{
int pIdx = ones[idx];
int cIdx = pIdx / 5;
int m = pIdx - cIdx * 5; // m = pIdx % 5
for (int i = 0; i < coeffs.length; i++)
{
prod[m][cIdx] = (prod[m][cIdx] + coeffs[i]) & 0x7FF7FF7FF7FF7FFL;
cIdx++;
}
}
// multiply negative ones
int[] negOnes = poly2.getNegOnes();
for (int idx = 0; idx != negOnes.length; idx++)
{
int pIdx = negOnes[idx];
int cIdx = pIdx / 5;
int m = pIdx - cIdx * 5; // m = pIdx % 5
for (int i = 0; i < coeffs.length; i++)
{
prod[m][cIdx] = (0x800800800800800L + prod[m][cIdx] - coeffs[i]) & 0x7FF7FF7FF7FF7FFL;
cIdx++;
}
}
// combine shifted coefficients (5 arrays) into a single array of length prod[*].length+1
long[] cCoeffs = Arrays.copyOf(prod[0], prod[0].length + 1);
for (int m = 1; m <= 4; m++)
{
int shift = m * 12;
int shift60 = 60 - shift;
long mask = (1L << shift60) - 1;
int pLen = prod[m].length;
for (int i = 0; i < pLen; i++)
{
long upper, lower;
upper = prod[m][i] >> shift60;
lower = prod[m][i] & mask;
cCoeffs[i] = (cCoeffs[i] + (lower << shift)) & 0x7FF7FF7FF7FF7FFL;
int nextIdx = i + 1;
cCoeffs[nextIdx] = (cCoeffs[nextIdx] + upper) & 0x7FF7FF7FF7FF7FFL;
}
}
// reduce indices of cCoeffs modulo numCoeffs
int shift = 12 * (numCoeffs % 5);
for (int cIdx = coeffs.length - 1; cIdx < cCoeffs.length; cIdx++)
{
long iCoeff; // coefficient to shift into the [0..numCoeffs-1] range
int newIdx;
if (cIdx == coeffs.length - 1)
{
iCoeff = numCoeffs == 5 ? 0 : cCoeffs[cIdx] >> shift;
newIdx = 0;
}
else
{
iCoeff = cCoeffs[cIdx];
newIdx = cIdx * 5 - numCoeffs;
}
int base = newIdx / 5;
int m = newIdx - base * 5; // m = newIdx % 5
long lower = iCoeff << (12 * m);
long upper = iCoeff >> (12 * (5 - m));
cCoeffs[base] = (cCoeffs[base] + lower) & 0x7FF7FF7FF7FF7FFL;
int base1 = base + 1;
if (base1 < coeffs.length)
{
cCoeffs[base1] = (cCoeffs[base1] + upper) & 0x7FF7FF7FF7FF7FFL;
}
}
return new LongPolynomial5(cCoeffs, numCoeffs);
}
public IntegerPolynomial toIntegerPolynomial()
{
int[] intCoeffs = new int[numCoeffs];
int cIdx = 0;
int shift = 0;
for (int i = 0; i < numCoeffs; i++)
{
intCoeffs[i] = (int)((coeffs[cIdx] >> shift) & 2047);
shift += 12;
if (shift >= 60)
{
shift = 0;
cIdx++;
}
}
return new IntegerPolynomial(intCoeffs);
}
}
|
