[35aab3] | 1 | /**************************************** |
---|
| 2 | * Computer Algebra System SINGULAR * |
---|
| 3 | ****************************************/ |
---|
| 4 | /* |
---|
| 5 | * ABSTRACT: finite fields with a none-prime number of elements (via tables) |
---|
| 6 | */ |
---|
| 7 | |
---|
[16f511] | 8 | #ifdef HAVE_CONFIG_H |
---|
[ba5e9e] | 9 | #include "libpolysconfig.h" |
---|
[16f511] | 10 | #endif /* HAVE_CONFIG_H */ |
---|
[7fee876] | 11 | |
---|
| 12 | #include <omalloc/omalloc.h> |
---|
| 13 | |
---|
[18cb65] | 14 | #include <misc/auxiliary.h> |
---|
| 15 | #include <misc/mylimits.h> |
---|
[7fee876] | 16 | |
---|
[18cb65] | 17 | #include <reporter/reporter.h> |
---|
[7fee876] | 18 | |
---|
| 19 | #include <coeffs/coeffs.h> |
---|
[2d805a] | 20 | #include <coeffs/numbers.h> |
---|
| 21 | #include <coeffs/ffields.h> |
---|
[d4fa60] | 22 | #include <coeffs/longrat.h> |
---|
[7fee876] | 23 | |
---|
| 24 | #include <string.h> |
---|
[a5cd69] | 25 | #include <math.h> |
---|
[bdda8c2] | 26 | #include <errno.h> |
---|
[d0a51ee] | 27 | |
---|
[7fee876] | 28 | BOOLEAN nfGreaterZero (number k, const coeffs r); |
---|
| 29 | number nfMult (number a, number b, const coeffs r); |
---|
| 30 | number nfInit (long i, const coeffs r); |
---|
| 31 | number nfParameter (int i, const coeffs r); |
---|
| 32 | int nfInt (number &n, const coeffs r); |
---|
| 33 | number nfAdd (number a, number b, const coeffs r); |
---|
| 34 | number nfSub (number a, number b, const coeffs r); |
---|
| 35 | void nfPower (number a, int i, number * result, const coeffs r); |
---|
| 36 | BOOLEAN nfIsZero (number a, const coeffs r); |
---|
| 37 | BOOLEAN nfIsOne (number a, const coeffs r); |
---|
| 38 | BOOLEAN nfIsMOne (number a, const coeffs r); |
---|
| 39 | number nfDiv (number a, number b, const coeffs r); |
---|
| 40 | number nfNeg (number c, const coeffs r); |
---|
| 41 | number nfInvers (number c, const coeffs r); |
---|
| 42 | BOOLEAN nfGreater (number a, number b, const coeffs r); |
---|
| 43 | BOOLEAN nfEqual (number a, number b, const coeffs r); |
---|
| 44 | const char * nfRead (const char *s, number *a, const coeffs r); |
---|
| 45 | #ifdef LDEBUG |
---|
| 46 | BOOLEAN nfDBTest (number a, const char *f, const int l, const coeffs r); |
---|
| 47 | #endif |
---|
| 48 | //void nfSetChar (const coeffs r); |
---|
| 49 | |
---|
| 50 | nMapFunc nfSetMap (const coeffs src, const coeffs dst); |
---|
| 51 | char * nfName (number n, const coeffs r); |
---|
| 52 | void nfReadTable (const int c, const coeffs r); |
---|
| 53 | |
---|
| 54 | void nfCoeffWrite(const coeffs r, BOOLEAN details); |
---|
| 55 | void nfShowMipo(const coeffs r); |
---|
| 56 | |
---|
| 57 | |
---|
| 58 | |
---|
| 59 | /// Our Type! |
---|
| 60 | static const n_coeffType ID = n_GF; |
---|
[5e3046] | 61 | |
---|
| 62 | //unsigned short *nfPlus1Table=NULL; /* the table i=log(z^i) -> log(z^i+1) */ |
---|
| 63 | |
---|
[1b078e] | 64 | const double sixteenlog2= 11.09035489; |
---|
[35aab3] | 65 | /* the q's from the table 'fftable' */ |
---|
[6f8225] | 66 | unsigned short fftable[]={ |
---|
| 67 | 4, 8, 16, 32, 64, 128, 256, 512,1024,2048,4096,8192,16384, 32768, |
---|
| 68 | /*2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10 2^11 2^12 2^13 2^14 2^15*/ |
---|
| 69 | 9, 27, 81,243,729,2187, 6561,19683,59049, |
---|
| 70 | /*3^2 3^3 3^4 3^5 3^6 3^7 3^8 3^9 3^10*/ |
---|
[35aab3] | 71 | 25,125,625,3125,15625, |
---|
| 72 | /*5^2 5^3 5^4 5^5 5^6*/ |
---|
| 73 | 49,343,2401,16807, |
---|
| 74 | /*7^2 7^3 7^4 7^5*/ |
---|
| 75 | 121,1331, 14641, |
---|
| 76 | /*11^2 11^3 11^4*/ |
---|
| 77 | 169, 2197, 28561, |
---|
| 78 | /*13^2 13^3 13^4*/ |
---|
| 79 | 289, 4913, |
---|
| 80 | /*17^2 17^3*/ |
---|
| 81 | 361, 6859, |
---|
| 82 | /*19^2 19^3*/ |
---|
| 83 | 529, 12167, |
---|
| 84 | /*23^2 23^3*/ |
---|
| 85 | 841, 24389, |
---|
| 86 | /*29^2 29^3*/ |
---|
| 87 | 961, 29791, |
---|
| 88 | /*31^2 31^3*/ |
---|
[6f8225] | 89 | 1369, 50653, |
---|
| 90 | /*37^2 37^3*/ |
---|
| 91 | 1681, /*41^2*/ |
---|
| 92 | 1849, /*43^2*/ |
---|
| 93 | 2209, /*47^2*/ |
---|
| 94 | 2809, /*53^2*/ |
---|
| 95 | 3481, /*59^2*/ |
---|
| 96 | 3721, /*61^2*/ |
---|
| 97 | 4489, /*67^2*/ |
---|
| 98 | 5041, /*71^2*/ |
---|
| 99 | 5329, /*73^2*/ |
---|
| 100 | 6241, /*79^2*/ |
---|
| 101 | 6889, /*83^2*/ |
---|
| 102 | 7921, /*89^2*/ |
---|
| 103 | 9409, /*97^2*/ |
---|
| 104 | 10201, /*101^2*/ |
---|
| 105 | 10609, /*103^2*/ |
---|
| 106 | 11449, /*107^2*/ |
---|
| 107 | 11881, /*109^2*/ |
---|
| 108 | 12769, /*113^2*/ |
---|
| 109 | 16129, /*127^2*/ |
---|
| 110 | 17161, /*131^2*/ |
---|
| 111 | 18769, /*137^2*/ |
---|
| 112 | 19321, /*139^2*/ |
---|
| 113 | 22201, /*149^2*/ |
---|
| 114 | 22801, /*151^2*/ |
---|
| 115 | 24649, /*157^2*/ |
---|
| 116 | 26569, /*163^2*/ |
---|
| 117 | 27889, /*167^2*/ |
---|
| 118 | 29929, /*173^2*/ |
---|
| 119 | 32041, /*179^2*/ |
---|
| 120 | 32761, /*181^2*/ |
---|
| 121 | 36481, /*191^2*/ |
---|
| 122 | 37249, /*193^2*/ |
---|
| 123 | 38809, /*197^2*/ |
---|
| 124 | 39601, /*199^2*/ |
---|
| 125 | 49729, /*223^2*/ |
---|
| 126 | 44521, /*211^2*/ |
---|
| 127 | 51529, /*227^2*/ |
---|
| 128 | 52441, /*229^2*/ |
---|
| 129 | 54289, /*233^2*/ |
---|
| 130 | 57121, /*239^2*/ |
---|
| 131 | 58081, /*241^2*/ |
---|
[85e68dd] | 132 | 63001, /*251^2*/ |
---|
[35aab3] | 133 | 0 }; |
---|
| 134 | |
---|
| 135 | /*1 |
---|
| 136 | * numbers in GF(p^n): |
---|
| 137 | * let nfCharQ=q=nfCharP^n=p^n |
---|
| 138 | * GF(q)\{0} will be generated by powers of an element Z |
---|
| 139 | * Z^i will be represented by the int i, 1 by the int 0, 0 by the int q=nfChar |
---|
| 140 | */ |
---|
| 141 | |
---|
| 142 | #ifdef LDEBUG |
---|
| 143 | /*2 |
---|
| 144 | * debugging: is a a valid representation of a number ? |
---|
| 145 | */ |
---|
[5e3046] | 146 | BOOLEAN nfDBTest (number a, const char *f, const int l, const coeffs r) |
---|
[35aab3] | 147 | { |
---|
[7f7b2a] | 148 | assume( r->m_nfPlus1Table != NULL ); |
---|
[5e3046] | 149 | if (((long)a<0L) || ((long)a>(long)r->m_nfCharQ)) |
---|
[35aab3] | 150 | { |
---|
[7447d8] | 151 | Print("wrong %d in %s:%d\n",(int)((long)a),f,l); |
---|
[35aab3] | 152 | return FALSE; |
---|
| 153 | } |
---|
| 154 | int i=0; |
---|
| 155 | do |
---|
| 156 | { |
---|
[5e3046] | 157 | if (r->m_nfPlus1Table[i]>r->m_nfCharQ) |
---|
[35aab3] | 158 | { |
---|
[5e3046] | 159 | Print("wrong table %d=%d in %s:%d\n",i,r->m_nfPlus1Table[i],f,l); |
---|
[35aab3] | 160 | return FALSE; |
---|
| 161 | } |
---|
| 162 | i++; |
---|
[5e3046] | 163 | } while (i<r->m_nfCharQ); |
---|
[35aab3] | 164 | return TRUE; |
---|
| 165 | } |
---|
[5e3046] | 166 | #define nfTest(N, R) nfDBTest(N,__FILE__,__LINE__, R) |
---|
[35aab3] | 167 | #endif |
---|
| 168 | |
---|
| 169 | /*2 |
---|
| 170 | * k >= 0 ? |
---|
| 171 | */ |
---|
[3510a6] | 172 | BOOLEAN nfGreaterZero (number k, const coeffs r) |
---|
[35aab3] | 173 | { |
---|
| 174 | #ifdef LDEBUG |
---|
[5e3046] | 175 | nfTest(k, r); |
---|
[35aab3] | 176 | #endif |
---|
[3510a6] | 177 | return !nfIsZero(k, r) && !nfIsMOne(k, r); |
---|
[35aab3] | 178 | } |
---|
| 179 | |
---|
| 180 | /*2 |
---|
| 181 | * a*b |
---|
| 182 | */ |
---|
[3510a6] | 183 | number nfMult (number a,number b, const coeffs r) |
---|
[35aab3] | 184 | { |
---|
| 185 | #ifdef LDEBUG |
---|
[5e3046] | 186 | nfTest(a, r); |
---|
| 187 | nfTest(b, r); |
---|
[35aab3] | 188 | #endif |
---|
[5e3046] | 189 | if (((long)a == (long)r->m_nfCharQ) || ((long)b == (long)r->m_nfCharQ)) |
---|
| 190 | return (number)(long)r->m_nfCharQ; |
---|
[35aab3] | 191 | /*else*/ |
---|
[7447d8] | 192 | int i=(int)((long)a+(long)b); |
---|
[5e3046] | 193 | if (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1; |
---|
[35aab3] | 194 | #ifdef LDEBUG |
---|
[5e3046] | 195 | nfTest((number)(long)i, r); |
---|
[35aab3] | 196 | #endif |
---|
[1c7953] | 197 | return (number)(long)i; |
---|
[35aab3] | 198 | } |
---|
| 199 | |
---|
| 200 | /*2 |
---|
| 201 | * int -> number |
---|
| 202 | */ |
---|
[2f3764] | 203 | number nfInit (long i, const coeffs r) |
---|
[35aab3] | 204 | { |
---|
[7f7b2a] | 205 | assume( r->m_nfPlus1Table != NULL ); |
---|
[35aab3] | 206 | // Hmm .. this is just to prevent initialization |
---|
| 207 | // from nfInitChar to go into an infinite loop |
---|
[5e3046] | 208 | if (i==0) return (number)(long)r->m_nfCharQ; |
---|
| 209 | while (i < 0) i += r->m_nfCharP; |
---|
| 210 | while (i >= r->m_nfCharP) i -= r->m_nfCharP; |
---|
| 211 | if (i==0) return (number)(long)r->m_nfCharQ; |
---|
[900802] | 212 | unsigned short c=0; |
---|
[35aab3] | 213 | while (i>1) |
---|
| 214 | { |
---|
[5e3046] | 215 | c=r->m_nfPlus1Table[c]; |
---|
[35aab3] | 216 | i--; |
---|
| 217 | } |
---|
| 218 | #ifdef LDEBUG |
---|
[5e3046] | 219 | nfTest((number)(long)c, r); |
---|
[35aab3] | 220 | #endif |
---|
[1c7953] | 221 | return (number)(long)c; |
---|
[35aab3] | 222 | } |
---|
| 223 | |
---|
| 224 | /* |
---|
| 225 | * the generating element `z` |
---|
| 226 | */ |
---|
[7fee876] | 227 | number nfParameter (int i, const coeffs) |
---|
[35aab3] | 228 | { |
---|
[121fd9] | 229 | assume(i==1); |
---|
[bdda8c2] | 230 | |
---|
[7fee876] | 231 | if( i == 1 ) |
---|
| 232 | return (number)1; |
---|
| 233 | |
---|
| 234 | return NULL; |
---|
[35aab3] | 235 | } |
---|
| 236 | |
---|
| 237 | /*2 |
---|
| 238 | * the degree of the "alg. number" |
---|
| 239 | */ |
---|
[da5d77] | 240 | static int nfParDeg(number n, const coeffs r) |
---|
[35aab3] | 241 | { |
---|
| 242 | #ifdef LDEBUG |
---|
[5e3046] | 243 | nfTest(n, r); |
---|
[35aab3] | 244 | #endif |
---|
[5e3046] | 245 | if((long)r->m_nfCharQ == (long)n) return -1; |
---|
[7447d8] | 246 | return (int)((long)n); |
---|
[35aab3] | 247 | } |
---|
| 248 | |
---|
| 249 | /*2 |
---|
| 250 | * number -> int |
---|
| 251 | */ |
---|
[2d2e40] | 252 | int nfInt (number &, const coeffs ) |
---|
[35aab3] | 253 | { |
---|
| 254 | return 0; |
---|
| 255 | } |
---|
| 256 | |
---|
| 257 | /*2 |
---|
| 258 | * a + b |
---|
| 259 | */ |
---|
[3510a6] | 260 | number nfAdd (number a, number b, const coeffs R) |
---|
[35aab3] | 261 | { |
---|
| 262 | /*4 z^a+z^b=z^b*(z^(a-b)+1), if a>=b; * |
---|
| 263 | * =z^a*(z^(b-a)+1) if a<b */ |
---|
| 264 | #ifdef LDEBUG |
---|
[5e3046] | 265 | nfTest(a, R); |
---|
| 266 | nfTest(b, R); |
---|
[35aab3] | 267 | #endif |
---|
[5e3046] | 268 | if ((long)R->m_nfCharQ == (long)a) return b; |
---|
| 269 | if ((long)R->m_nfCharQ == (long)b) return a; |
---|
[7447d8] | 270 | long zb,zab,r; |
---|
| 271 | if ((long)a >= (long)b) |
---|
[35aab3] | 272 | { |
---|
[7447d8] | 273 | zb = (long)b; |
---|
| 274 | zab = (long)a-(long)b; |
---|
[35aab3] | 275 | } |
---|
| 276 | else |
---|
| 277 | { |
---|
[7447d8] | 278 | zb = (long)a; |
---|
| 279 | zab = (long)b-(long)a; |
---|
[35aab3] | 280 | } |
---|
| 281 | #ifdef LDEBUG |
---|
[5e3046] | 282 | nfTest((number)zab, R); |
---|
[35aab3] | 283 | #endif |
---|
[5e3046] | 284 | if (R->m_nfPlus1Table[zab]==R->m_nfCharQ) r=(long)R->m_nfCharQ; /*if z^(a-b)+1 =0*/ |
---|
[35aab3] | 285 | else |
---|
| 286 | { |
---|
[5e3046] | 287 | r= zb+(long)R->m_nfPlus1Table[zab]; |
---|
| 288 | if(r>=(long)R->m_nfCharQ1) r-=(long)R->m_nfCharQ1; |
---|
[35aab3] | 289 | } |
---|
| 290 | #ifdef LDEBUG |
---|
[5e3046] | 291 | nfTest((number)r, R); |
---|
[35aab3] | 292 | #endif |
---|
| 293 | return (number)r; |
---|
| 294 | } |
---|
| 295 | |
---|
| 296 | /*2 |
---|
| 297 | * a - b |
---|
| 298 | */ |
---|
[3510a6] | 299 | number nfSub (number a, number b, const coeffs r) |
---|
[35aab3] | 300 | { |
---|
[3510a6] | 301 | number mb = nfNeg(b, r); |
---|
| 302 | return nfAdd(a,mb,r); |
---|
[35aab3] | 303 | } |
---|
| 304 | |
---|
| 305 | /*2 |
---|
| 306 | * a == 0 ? |
---|
| 307 | */ |
---|
[3510a6] | 308 | BOOLEAN nfIsZero (number a, const coeffs r) |
---|
[35aab3] | 309 | { |
---|
| 310 | #ifdef LDEBUG |
---|
[5e3046] | 311 | nfTest(a, r); |
---|
[35aab3] | 312 | #endif |
---|
[5e3046] | 313 | return (long)r->m_nfCharQ == (long)a; |
---|
[35aab3] | 314 | } |
---|
| 315 | |
---|
| 316 | /*2 |
---|
| 317 | * a == 1 ? |
---|
| 318 | */ |
---|
[3510a6] | 319 | BOOLEAN nfIsOne (number a, const coeffs r) |
---|
[35aab3] | 320 | { |
---|
| 321 | #ifdef LDEBUG |
---|
[5e3046] | 322 | nfTest(a, r); |
---|
[35aab3] | 323 | #endif |
---|
[7447d8] | 324 | return 0L == (long)a; |
---|
[35aab3] | 325 | } |
---|
| 326 | |
---|
| 327 | /*2 |
---|
| 328 | * a == -1 ? |
---|
| 329 | */ |
---|
[3510a6] | 330 | BOOLEAN nfIsMOne (number a, const coeffs r) |
---|
[35aab3] | 331 | { |
---|
| 332 | #ifdef LDEBUG |
---|
[5e3046] | 333 | nfTest(a, r); |
---|
[35aab3] | 334 | #endif |
---|
[7447d8] | 335 | if (0L == (long)a) return FALSE; /* special handling of char 2*/ |
---|
[5e3046] | 336 | return (long)r->m_nfM1 == (long)a; |
---|
[35aab3] | 337 | } |
---|
| 338 | |
---|
| 339 | /*2 |
---|
| 340 | * a / b |
---|
| 341 | */ |
---|
[3510a6] | 342 | number nfDiv (number a,number b, const coeffs r) |
---|
[35aab3] | 343 | { |
---|
| 344 | #ifdef LDEBUG |
---|
[5e3046] | 345 | nfTest(b, r); |
---|
[35aab3] | 346 | #endif |
---|
[5e3046] | 347 | if ((long)b==(long)r->m_nfCharQ) |
---|
[35aab3] | 348 | { |
---|
[b7e838] | 349 | WerrorS(nDivBy0); |
---|
[5e3046] | 350 | return (number)((long)r->m_nfCharQ); |
---|
[35aab3] | 351 | } |
---|
| 352 | #ifdef LDEBUG |
---|
[5e3046] | 353 | nfTest(a, r); |
---|
[35aab3] | 354 | #endif |
---|
[5e3046] | 355 | if ((long)a==(long)r->m_nfCharQ) |
---|
| 356 | return (number)((long)r->m_nfCharQ); |
---|
[35aab3] | 357 | /*else*/ |
---|
[7447d8] | 358 | long s = (long)a - (long)b; |
---|
| 359 | if (s < 0L) |
---|
[5e3046] | 360 | s += (long)r->m_nfCharQ1; |
---|
[35aab3] | 361 | #ifdef LDEBUG |
---|
[5e3046] | 362 | nfTest((number)s, r); |
---|
[35aab3] | 363 | #endif |
---|
| 364 | return (number)s; |
---|
| 365 | } |
---|
| 366 | |
---|
| 367 | /*2 |
---|
| 368 | * 1 / c |
---|
| 369 | */ |
---|
[3510a6] | 370 | number nfInvers (number c, const coeffs r) |
---|
[35aab3] | 371 | { |
---|
| 372 | #ifdef LDEBUG |
---|
[5e3046] | 373 | nfTest(c, r); |
---|
[35aab3] | 374 | #endif |
---|
[5e3046] | 375 | if ((long)c==(long)r->m_nfCharQ) |
---|
[35aab3] | 376 | { |
---|
[b7e838] | 377 | WerrorS(nDivBy0); |
---|
[5e3046] | 378 | return (number)((long)r->m_nfCharQ); |
---|
[35aab3] | 379 | } |
---|
| 380 | #ifdef LDEBUG |
---|
[5e3046] | 381 | nfTest(((number)((long)r->m_nfCharQ1-(long)c)), r); |
---|
[35aab3] | 382 | #endif |
---|
[5e3046] | 383 | return (number)((long)r->m_nfCharQ1-(long)c); |
---|
[35aab3] | 384 | } |
---|
| 385 | |
---|
| 386 | /*2 |
---|
| 387 | * -c |
---|
| 388 | */ |
---|
[3510a6] | 389 | number nfNeg (number c, const coeffs r) |
---|
[35aab3] | 390 | { |
---|
| 391 | /*4 -z^c=z^c*(-1)=z^c*nfM1*/ |
---|
| 392 | #ifdef LDEBUG |
---|
[5e3046] | 393 | nfTest(c, r); |
---|
[35aab3] | 394 | #endif |
---|
[5e3046] | 395 | if ((long)r->m_nfCharQ == (long)c) return c; |
---|
| 396 | long i=(long)c+(long)r->m_nfM1; |
---|
| 397 | if (i>=(long)r->m_nfCharQ1) i-=(long)r->m_nfCharQ1; |
---|
[35aab3] | 398 | #ifdef LDEBUG |
---|
[5e3046] | 399 | nfTest((number)i, r); |
---|
[35aab3] | 400 | #endif |
---|
| 401 | return (number)i; |
---|
| 402 | } |
---|
| 403 | |
---|
| 404 | /*2 |
---|
| 405 | * a > b ? |
---|
| 406 | */ |
---|
[3510a6] | 407 | BOOLEAN nfGreater (number a,number b, const coeffs r) |
---|
[35aab3] | 408 | { |
---|
| 409 | #ifdef LDEBUG |
---|
[5e3046] | 410 | nfTest(a, r); |
---|
| 411 | nfTest(b, r); |
---|
[35aab3] | 412 | #endif |
---|
[7447d8] | 413 | return (long)a != (long)b; |
---|
[35aab3] | 414 | } |
---|
| 415 | |
---|
| 416 | /*2 |
---|
| 417 | * a == b ? |
---|
| 418 | */ |
---|
[3510a6] | 419 | BOOLEAN nfEqual (number a,number b, const coeffs r) |
---|
[35aab3] | 420 | { |
---|
| 421 | #ifdef LDEBUG |
---|
[5e3046] | 422 | nfTest(a, r); |
---|
| 423 | nfTest(b, r); |
---|
[35aab3] | 424 | #endif |
---|
[7447d8] | 425 | return (long)a == (long)b; |
---|
[35aab3] | 426 | } |
---|
| 427 | |
---|
| 428 | /*2 |
---|
| 429 | * write via StringAppend |
---|
| 430 | */ |
---|
[ce1f78] | 431 | static void nfWriteLong (number &a, const coeffs r) |
---|
| 432 | { |
---|
| 433 | #ifdef LDEBUG |
---|
| 434 | nfTest(a, r); |
---|
| 435 | #endif |
---|
| 436 | if ((long)a==(long)r->m_nfCharQ) StringAppendS("0"); |
---|
| 437 | else if ((long)a==0L) StringAppendS("1"); |
---|
| 438 | else if (nfIsMOne(a, r)) StringAppendS("-1"); |
---|
| 439 | else |
---|
| 440 | { |
---|
[7fee876] | 441 | StringAppendS(n_ParameterNames(r)[0]); |
---|
[ce1f78] | 442 | if ((long)a!=1L) |
---|
| 443 | { |
---|
| 444 | StringAppend("^%d",(int)((long)a)); // long output! |
---|
| 445 | } |
---|
| 446 | } |
---|
| 447 | } |
---|
| 448 | |
---|
| 449 | |
---|
| 450 | /*2 |
---|
| 451 | * write (shortert output) via StringAppend |
---|
| 452 | */ |
---|
| 453 | static void nfWriteShort (number &a, const coeffs r) |
---|
[35aab3] | 454 | { |
---|
| 455 | #ifdef LDEBUG |
---|
[5e3046] | 456 | nfTest(a, r); |
---|
[35aab3] | 457 | #endif |
---|
[5e3046] | 458 | if ((long)a==(long)r->m_nfCharQ) StringAppendS("0"); |
---|
[7447d8] | 459 | else if ((long)a==0L) StringAppendS("1"); |
---|
[3510a6] | 460 | else if (nfIsMOne(a, r)) StringAppendS("-1"); |
---|
[35aab3] | 461 | else |
---|
| 462 | { |
---|
[7fee876] | 463 | StringAppendS(n_ParameterNames(r)[0]); |
---|
[7447d8] | 464 | if ((long)a!=1L) |
---|
[35aab3] | 465 | { |
---|
[7447d8] | 466 | StringAppend("%d",(int)((long)a)); |
---|
[35aab3] | 467 | } |
---|
| 468 | } |
---|
| 469 | } |
---|
| 470 | |
---|
| 471 | /*2 |
---|
| 472 | * |
---|
| 473 | */ |
---|
[3510a6] | 474 | char * nfName(number a, const coeffs r) |
---|
[35aab3] | 475 | { |
---|
| 476 | #ifdef LDEBUG |
---|
[5e3046] | 477 | nfTest(a, r); |
---|
[35aab3] | 478 | #endif |
---|
| 479 | char *s; |
---|
[7fee876] | 480 | const char * const nf_Parameter=n_ParameterNames(r)[0]; |
---|
[5e3046] | 481 | if (((long)a==(long)r->m_nfCharQ) || ((long)a==0L)) return NULL; |
---|
[7447d8] | 482 | else if ((long)a==1L) |
---|
[35aab3] | 483 | { |
---|
[7fee876] | 484 | return omStrDup(nf_Parameter); |
---|
[35aab3] | 485 | } |
---|
| 486 | else |
---|
| 487 | { |
---|
[7fee876] | 488 | s=(char *)omAlloc(4+strlen(nf_Parameter)); |
---|
| 489 | sprintf(s,"%s%d",nf_Parameter,(int)((long)a)); |
---|
[35aab3] | 490 | } |
---|
| 491 | return s; |
---|
| 492 | } |
---|
| 493 | /*2 |
---|
| 494 | * c ^ i with i>=0 |
---|
| 495 | */ |
---|
[3510a6] | 496 | void nfPower (number a, int i, number * result, const coeffs r) |
---|
[35aab3] | 497 | { |
---|
| 498 | #ifdef LDEBUG |
---|
[5e3046] | 499 | nfTest(a, r); |
---|
[35aab3] | 500 | #endif |
---|
| 501 | if (i==0) |
---|
| 502 | { |
---|
| 503 | //*result=nfInit(1); |
---|
[7447d8] | 504 | *result = (number)0L; |
---|
[35aab3] | 505 | } |
---|
| 506 | else if (i==1) |
---|
| 507 | { |
---|
| 508 | *result = a; |
---|
| 509 | } |
---|
| 510 | else |
---|
| 511 | { |
---|
[3510a6] | 512 | nfPower(a,i-1,result, r); |
---|
| 513 | *result = nfMult(a,*result, r); |
---|
[35aab3] | 514 | } |
---|
| 515 | #ifdef LDEBUG |
---|
[5e3046] | 516 | nfTest(*result, r); |
---|
[35aab3] | 517 | #endif |
---|
| 518 | } |
---|
| 519 | |
---|
| 520 | /*4 |
---|
| 521 | * read an integer (with reduction mod p) |
---|
| 522 | */ |
---|
[5e3046] | 523 | static const char* nfEati(const char *s, int *i, const coeffs r) |
---|
[35aab3] | 524 | { |
---|
| 525 | if (*s >= '0' && *s <= '9') |
---|
| 526 | { |
---|
| 527 | *i = 0; |
---|
| 528 | do |
---|
| 529 | { |
---|
| 530 | *i *= 10; |
---|
| 531 | *i += *s++ - '0'; |
---|
[a2cdd62] | 532 | if (*i > (MAX_INT_VAL / 10)) *i = *i % r->m_nfCharP; |
---|
[35aab3] | 533 | } |
---|
| 534 | while (*s >= '0' && *s <= '9'); |
---|
[5e3046] | 535 | if (*i >= r->m_nfCharP) *i = *i % r->m_nfCharP; |
---|
[35aab3] | 536 | } |
---|
| 537 | else *i = 1; |
---|
| 538 | return s; |
---|
| 539 | } |
---|
| 540 | |
---|
| 541 | /*2 |
---|
| 542 | * read a number |
---|
| 543 | */ |
---|
[3510a6] | 544 | const char * nfRead (const char *s, number *a, const coeffs r) |
---|
[35aab3] | 545 | { |
---|
| 546 | int i; |
---|
| 547 | number z; |
---|
| 548 | number n; |
---|
| 549 | |
---|
[5e3046] | 550 | s = nfEati(s, &i, r); |
---|
[3510a6] | 551 | z=nfInit(i, r); |
---|
[35aab3] | 552 | *a=z; |
---|
| 553 | if (*s == '/') |
---|
| 554 | { |
---|
| 555 | s++; |
---|
[5e3046] | 556 | s = nfEati(s, &i, r); |
---|
[3510a6] | 557 | n=nfInit(i, r); |
---|
| 558 | *a = nfDiv(z,n,r); |
---|
[35aab3] | 559 | } |
---|
[7fee876] | 560 | const char * const nf_Parameter = n_ParameterNames(r)[0]; |
---|
| 561 | const int N = strlen(nf_Parameter); |
---|
| 562 | if (strncmp(s,nf_Parameter, N)==0) |
---|
[35aab3] | 563 | { |
---|
[7fee876] | 564 | s += N; |
---|
[35aab3] | 565 | if ((*s >= '0') && (*s <= '9')) |
---|
| 566 | { |
---|
| 567 | s=eati(s,&i); |
---|
[5e3046] | 568 | while (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1; |
---|
[35aab3] | 569 | } |
---|
| 570 | else |
---|
| 571 | i=1; |
---|
[01a57b] | 572 | z=(number)(long)i; |
---|
[3510a6] | 573 | *a=nfMult(*a,z,r); |
---|
[35aab3] | 574 | } |
---|
| 575 | #ifdef LDEBUG |
---|
[5e3046] | 576 | nfTest(*a, r); |
---|
[35aab3] | 577 | #endif |
---|
| 578 | return s; |
---|
| 579 | } |
---|
| 580 | |
---|
| 581 | int gf_tab_numdigits62 ( int q ); |
---|
| 582 | int convertback62 ( char * p, int n ); |
---|
| 583 | |
---|
| 584 | int nfMinPoly[16]; |
---|
| 585 | |
---|
[d0a51ee] | 586 | void nfShowMipo(const coeffs r) |
---|
[35aab3] | 587 | { |
---|
| 588 | int i=nfMinPoly[0]; |
---|
| 589 | int j=0; |
---|
| 590 | loop |
---|
| 591 | { |
---|
| 592 | j++; |
---|
| 593 | if (nfMinPoly[j]!=0) |
---|
[7fee876] | 594 | StringAppend("%d*%s^%d",nfMinPoly[j],n_ParameterNames(r)[0],i); |
---|
[35aab3] | 595 | i--; |
---|
| 596 | if(i<0) break; |
---|
| 597 | if (nfMinPoly[j]!=0) |
---|
| 598 | StringAppendS("+"); |
---|
| 599 | } |
---|
| 600 | } |
---|
| 601 | |
---|
| 602 | static void nfReadMipo(char *s) |
---|
| 603 | { |
---|
| 604 | const char *l=strchr(s,';')+1; |
---|
| 605 | char *n; |
---|
| 606 | int i=strtol(l,&n,10); |
---|
| 607 | l=n; |
---|
| 608 | int j=1; |
---|
| 609 | nfMinPoly[0]=i; |
---|
| 610 | while(i>=0) |
---|
| 611 | { |
---|
| 612 | nfMinPoly[j]=strtol(l,&n,10); |
---|
| 613 | if (l==n) break; |
---|
| 614 | l=n; |
---|
| 615 | j++; |
---|
| 616 | i--; |
---|
| 617 | } |
---|
| 618 | if (i>=0) |
---|
| 619 | { |
---|
| 620 | WerrorS("error in reading minpoly from gftables"); |
---|
| 621 | } |
---|
| 622 | } |
---|
| 623 | |
---|
| 624 | /*2 |
---|
| 625 | * init global variables from files 'gftables/%d' |
---|
| 626 | */ |
---|
[5e3046] | 627 | void nfReadTable(const int c, const coeffs r) |
---|
[35aab3] | 628 | { |
---|
| 629 | //Print("GF(%d)\n",c); |
---|
[5e3046] | 630 | if ((c==r->m_nfCharQ)||(c==-r->m_nfCharQ)) |
---|
[35aab3] | 631 | /*this field is already set*/ return; |
---|
| 632 | int i=0; |
---|
[bdda8c2] | 633 | |
---|
| 634 | while ((fftable[i]!=c) && (fftable[i]!=0)) |
---|
[1b078e] | 635 | i++; |
---|
[bdda8c2] | 636 | |
---|
[35aab3] | 637 | if (fftable[i]==0) |
---|
[1b078e] | 638 | { |
---|
[cbe144] | 639 | #ifndef NDEBUG |
---|
| 640 | Warn("illegal GF-table size: %d", c); |
---|
| 641 | #endif |
---|
[35aab3] | 642 | return; |
---|
[1b078e] | 643 | } |
---|
| 644 | |
---|
[5e3046] | 645 | if (r->m_nfCharQ > 1) |
---|
[35aab3] | 646 | { |
---|
[5e3046] | 647 | omFreeSize( (ADDRESS)r->m_nfPlus1Table,r->m_nfCharQ*sizeof(unsigned short) ); |
---|
| 648 | r->m_nfPlus1Table=NULL; |
---|
[35aab3] | 649 | } |
---|
| 650 | if ((c>1) || (c<0)) |
---|
| 651 | { |
---|
[5e3046] | 652 | if (c>1) r->m_nfCharQ = c; |
---|
| 653 | else r->m_nfCharQ = -c; |
---|
[35aab3] | 654 | char buf[100]; |
---|
[72486f0] | 655 | sprintf(buf,"gftables/%d",r->m_nfCharQ); |
---|
[35aab3] | 656 | FILE * fp = feFopen(buf,"r",NULL,TRUE); |
---|
| 657 | if (fp==NULL) |
---|
| 658 | { |
---|
| 659 | return; |
---|
| 660 | } |
---|
| 661 | if(!fgets( buf, sizeof(buf), fp)) return; |
---|
| 662 | if(strcmp(buf,"@@ factory GF(q) table @@\n")!=0) |
---|
| 663 | { |
---|
| 664 | goto err; |
---|
| 665 | } |
---|
| 666 | if(!fgets( buf, sizeof(buf), fp)) |
---|
| 667 | { |
---|
| 668 | goto err; |
---|
| 669 | } |
---|
| 670 | int q; |
---|
[bdda8c2] | 671 | int res = -1; |
---|
| 672 | do |
---|
| 673 | { |
---|
| 674 | res = sscanf(buf,"%d %d",&r->m_nfCharP,&q); |
---|
| 675 | } |
---|
| 676 | while((res < 0) and (errno == EINTR)); |
---|
| 677 | |
---|
[35aab3] | 678 | nfReadMipo(buf); |
---|
[5e3046] | 679 | r->m_nfCharQ1=r->m_nfCharQ-1; |
---|
[35aab3] | 680 | //Print("nfCharQ=%d,nfCharQ1=%d,mipo=>>%s<<\n",nfCharQ,nfCharQ1,buf); |
---|
[5e3046] | 681 | r->m_nfPlus1Table= (unsigned short *)omAlloc( (r->m_nfCharQ)*sizeof(unsigned short) ); |
---|
| 682 | int digs = gf_tab_numdigits62( r->m_nfCharQ ); |
---|
[35aab3] | 683 | char * bufptr; |
---|
| 684 | int i = 1; |
---|
| 685 | int k; |
---|
[5e3046] | 686 | while ( i < r->m_nfCharQ ) |
---|
[35aab3] | 687 | { |
---|
| 688 | fgets( buf, sizeof(buf), fp); |
---|
| 689 | //( strlen( buffer ) == (size_t)digs * 30, "illegal table" ); |
---|
| 690 | bufptr = buf; |
---|
| 691 | k = 0; |
---|
[5e3046] | 692 | while ( (i < r->m_nfCharQ) && (k < 30) ) |
---|
[35aab3] | 693 | { |
---|
[5e3046] | 694 | r->m_nfPlus1Table[i] = convertback62( bufptr, digs ); |
---|
| 695 | if(r->m_nfPlus1Table[i]>r->m_nfCharQ) |
---|
[35aab3] | 696 | { |
---|
[5e3046] | 697 | Print("wrong entry %d: %d(%c%c%c)\n",i,r->m_nfPlus1Table[i],bufptr[0],bufptr[1],bufptr[2]); |
---|
[35aab3] | 698 | } |
---|
| 699 | bufptr += digs; |
---|
[5e3046] | 700 | if (r->m_nfPlus1Table[i]==r->m_nfCharQ) |
---|
[35aab3] | 701 | { |
---|
[5e3046] | 702 | if(i==r->m_nfCharQ1) |
---|
[35aab3] | 703 | { |
---|
[5e3046] | 704 | r->m_nfM1=0; |
---|
[35aab3] | 705 | } |
---|
| 706 | else |
---|
| 707 | { |
---|
[5e3046] | 708 | r->m_nfM1=i; |
---|
[35aab3] | 709 | } |
---|
| 710 | } |
---|
| 711 | i++; k++; |
---|
| 712 | } |
---|
| 713 | } |
---|
[5e3046] | 714 | r->m_nfPlus1Table[0]=r->m_nfPlus1Table[r->m_nfCharQ1]; |
---|
[35aab3] | 715 | } |
---|
| 716 | else |
---|
[5e3046] | 717 | r->m_nfCharQ=0; |
---|
[35aab3] | 718 | #ifdef LDEBUG |
---|
[5e3046] | 719 | nfTest((number)0, r); |
---|
[35aab3] | 720 | #endif |
---|
| 721 | return; |
---|
| 722 | err: |
---|
[5e3046] | 723 | Werror("illegal GF-table %d",r->m_nfCharQ); |
---|
[35aab3] | 724 | } |
---|
| 725 | |
---|
| 726 | /*2 |
---|
| 727 | * map Z/p -> GF(p,n) |
---|
| 728 | */ |
---|
[49a64cf] | 729 | number nfMapP(number c, const coeffs, const coeffs dst) |
---|
[35aab3] | 730 | { |
---|
[d0a51ee] | 731 | return nfInit((int)((long)c), dst); |
---|
[35aab3] | 732 | } |
---|
| 733 | |
---|
[85e68dd] | 734 | /*2 |
---|
| 735 | * map GF(p,n1) -> GF(p,n2), n1 < n2, n1 | n2 |
---|
| 736 | */ |
---|
| 737 | int nfMapGG_factor; |
---|
[49a64cf] | 738 | number nfMapGG(number c, const coeffs src, const coeffs) |
---|
[85e68dd] | 739 | { |
---|
| 740 | int i=(long)c; |
---|
| 741 | i*= nfMapGG_factor; |
---|
[5e3046] | 742 | while (i >src->m_nfCharQ1) i-=src->m_nfCharQ1; |
---|
[85e68dd] | 743 | return (number)((long)i); |
---|
| 744 | } |
---|
| 745 | /*2 |
---|
| 746 | * map GF(p,n1) -> GF(p,n2), n1 > n2, n2 | n1 |
---|
| 747 | */ |
---|
[49a64cf] | 748 | number nfMapGGrev(number c, const coeffs src, const coeffs) |
---|
[85e68dd] | 749 | { |
---|
| 750 | int ex=(int)((long)c); |
---|
| 751 | if ((ex % nfMapGG_factor)==0) |
---|
| 752 | return (number)(((long)ex) / ((long)nfMapGG_factor)); |
---|
| 753 | else |
---|
[5e3046] | 754 | return (number)(long)src->m_nfCharQ; /* 0 */ |
---|
[85e68dd] | 755 | } |
---|
| 756 | |
---|
[35aab3] | 757 | /*2 |
---|
| 758 | * set map function nMap ... -> GF(p,n) |
---|
| 759 | */ |
---|
[a0ce49] | 760 | nMapFunc nfSetMap(const coeffs src, const coeffs dst) |
---|
[35aab3] | 761 | { |
---|
[1cce47] | 762 | if (nCoeff_is_GF(src,src->m_nfCharQ)) |
---|
[35aab3] | 763 | { |
---|
[d0a51ee] | 764 | return ndCopyMap; /* GF(p,n) -> GF(p,n) */ |
---|
[35aab3] | 765 | } |
---|
[1cce47] | 766 | if (nCoeff_is_GF(src)) |
---|
[85e68dd] | 767 | { |
---|
[a0ce49] | 768 | const coeffs r = dst; |
---|
[85e68dd] | 769 | int q=src->ch; |
---|
[5e3046] | 770 | if ((src->m_nfCharQ % q)==0) /* GF(p,n1) -> GF(p,n2), n2 > n1 */ |
---|
[85e68dd] | 771 | { |
---|
| 772 | // check if n2 is a multiple of n1 |
---|
| 773 | int n1=1; |
---|
[5e3046] | 774 | int qq=r->m_nfCharP; |
---|
| 775 | while(qq!=q) { qq *= r->m_nfCharP; n1++; } |
---|
[85e68dd] | 776 | int n2=1; |
---|
[5e3046] | 777 | qq=r->m_nfCharP; |
---|
| 778 | while(qq!=src->m_nfCharQ) { qq *= r->m_nfCharP; n2++; } |
---|
[2cba98d] | 779 | //Print("map %d^%d -> %d^%d\n",r->m_nfCharP,n1,r->m_nfCharP,n2); |
---|
[85e68dd] | 780 | if ((n2 % n1)==0) |
---|
| 781 | { |
---|
[2cba98d] | 782 | int save_ch=r->m_nfCharQ; |
---|
| 783 | nfReadTable(src->m_nfCharQ, r); |
---|
[5e3046] | 784 | int nn=r->m_nfPlus1Table[0]; |
---|
| 785 | nfReadTable(save_ch, r); |
---|
| 786 | nfMapGG_factor= r->m_nfPlus1Table[0] / nn; |
---|
[2cba98d] | 787 | //Print("nfMapGG_factor=%d (%d / %d)\n",nfMapGG_factor, r->m_nfPlus1Table[0], nn); |
---|
[85e68dd] | 788 | return nfMapGG; |
---|
| 789 | } |
---|
| 790 | else if ((n1 % n2)==0) |
---|
| 791 | { |
---|
| 792 | nfMapGG_factor= (n1/n2); |
---|
| 793 | return nfMapGGrev; |
---|
| 794 | } |
---|
| 795 | else |
---|
| 796 | return NULL; |
---|
| 797 | } |
---|
| 798 | } |
---|
[fb875f1] | 799 | if (nCoeff_is_Zp(src,dst->m_nfCharP)) |
---|
[35aab3] | 800 | { |
---|
| 801 | return nfMapP; /* Z/p -> GF(p,n) */ |
---|
| 802 | } |
---|
| 803 | return NULL; /* default */ |
---|
| 804 | } |
---|
[5e3046] | 805 | |
---|
[b0bb93f] | 806 | static BOOLEAN nfCoeffIsEqual(const coeffs, n_coeffType, void*); |
---|
| 807 | |
---|
[7fee876] | 808 | static void nfKillChar(coeffs r) |
---|
| 809 | { |
---|
| 810 | char** p = (char**)n_ParameterNames(r); |
---|
| 811 | |
---|
| 812 | const int P = n_NumberOfParameters(r); |
---|
[bdda8c2] | 813 | |
---|
[7fee876] | 814 | for( int i = 1; i <= P; i++ ) |
---|
[bdda8c2] | 815 | if (p[i-1] != NULL) |
---|
[7fee876] | 816 | omFree( (ADDRESS)p[i-1] ); |
---|
[bdda8c2] | 817 | |
---|
| 818 | omFreeSize((ADDRESS)p, P * sizeof(char*)); |
---|
[7fee876] | 819 | } |
---|
| 820 | |
---|
[45cc512] | 821 | static char* nfCoeffString(const coeffs r) |
---|
| 822 | { |
---|
| 823 | const char *p=n_ParameterNames(r)[0]; |
---|
| 824 | char *s=(char*)omAlloc(11+1+strlen(p)); |
---|
| 825 | sprintf(s,"%d,%s",r->m_nfCharQ,p); |
---|
| 826 | return s; |
---|
| 827 | } |
---|
| 828 | |
---|
[1cce47] | 829 | BOOLEAN nfInitChar(coeffs r, void * parameter) |
---|
[5e3046] | 830 | { |
---|
| 831 | //r->cfInitChar=npInitChar; |
---|
[7fee876] | 832 | r->cfKillChar=nfKillChar; |
---|
[e9039a7] | 833 | r->nCoeffIsEqual=nfCoeffIsEqual; |
---|
[45cc512] | 834 | r->cfCoeffString=nfCoeffString; |
---|
[5e3046] | 835 | |
---|
| 836 | r->cfMult = nfMult; |
---|
| 837 | r->cfSub = nfSub; |
---|
| 838 | r->cfAdd = nfAdd; |
---|
| 839 | r->cfDiv = nfDiv; |
---|
| 840 | r->cfIntDiv= nfDiv; |
---|
| 841 | //r->cfIntMod= ndIntMod; |
---|
| 842 | r->cfExactDiv= nfDiv; |
---|
| 843 | r->cfInit = nfInit; |
---|
| 844 | //r->cfSize = ndSize; |
---|
| 845 | r->cfInt = nfInt; |
---|
| 846 | #ifdef HAVE_RINGS |
---|
| 847 | //r->cfDivComp = NULL; // only for ring stuff |
---|
| 848 | //r->cfIsUnit = NULL; // only for ring stuff |
---|
| 849 | //r->cfGetUnit = NULL; // only for ring stuff |
---|
| 850 | //r->cfExtGcd = NULL; // only for ring stuff |
---|
| 851 | // r->cfDivBy = NULL; // only for ring stuff |
---|
| 852 | #endif |
---|
| 853 | r->cfNeg = nfNeg; |
---|
| 854 | r->cfInvers= nfInvers; |
---|
| 855 | //r->cfCopy = ndCopy; |
---|
| 856 | //r->cfRePart = ndCopy; |
---|
| 857 | //r->cfImPart = ndReturn0; |
---|
[bdda8c2] | 858 | |
---|
[ce1f78] | 859 | r->cfWriteLong = nfWriteLong; |
---|
[d4fa60] | 860 | r->cfInit_bigint = nlModP; |
---|
[5e3046] | 861 | r->cfRead = nfRead; |
---|
| 862 | //r->cfNormalize=ndNormalize; |
---|
| 863 | r->cfGreater = nfGreater; |
---|
| 864 | r->cfEqual = nfEqual; |
---|
| 865 | r->cfIsZero = nfIsZero; |
---|
| 866 | r->cfIsOne = nfIsOne; |
---|
| 867 | r->cfIsMOne = nfIsMOne; |
---|
| 868 | r->cfGreaterZero = nfGreaterZero; |
---|
| 869 | r->cfPower = nfPower; |
---|
| 870 | //r->cfGcd = ndGcd; |
---|
| 871 | //r->cfLcm = ndGcd; |
---|
| 872 | //r->cfDelete= ndDelete; |
---|
| 873 | r->cfSetMap = nfSetMap; |
---|
| 874 | //r->cfName = ndName; |
---|
| 875 | // debug stuff |
---|
[c7e3d7] | 876 | r->cfCoeffWrite=nfCoeffWrite; |
---|
[bdda8c2] | 877 | |
---|
[da5d77] | 878 | r->cfParDeg = nfParDeg; |
---|
[a0ce49] | 879 | |
---|
| 880 | #ifdef LDEBUG |
---|
[5e3046] | 881 | r->cfDBTest=nfDBTest; |
---|
[a0ce49] | 882 | #endif |
---|
[bdda8c2] | 883 | |
---|
[5e3046] | 884 | // the variables: |
---|
| 885 | r->nNULL = (number)0; |
---|
[73a9ffb] | 886 | assume( getCoeffType(r) == n_GF ); |
---|
[5e3046] | 887 | |
---|
[2b7f4e] | 888 | GFInfo* p = (GFInfo *)(parameter); |
---|
| 889 | assume (p->GFChar > 0); |
---|
| 890 | assume (p->GFDegree > 0); |
---|
| 891 | |
---|
[dc06550] | 892 | const char * name = p->GFPar_name; |
---|
[bdda8c2] | 893 | |
---|
[5e3046] | 894 | r->m_nfCharQ = 0; |
---|
[dc06550] | 895 | r->m_nfCharP = p->GFChar; |
---|
| 896 | r->m_nfCharQ1 = 0; |
---|
[7fee876] | 897 | |
---|
| 898 | r->iNumberOfParameters = 1; |
---|
| 899 | r->cfParameter = nfParameter; |
---|
| 900 | |
---|
| 901 | char ** pParameterNames = (char **) omAlloc0(sizeof(char *)); |
---|
| 902 | pParameterNames[0] = omStrDup(name); //TODO use omAlloc for allocating memory and use strcpy? |
---|
| 903 | |
---|
| 904 | assume( pParameterNames != NULL ); |
---|
| 905 | assume( pParameterNames[0] != NULL ); |
---|
[bdda8c2] | 906 | |
---|
[7fee876] | 907 | r->pParameterNames = pParameterNames; |
---|
| 908 | // NOTE: r->m_nfParameter was replaced by n_ParameterNames(r)[0] |
---|
| 909 | |
---|
| 910 | // TODO: nfKillChar MUST destroy r->pParameterNames[0] (0-term. string) && r->pParameterNames (array of size 1) |
---|
| 911 | |
---|
[dc06550] | 912 | r->m_nfPlus1Table= NULL; |
---|
[5e3046] | 913 | |
---|
[ce1f78] | 914 | if (strlen(name) > 1) |
---|
| 915 | r->cfWriteShort = nfWriteLong; |
---|
| 916 | else |
---|
| 917 | r->cfWriteShort = nfWriteShort; |
---|
[e969ab6] | 918 | |
---|
[5e3046] | 919 | r->has_simple_Alloc=TRUE; |
---|
| 920 | r->has_simple_Inverse=TRUE; |
---|
[1b078e] | 921 | |
---|
| 922 | if(p->GFChar > (2<<15)) |
---|
| 923 | { |
---|
[cbe144] | 924 | #ifndef NDEBUG |
---|
| 925 | Warn("illegal characteristic"); |
---|
| 926 | #endif |
---|
[a9f584] | 927 | return TRUE; |
---|
[1b078e] | 928 | } |
---|
| 929 | |
---|
[bdda8c2] | 930 | const double check= log ((double) (p->GFChar)); |
---|
[1b078e] | 931 | |
---|
| 932 | if( (p->GFDegree * check) > sixteenlog2 ) |
---|
| 933 | { |
---|
[cbe144] | 934 | #ifndef NDEBUG |
---|
| 935 | Warn("Sorry: illegal size: %u ^ %u", p->GFChar, p->GFDegree ); |
---|
| 936 | #endif |
---|
[a9f584] | 937 | return TRUE; |
---|
[1b078e] | 938 | } |
---|
| 939 | |
---|
| 940 | int c = pow (p->GFChar, p->GFDegree); |
---|
| 941 | |
---|
[5e3046] | 942 | nfReadTable(c, r); |
---|
[bdda8c2] | 943 | |
---|
[7f7b2a] | 944 | if( r->m_nfPlus1Table == NULL ) |
---|
| 945 | { |
---|
[cbe144] | 946 | #ifndef NDEBUG |
---|
| 947 | Warn("Sorry: cannot init lookup table!"); |
---|
| 948 | #endif |
---|
[a9f584] | 949 | return TRUE; |
---|
[7f7b2a] | 950 | } |
---|
[bdda8c2] | 951 | |
---|
| 952 | |
---|
[1b078e] | 953 | assume (r -> m_nfCharQ > 0); |
---|
| 954 | |
---|
[bdda8c2] | 955 | r->ch = r->m_nfCharP; |
---|
[7f7b2a] | 956 | assume( r->m_nfPlus1Table != NULL ); |
---|
[bdda8c2] | 957 | |
---|
[a9f584] | 958 | return FALSE; |
---|
[bdda8c2] | 959 | |
---|
[5e3046] | 960 | } |
---|
[c7e3d7] | 961 | |
---|
[03f7b5] | 962 | void nfCoeffWrite (const coeffs r, BOOLEAN details) |
---|
[c7e3d7] | 963 | { |
---|
[e9039a7] | 964 | // m_nfCharQ = p^k where p is the characteristic (r->CharP) and k is GFDegree |
---|
| 965 | Print("// # ground field : %d\n",r->m_nfCharQ); |
---|
[7fee876] | 966 | Print("// primitive element : %s\n", n_ParameterNames(r)[0]); |
---|
[03f7b5] | 967 | if ( details ) |
---|
| 968 | { |
---|
| 969 | StringSetS("// minpoly : "); |
---|
| 970 | nfShowMipo(r); |
---|
[538512] | 971 | StringAppendS("\n"); |
---|
| 972 | char *s=StringEndS(); PrintS(s); omFree(s); |
---|
[03f7b5] | 973 | } |
---|
[bdda8c2] | 974 | else PrintS("// minpoly : ...\n"); |
---|
[c7e3d7] | 975 | } |
---|
| 976 | |
---|
[b0bb93f] | 977 | static BOOLEAN nfCoeffIsEqual (const coeffs r, n_coeffType n, void * parameter) |
---|
[e9039a7] | 978 | { |
---|
| 979 | if (n==n_GF) { |
---|
| 980 | GFInfo* p = (GFInfo *)(parameter); |
---|
| 981 | int c = pow (p->GFChar, p->GFDegree); |
---|
[7fee876] | 982 | if ((c == r->m_nfCharQ) && (strcmp(n_ParameterNames(r)[0], p->GFPar_name) == 0)) |
---|
[e9039a7] | 983 | return TRUE; |
---|
| 984 | } |
---|
| 985 | return FALSE; |
---|
| 986 | } |
---|