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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
package org.bouncycastle.pqc.math.linearalgebra;
/**
* This class represents polynomial rings <tt>GF(2^m)[X]/p(X)</tt> for
* <tt>m<32</tt>. If <tt>p(X)</tt> is irreducible, the polynomial ring
* is in fact an extension field of <tt>GF(2^m)</tt>.
*/
public class PolynomialRingGF2m
{
/**
* the finite field this polynomial ring is defined over
*/
private GF2mField field;
/**
* the reduction polynomial
*/
private PolynomialGF2mSmallM p;
/**
* the squaring matrix for this polynomial ring (given as the array of its
* row vectors)
*/
protected PolynomialGF2mSmallM[] sqMatrix;
/**
* the matrix for computing square roots in this polynomial ring (given as
* the array of its row vectors). This matrix is computed as the inverse of
* the squaring matrix.
*/
protected PolynomialGF2mSmallM[] sqRootMatrix;
/**
* Constructor.
*
* @param field the finite field
* @param p the reduction polynomial
*/
public PolynomialRingGF2m(GF2mField field, PolynomialGF2mSmallM p)
{
this.field = field;
this.p = p;
computeSquaringMatrix();
computeSquareRootMatrix();
}
/**
* @return the squaring matrix for this polynomial ring
*/
public PolynomialGF2mSmallM[] getSquaringMatrix()
{
return sqMatrix;
}
/**
* @return the matrix for computing square roots for this polynomial ring
*/
public PolynomialGF2mSmallM[] getSquareRootMatrix()
{
return sqRootMatrix;
}
/**
* Compute the squaring matrix for this polynomial ring, using the base
* field and the reduction polynomial.
*/
private void computeSquaringMatrix()
{
int numColumns = p.getDegree();
sqMatrix = new PolynomialGF2mSmallM[numColumns];
for (int i = 0; i < numColumns >> 1; i++)
{
int[] monomCoeffs = new int[(i << 1) + 1];
monomCoeffs[i << 1] = 1;
sqMatrix[i] = new PolynomialGF2mSmallM(field, monomCoeffs);
}
for (int i = numColumns >> 1; i < numColumns; i++)
{
int[] monomCoeffs = new int[(i << 1) + 1];
monomCoeffs[i << 1] = 1;
PolynomialGF2mSmallM monomial = new PolynomialGF2mSmallM(field,
monomCoeffs);
sqMatrix[i] = monomial.mod(p);
}
}
/**
* Compute the matrix for computing square roots in this polynomial ring by
* inverting the squaring matrix.
*/
private void computeSquareRootMatrix()
{
int numColumns = p.getDegree();
// clone squaring matrix
PolynomialGF2mSmallM[] tmpMatrix = new PolynomialGF2mSmallM[numColumns];
for (int i = numColumns - 1; i >= 0; i--)
{
tmpMatrix[i] = new PolynomialGF2mSmallM(sqMatrix[i]);
}
// initialize square root matrix as unit matrix
sqRootMatrix = new PolynomialGF2mSmallM[numColumns];
for (int i = numColumns - 1; i >= 0; i--)
{
sqRootMatrix[i] = new PolynomialGF2mSmallM(field, i);
}
// simultaneously compute Gaussian reduction of squaring matrix and unit
// matrix
for (int i = 0; i < numColumns; i++)
{
// if diagonal element is zero
if (tmpMatrix[i].getCoefficient(i) == 0)
{
boolean foundNonZero = false;
// find a non-zero element in the same row
for (int j = i + 1; j < numColumns; j++)
{
if (tmpMatrix[j].getCoefficient(i) != 0)
{
// found it, swap columns ...
foundNonZero = true;
swapColumns(tmpMatrix, i, j);
swapColumns(sqRootMatrix, i, j);
// ... and quit searching
j = numColumns;
continue;
}
}
// if no non-zero element was found
if (!foundNonZero)
{
// the matrix is not invertible
throw new ArithmeticException(
"Squaring matrix is not invertible.");
}
}
// normalize i-th column
int coef = tmpMatrix[i].getCoefficient(i);
int invCoef = field.inverse(coef);
tmpMatrix[i].multThisWithElement(invCoef);
sqRootMatrix[i].multThisWithElement(invCoef);
// normalize all other columns
for (int j = 0; j < numColumns; j++)
{
if (j != i)
{
coef = tmpMatrix[j].getCoefficient(i);
if (coef != 0)
{
PolynomialGF2mSmallM tmpSqColumn = tmpMatrix[i]
.multWithElement(coef);
PolynomialGF2mSmallM tmpInvColumn = sqRootMatrix[i]
.multWithElement(coef);
tmpMatrix[j].addToThis(tmpSqColumn);
sqRootMatrix[j].addToThis(tmpInvColumn);
}
}
}
}
}
private static void swapColumns(PolynomialGF2mSmallM[] matrix, int first,
int second)
{
PolynomialGF2mSmallM tmp = matrix[first];
matrix[first] = matrix[second];
matrix[second] = tmp;
}
}
|
