spielwiese
|
Last change
on this file since 2cfffe was
2cfffe,
checked in by Hans Schönemann <hannes@…>, 21 years ago
|
|
This commit was generated by cvs2svn to compensate for changes in r6316,
which included commits to RCS files with non-trunk default branches.
git-svn-id: file:///usr/local/Singular/svn/trunk@6317 2c84dea3-7e68-4137-9b89-c4e89433aadc
|
-
Property mode set to
100644
|
|
File size:
1.2 KB
|
| Line | |
|---|
| 1 | #include <NTL/ZZX.h> |
|---|
| 2 | |
|---|
| 3 | #include <NTL/new.h> |
|---|
| 4 | |
|---|
| 5 | NTL_START_IMPL |
|---|
| 6 | |
|---|
| 7 | |
|---|
| 8 | void CharPolyMod(ZZX& gg, const ZZX& a, const ZZX& f, long deterministic) |
|---|
| 9 | { |
|---|
| 10 | if (!IsOne(LeadCoeff(f)) || deg(f) < 1 || deg(a) >= deg(f)) |
|---|
| 11 | Error("CharPolyMod: bad args"); |
|---|
| 12 | |
|---|
| 13 | |
|---|
| 14 | if (IsZero(a)) { |
|---|
| 15 | clear(gg); |
|---|
| 16 | SetCoeff(gg, deg(f)); |
|---|
| 17 | return; |
|---|
| 18 | } |
|---|
| 19 | |
|---|
| 20 | long bound = 2 + CharPolyBound(a, f); |
|---|
| 21 | |
|---|
| 22 | long gp_cnt = 0; |
|---|
| 23 | |
|---|
| 24 | zz_pBak bak; |
|---|
| 25 | bak.save(); |
|---|
| 26 | |
|---|
| 27 | ZZ_pBak bak1; |
|---|
| 28 | bak1.save(); |
|---|
| 29 | |
|---|
| 30 | ZZX g; |
|---|
| 31 | ZZ prod; |
|---|
| 32 | |
|---|
| 33 | clear(g); |
|---|
| 34 | set(prod); |
|---|
| 35 | |
|---|
| 36 | long i; |
|---|
| 37 | |
|---|
| 38 | long instable = 1; |
|---|
| 39 | |
|---|
| 40 | for (i = 0; ; i++) { |
|---|
| 41 | if (NumBits(prod) > bound) |
|---|
| 42 | break; |
|---|
| 43 | |
|---|
| 44 | if (!deterministic && |
|---|
| 45 | !instable && bound > 1000 && NumBits(prod) < 0.25*bound) { |
|---|
| 46 | long plen = 90 + NumBits(max(bound, MaxBits(g))); |
|---|
| 47 | |
|---|
| 48 | ZZ P; |
|---|
| 49 | |
|---|
| 50 | GenPrime(P, plen, 90 + 2*NumBits(gp_cnt++)); |
|---|
| 51 | |
|---|
| 52 | ZZ_p::init(P); |
|---|
| 53 | ZZ_pX G, A, F; |
|---|
| 54 | conv(A, a); |
|---|
| 55 | conv(F, f); |
|---|
| 56 | CharPolyMod(G, A, F); |
|---|
| 57 | |
|---|
| 58 | if (CRT(g, prod, G)) |
|---|
| 59 | instable = 1; |
|---|
| 60 | else |
|---|
| 61 | break; |
|---|
| 62 | } |
|---|
| 63 | |
|---|
| 64 | zz_p::FFTInit(i); |
|---|
| 65 | |
|---|
| 66 | zz_pX G, A, F; |
|---|
| 67 | conv(A, a); |
|---|
| 68 | conv(F, f); |
|---|
| 69 | CharPolyMod(G, A, F); |
|---|
| 70 | instable = CRT(g, prod, G); |
|---|
| 71 | } |
|---|
| 72 | |
|---|
| 73 | gg = g; |
|---|
| 74 | |
|---|
| 75 | bak.restore(); |
|---|
| 76 | bak1.restore(); |
|---|
| 77 | } |
|---|
| 78 | |
|---|
| 79 | NTL_END_IMPL |
|---|
Note: See
TracBrowser
for help on using the repository browser.
