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
|
#include <NTL/mat_poly_ZZ_p.h>
#include <NTL/new.h>
NTL_START_IMPL
static
void HessCharPoly(ZZ_pX& g, const ZZ_pX& a, const ZZ_pX& f)
{
long n = deg(f);
if (n <= 0 || deg(a) >= n)
Error("HessCharPoly: bad args");
mat_ZZ_p M;
M.SetDims(n, n);
long i, j;
ZZ_pX t;
t = a;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
M[i][j] = coeff(t, j);
if (i < n-1)
MulByXMod(t, t, f);
}
CharPoly(g, M);
}
void CharPolyMod(ZZ_pX& g, const ZZ_pX& a, const ZZ_pX& ff)
{
ZZ_pX f = ff;
MakeMonic(f);
long n = deg(f);
if (n <= 0 || deg(a) >= n)
Error("CharPoly: bad args");
if (IsZero(a)) {
clear(g);
SetCoeff(g, n);
return;
}
if (n > 25) {
ZZ_pX h;
MinPolyMod(h, a, f);
if (deg(h) == n) {
g = h;
return;
}
}
if (ZZ_p::modulus() < n+1) {
HessCharPoly(g, a, f);
return;
}
vec_ZZ_p u(INIT_SIZE, n+1), v(INIT_SIZE, n+1);
ZZ_pX h, h1;
negate(h, a);
long i;
for (i = 0; i <= n; i++) {
u[i] = i;
add(h1, h, u[i]);
resultant(v[i], f, h1);
}
interpolate(g, u, v);
}
NTL_END_IMPL
|
