Go to the source code of this file.
|
unsigned long * | computeMinimalPolynomial (unsigned long **matrix, unsigned n, unsigned long p) |
|
unsigned long | modularInverse (long long x, long long p) |
|
void | vectorMatrixMult (unsigned long *vec, unsigned long **mat, unsigned **nonzeroIndices, unsigned *nonzeroCounts, unsigned long *result, 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) |
|
static unsigned long | multMod (unsigned long a, unsigned long b, unsigned long p) |
|
◆ ULONG64
#define ULONG64 (unsigned long) |
◆ computeMinimalPolynomial()
unsigned long* computeMinimalPolynomial |
( |
unsigned long ** |
matrix, |
|
|
unsigned |
n, |
|
|
unsigned long |
p |
|
) |
| |
Definition at line 428 of file minpoly.cc.
434 unsigned long *
result =
new unsigned long[n + 1];
435 unsigned long *mpvec =
new unsigned long[n + 1];
436 unsigned long *tmp =
new unsigned long[n + 1];
439 for(
int i = 0;
i <= n;
i++)
450 unsigned* nonzeroCounts =
new unsigned[n];
451 unsigned** nonzeroIndices =
new unsigned*[n];
452 for (
int i = 0;
i < n;
i++)
454 nonzeroIndices[
i] =
new unsigned[n];
455 nonzeroCounts[
i] = 0;
456 for (
int j = 0;
j < n;
j++)
460 nonzeroIndices[
i][nonzeroCounts[
i]] =
j;
468 unsigned long *
vec =
new unsigned long[n];
469 unsigned long *vecnew =
new unsigned long[n];
471 unsigned loopsEven =
true;
474 for(
int j = 0;
j < n;
j++)
480 lindepmat.resetMatrix ();
484 bool ld = lindepmat.findLinearDependency (
vec, mpvec);
498 unsigned degmpvec = n;
499 while(mpvec[degmpvec] == 0)
518 for(
int j = 0;
j <= n;
j++)
522 degresult =
lcm (tmp,
result, mpvec,
p, degresult, degmpvec);
534 newvectormat.insertMatrix (lindepmat);
543 i = newvectormat.findSmallestNonpivot ();
547 i = newvectormat.findLargestNonpivot ();
552 loopsEven = !loopsEven;
555 for (
int i = 0;
i < n;
i++)
557 delete[] nonzeroIndices[
i];
559 delete[] nonzeroIndices;
560 delete[] nonzeroCounts;
void vectorMatrixMult(unsigned long *vec, unsigned long **mat, unsigned **nonzeroIndices, unsigned *nonzeroCounts, unsigned long *result, unsigned n, unsigned long p)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
◆ gcd()
int gcd |
( |
unsigned long * |
g, |
|
|
unsigned long * |
a, |
|
|
unsigned long * |
b, |
|
|
unsigned long |
p, |
|
|
int |
dega, |
|
|
int |
degb |
|
) |
| |
Definition at line 666 of file minpoly.cc.
669 unsigned long *
tmp1 =
new unsigned long[dega + 1];
670 unsigned long *
tmp2 =
new unsigned long[degb + 1];
671 for(
int i = 0;
i <= dega;
i++)
675 for(
int i = 0;
i <= degb;
i++)
682 unsigned long *swappol;
697 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 709 of file minpoly.cc.
712 unsigned long *
g =
new unsigned long[dega + 1];
714 for(
int i = 0;
i <= dega;
i++)
729 if(
l[dega + degb + 1] != 1)
732 for(
int i = 0;
i <= dega + degb;
i++)
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
void quo(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
unsigned long modularInverse(long long x, long long p)
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)
◆ modularInverse()
unsigned long modularInverse |
( |
long long |
x, |
|
|
long long |
p |
|
) |
| |
Definition at line 744 of file minpoly.cc.
753 long long q, t1, t2, t3;
773 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 647 of file minpoly.cc.
652 for(
int i = 0;
i <= dega;
i++)
654 for(
int j = 0;
j <= degb;
j++)
◆ multMod()
static unsigned long multMod |
( |
unsigned long |
a, |
|
|
unsigned long |
b, |
|
|
unsigned long |
p |
|
) |
| |
|
inlinestatic |
Definition at line 202 of file minpoly.h.
205 #define ULONG64 (unsigned long long)
207 #define ULONG64 (unsigned long)
◆ quo()
void quo |
( |
unsigned long * |
a, |
|
|
unsigned long * |
q, |
|
|
unsigned long |
p, |
|
|
int & |
dega, |
|
|
int |
degq |
|
) |
| |
Definition at line 597 of file minpoly.cc.
600 unsigned degres = dega - degq;
601 unsigned long *
result =
new unsigned long[degres + 1];
604 for (
int i = 0;
i <= degres;
i++)
611 unsigned d = dega - degq;
614 for(
int i = degq;
i >= 0;
i--)
624 while(dega >= 0 && a[dega] == 0)
631 for(
int i = 0;
i <= degres;
i++)
636 for(
int i = degres + 1;
i <= degq + degres;
i++)
◆ rem()
void rem |
( |
unsigned long * |
a, |
|
|
unsigned long * |
q, |
|
|
unsigned long |
p, |
|
|
int & |
dega, |
|
|
int |
degq |
|
) |
| |
Definition at line 572 of file minpoly.cc.
577 unsigned d = dega - degq;
579 for(
int i = degq;
i >= 0;
i--)
589 while(dega >= 0 && a[dega] == 0)
◆ vectorMatrixMult()
void vectorMatrixMult |
( |
unsigned long * |
vec, |
|
|
unsigned long ** |
mat, |
|
|
unsigned ** |
nonzeroIndices, |
|
|
unsigned * |
nonzeroCounts, |
|
|
unsigned long * |
result, |
|
|
unsigned |
n, |
|
|
unsigned long |
p |
|
) |
| |
Definition at line 393 of file minpoly.cc.
399 for(
int i = 0;
i < n;
i++)
402 for(
int j = 0;
j < nonzeroCounts[
i];
j++)