#include <cmath>
#include <cstdlib>
#include <kernel/mod2.h>
#include "minpoly.h"
Go to the source code of this file.
|
void | vectorMatrixMult (unsigned long *vec, unsigned long **mat, unsigned **nonzeroIndices, unsigned *nonzeroCounts, unsigned long *result, unsigned n, unsigned long p) |
|
unsigned long * | computeMinimalPolynomial (unsigned long **matrix, unsigned n, unsigned long p) |
|
void | rem (unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq) |
|
void | quo (unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq) |
|
void | mult (unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb) |
|
int | gcd (unsigned long *g, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb) |
|
int | lcm (unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb) |
|
unsigned long | modularInverse (long long x, long long p) |
|
◆ computeMinimalPolynomial()
unsigned long* computeMinimalPolynomial |
( |
unsigned long ** |
matrix, |
|
|
unsigned |
n, |
|
|
unsigned long |
p |
|
) |
| |
Definition at line 430 of file minpoly.cc.
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++)
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++)
482 lindepmat.resetMatrix ();
486 bool ld = lindepmat.findLinearDependency (vec, mpvec);
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);
536 newvectormat.insertMatrix (lindepmat);
545 i = newvectormat.findSmallestNonpivot ();
549 i = newvectormat.findLargestNonpivot ();
554 loopsEven = !loopsEven;
557 for (
int i = 0; i < n; i++)
559 delete[] nonzeroIndices[
i];
561 delete[] nonzeroIndices;
562 delete[] nonzeroCounts;
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
void vectorMatrixMult(unsigned long *vec, unsigned long **mat, unsigned **nonzeroIndices, unsigned *nonzeroCounts, unsigned long *result, unsigned n, unsigned long p)
◆ gcd()
int gcd |
( |
unsigned long * |
g, |
|
|
unsigned long * |
a, |
|
|
unsigned long * |
b, |
|
|
unsigned long |
p, |
|
|
int |
dega, |
|
|
int |
degb |
|
) |
| |
Definition at line 668 of file minpoly.cc.
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++)
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
◆ lcm()
int lcm |
( |
unsigned long * |
l, |
|
|
unsigned long * |
a, |
|
|
unsigned long * |
b, |
|
|
unsigned long |
p, |
|
|
int |
dega, |
|
|
int |
degb |
|
) |
| |
Definition at line 711 of file minpoly.cc.
714 unsigned long *
g =
new unsigned long[dega + 1];
716 for(
int i = 0;
i <= dega;
i++)
726 quo (
a, g,
p, dega, degg);
731 if(
l[dega + degb + 1] != 1)
734 for(
int i = 0;
i <= dega + degb;
i++)
int gcd(unsigned long *g, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
void quo(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
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)
◆ modularInverse()
unsigned long modularInverse |
( |
long long |
x, |
|
|
long long |
p |
|
) |
| |
Definition at line 746 of file minpoly.cc.
755 long long q, t1, t2, t3;
775 return (
unsigned long) u1;
◆ mult()
void mult |
( |
unsigned long * |
result, |
|
|
unsigned long * |
a, |
|
|
unsigned long * |
b, |
|
|
unsigned long |
p, |
|
|
int |
dega, |
|
|
int |
degb |
|
) |
| |
Definition at line 649 of file minpoly.cc.
654 for(
int i = 0;
i <= dega;
i++)
656 for(
int j = 0;
j <= degb;
j++)
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
◆ quo()
void quo |
( |
unsigned long * |
a, |
|
|
unsigned long * |
q, |
|
|
unsigned long |
p, |
|
|
int & |
dega, |
|
|
int |
degq |
|
) |
| |
Definition at line 599 of file minpoly.cc.
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;
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++)
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
unsigned long modularInverse(long long x, long long p)
◆ rem()
void rem |
( |
unsigned long * |
a, |
|
|
unsigned long * |
q, |
|
|
unsigned long |
p, |
|
|
int & |
dega, |
|
|
int |
degq |
|
) |
| |
Definition at line 574 of file minpoly.cc.
579 unsigned d = dega - degq;
581 for(
int i = degq;
i >= 0;
i--)
591 while(dega >= 0 &&
a[dega] == 0)
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
unsigned long modularInverse(long long x, long long p)
◆ vectorMatrixMult()
void vectorMatrixMult |
( |
unsigned long * |
vec, |
|
|
unsigned long ** |
mat, |
|
|
unsigned ** |
nonzeroIndices, |
|
|
unsigned * |
nonzeroCounts, |
|
|
unsigned long * |
result, |
|
|
unsigned |
n, |
|
|
unsigned long |
p |
|
) |
| |
Definition at line 395 of file minpoly.cc.
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);
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)