26 matrix =
new unsigned long *[
n];
27 for(
int i = 0;
i <
n;
i++)
29 matrix[
i] =
new unsigned long[2 * n + 1];
32 tmprow =
new unsigned long[2 * n + 1];
41 for(
int i = 0;
i <
n;
i++)
55 for(
int i = 0;
i <
n;
i++)
72 for(
int j = piv;
j <
n + rows + 1;
j++)
94 for(
int j = i + 1;
j < 2 *
n + 1;
j++)
102 for(
int i = 0;
i <
n;
i++)
117 for(
int i = 0;
i <=
n;
i++)
128 for(
int i = 0;
i < 2 * n + 1;
i++)
141 std::ostream &
operator<< (std::ostream & out,
144 int width = ((int) log10 (mat.
p)) + 1;
146 out <<
"Pivots: " << std::endl;
147 for(
int j = 0;
j < mat.
n;
j++)
149 out << std::setw (width) << mat.
pivots[
j] <<
" ";
152 out <<
"matrix:" << std::endl;
153 for(
int i = 0;
i < mat.
rows;
i++)
155 for(
int j = 0;
j < mat.
n;
j++)
157 out << std::setw (width) << mat.
matrix[
i][
j] <<
" ";
160 for(
int j = mat.
n;
j <= 2 * mat.
n;
j++)
162 out << std::setw (width) << mat.
matrix[
i][
j] <<
" ";
166 out <<
"tmprow: " << std::endl;
167 for(
int j = 0;
j < mat.
n;
j++)
169 out << std::setw (width) << mat.
tmprow[
j] <<
" ";
172 for(
int j = mat.
n;
j <= 2 * mat.
n;
j++)
174 out << std::setw (width) << mat.
tmprow[
j] <<
" ";
188 matrix =
new unsigned long *[
n];
189 for(
int i = 0;
i <
n;
i++)
198 for (
int i = 0;
i <
n;
i++)
211 for(
int i = 0;
i <
n;
i++)
220 for(
int i = 0;
i <
n;
i++)
232 for(
int j = i + 1;
j <
n;
j++)
243 unsigned x = row[piv];
252 int smallestNonPivIndex = 0;
253 while (
nonPivots[smallestNonPivIndex] < piv)
255 smallestNonPivIndex++;
258 for (
int j = smallestNonPivIndex;
j <
n-
rows;
j++)
282 for(
int i = 0;
i <
n;
i++)
295 for (
int j = piv;
j <
n;
j++)
299 unsigned long tmp =
multMod(row[
j], x,
p);
314 for (
int i = 0;
i < n-
rows;
i++)
319 for (
int j =
i;
j < n-rows-1;
j++)
335 for(
int i = 0;
i < mat.
rows;
i++)
348 for(
int i = 0;
i <
n;
i++)
350 bool isPivot =
false;
374 for(
int i =
n-1;
i >= 0;
i--)
376 bool isPivot =
false;
396 unsigned **nonzeroIndices,
unsigned *nonzeroCounts,
397 unsigned long *
result,
unsigned n,
unsigned long p)
401 for(
int i = 0;
i <
n;
i++)
404 for(
int j = 0;
j < nonzeroCounts[
i];
j++)
406 tmp =
multMod (vec[nonzeroIndices[
i][
j]], mat[nonzeroIndices[
i][j]][
i], p);
418 void printVec (
unsigned long *
vec,
int n)
420 for(
int i = 0;
i <
n;
i++)
422 std::cout << vec[
i] <<
", ";
425 std::cout << std::endl;
436 unsigned long *
result =
new unsigned long[n + 1];
437 unsigned long *mpvec =
new unsigned long[n + 1];
438 unsigned long *tmp =
new unsigned long[n + 1];
441 for(
int i = 0;
i <=
n;
i++)
452 unsigned* nonzeroCounts =
new unsigned[
n];
453 unsigned** nonzeroIndices =
new unsigned*[
n];
454 for (
int i = 0;
i <
n;
i++)
456 nonzeroIndices[
i] =
new unsigned[
n];
457 nonzeroCounts[
i] = 0;
458 for (
int j = 0;
j <
n;
j++)
460 if (matrix[
j][
i] != 0)
462 nonzeroIndices[
i][nonzeroCounts[
i]] =
j;
470 unsigned long *vec =
new unsigned long[
n];
471 unsigned long *vecnew =
new unsigned long[
n];
473 unsigned loopsEven =
true;
476 for(
int j = 0;
j <
n;
j++)
493 vectorMatrixMult (vec, matrix, nonzeroIndices, nonzeroCounts, vecnew, n, p);
500 unsigned degmpvec =
n;
501 while(mpvec[degmpvec] == 0)
520 for(
int j = 0;
j <=
n;
j++)
524 degresult =
lcm (tmp, result, mpvec, p, degresult, degmpvec);
554 loopsEven = !loopsEven;
557 for (
int i = 0; i <
n; i++)
559 delete[] nonzeroIndices[
i];
561 delete[] nonzeroIndices;
562 delete[] nonzeroCounts;
574 void rem (
unsigned long *
a,
unsigned long *q,
unsigned long p,
int °a,
579 unsigned d = dega - degq;
581 for(
int i = degq;
i >= 0;
i--)
583 long tmp = p -
multMod (factor, q[
i], p);
591 while(dega >= 0 && a[dega] == 0)
599 void quo (
unsigned long *
a,
unsigned long *q,
unsigned long p,
int °a,
602 unsigned degres = dega - degq;
603 unsigned long *
result =
new unsigned long[degres + 1];
606 for (
int i = 0;
i <= degres;
i++)
613 unsigned d = dega - degq;
615 result[d] =
multMod (a[dega], inv, p);
616 for(
int i = degq;
i >= 0;
i--)
618 unsigned long tmp = p -
multMod (result[d], q[
i], p);
626 while(dega >= 0 && a[dega] == 0)
633 for(
int i = 0;
i <= degres;
i++)
638 for(
int i = degres + 1;
i <= degq + degres;
i++)
650 unsigned long p,
int dega,
int degb)
654 for(
int i = 0;
i <= dega;
i++)
656 for(
int j = 0;
j <= degb;
j++)
659 if (result[i + j] >= p)
668 int gcd (
unsigned long *
g,
unsigned long *
a,
unsigned long *
b,
669 unsigned long p,
int dega,
int degb)
671 unsigned long *
tmp1 =
new unsigned long[dega + 1];
672 unsigned long *
tmp2 =
new unsigned long[degb + 1];
673 for(
int i = 0;
i <= dega;
i++)
677 for(
int i = 0;
i <= degb;
i++)
684 unsigned long *swappol;
689 rem (tmp1, tmp2, p, degtmp1, degtmp2);
699 for(
int i = 0;
i <= degtmp1;
i++)
711 int lcm (
unsigned long *
l,
unsigned long *
a,
unsigned long *
b,
712 unsigned long p,
int dega,
int degb)
714 unsigned long *
g =
new unsigned long[dega + 1];
716 for(
int i = 0;
i <= dega;
i++)
721 int degg =
gcd (g, a, b, p, dega, degb);
726 quo (a, g, p, dega, degg);
728 mult (l, a, b, p, dega, degb);
731 if(l[dega + degb + 1] != 1)
734 for(
int i = 0;
i <= dega + degb;
i++)
755 long long q, t1, t2, t3;
775 return (
unsigned long) u1;
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
LinearDependencyMatrix(unsigned n, unsigned long p)
int gcd(unsigned long *g, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
const CanonicalForm CFMap CFMap int &both_non_zero int n
void normalizeTmp(unsigned i)
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
unsigned long * computeMinimalPolynomial(unsigned long **matrix, unsigned n, unsigned long p)
bool findLinearDependency(unsigned long *newRow, unsigned long *dep)
void quo(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
~LinearDependencyMatrix()
void normalizeRow(unsigned long *row, unsigned i)
void insertMatrix(LinearDependencyMatrix &mat)
void vectorMatrixMult(unsigned long *vec, unsigned long **mat, unsigned **nonzeroIndices, unsigned *nonzeroCounts, unsigned long *result, unsigned n, unsigned long p)
NewVectorMatrix(unsigned n, unsigned long p)
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
unsigned long modularInverse(long long x, long long p)
void insertRow(unsigned long *row)
int firstNonzeroEntry(unsigned long *row)
int findLargestNonpivot()
int findSmallestNonpivot()
ostream & operator<<(ostream &s, const spectrum &spec)
int firstNonzeroEntry(unsigned long *row)