1 /* SYMMETRICA ff.c */
2 #include "def.h"
3 #include "macro.h"
4
5 #define MAXDEGREE 20
6 INT null_ip[MAXDEGREE];
7 INT eins_ip[MAXDEGREE];
8
9 #ifdef FFTRUE
10 /*
11 #define SYM_free(a) SYM_free_debug(a)
12 #define SYM_malloc(a) SYM_malloc_debug(a)
13 #define SYM_calloc(a,b) SYM_calloc_debug(a,b)
14 #define SYM_free(a)
15 */
16
17 #define UE_malloc(a) SYM_malloc(a)
18 #define UE_realloc(a,b) SYM_realloc(a,b)
19
20 static INT init_ff();
21 static INT Charakteristik=(INT)0;
22 static INT UE_Erw_Grad=(INT)0;
23 static INT *UE_Platz_Mult=NULL;
24
25 #define Mult_Tafel_Speicher XYZ_ABC
26 static INT ***Mult_Tafel_Speicher = NULL;
27 static INT *Mult_Tafel_Grad = NULL;
28 static INT *Mult_Tafel_Charakteristik = NULL;
29 static INT **UE_Platz_Mult_Speicher = NULL;
30 static INT Mult_Tafel_Counter = (INT)0;
31
32 static int globalno=0;
33 static INT **Mult_Tafel=NULL;
34 static FILE *Datei =NULL; /* UWH */
35
36
37 static INT *Faktor_eins = NULL; /* AK 190802 */
38 static INT Faktor_eins_size = 0; /* AK 190802 */
39 static INT *Faktor_zwei = NULL; /* AK 190802 */
40 static INT Faktor_zwei_size = 0; /* AK 190802 */
41
42
43 static INT getString();
44 static INT UE_add();
45 static INT UE_fZeige();
46 static INT UE_invers();
47 static INT UE_ist_gleich();
48 static INT UE_ist_eins();
49 static INT UE_ist_null();
50 static INT UE_kgv();
51 static INT UE_mult();
52 static INT UE_negativ();
53 /* static INT UE_sqrt(); */
54 static INT UE_scan();
55 static INT UE_hoch();
56 /* static INT UE_prim(); */
57 static INT liestracepol();
58 static INT UE_Random();
59 static INT UE_order();
60 static INT UE_Int_Aequivalent();
61 static INT UE_Platz();
62 static INT UE_Free();
63 static INT minimalErw();
64 static int spezHoch();
65 static INT spezMult();
66 static INT spezEinsGGT();
67 static INT testirrPolynom();
68 static INT reduzierpoly();
69
70 /*
71 about the datastructure used for finite field elements:
72
73 */
74 #define UE_IST_NULL(e) \
75 { INT i=**e; for (;i>0;i--) if ((*e)[i] != 0) return 0; return 1; }
76
77 #define UE_ADDG(a,b) (((a)+(b)) >= Charakteristik ?\
78 ((a)+(b))-Charakteristik: (a)+(b))
79
80 #define UE_MULTG(a,b) ((a) && (b) ? ((a)*(b)) % Charakteristik : 0 )
81
82 #define UE_FREE(a) do { SYM_FREE(*a); *a=NULL; } while(0)
83
ff_anfang()84 INT ff_anfang()
85 /* AK 011204 */
86 {
87 INT i;
88 for (i=0;i<MAXDEGREE;i++) eins_ip[i]=1;
89 for (i=0;i<MAXDEGREE;i++) null_ip[i]=0;
90 return OK;
91 }
92
93 /******************************************************************************/
94 /* Endliche Koerper : Grundkoerperarithmetik */
95 /* */
96 /* Verfasser : Ulrich Eidt */
97 /* Stand : 04.11.91 */
98 /******************************************************************************/
s_ff_ip(a)99 static INT * s_ff_ip(a) OP a;
100 /* AK 180194 */ /* select .. int pointer */
101 /* returns an INT pointer with vector of coefficients */
102 /* AK 130704 V3.0 */
103 {
104 return s_o_s(s_v_i(a,1)).ob_INTpointer;
105 }
106
c_ff_ip(a,b)107 INT c_ff_ip(a,b) OP a; INT *b;
108 {
109 OBJECTSELF c;
110 c.ob_INTpointer = b;
111 c_o_s(s_v_i(a,(INT)1) , c);
112 return OK;
113 }
114
s_ff_ii(a,i)115 INT s_ff_ii(a,i) OP a; INT i;
116 /* at point 0, the degee
117 at point 1,...,s_ff_di the values */
118 {
119 if (i > s_ff_di(a))
120 error("s_ff_ii: index too big");
121 return * (s_ff_ip(a)+i);
122 }
123
124
UE_addg(a,b)125 static INT UE_addg(a,b) INT a,b;
126 /* Summation : a,b sind die Summanden (Integerzahlen) */
127 {
128 if (!b)
129 return(a);
130 if (!a)
131 return(b);
132 if (a+b>=Charakteristik)
133 return(a+b-Charakteristik);
134 return(a+b);
135 }
136
UE_subg(a,b)137 static INT UE_subg (a,b) INT a,b;/* Subtraktion : a,b sind Integerzahlen */
138 {
139 if (!b)
140 return(a);
141 if (!a)
142 return(Charakteristik-b);
143 if (a>=b)
144 return(a-b);
145 return(Charakteristik+a-b);
146 }
147
UE_multg(a,b)148 static INT UE_multg(a,b) INT a,b;
149 /* Multiplikation : a,b sind Faktoren (Integerzahlen) */
150 {
151 if (a && b)
152 return((a*b) % Charakteristik);
153 return((INT)0);
154 }
155
156
UE_divg(a,b)157 static INT UE_divg(a,b) INT a,b;/* Division : a,b sind Integerzahlen */
158 /* UE */
159 {
160 INT j,i,s;
161 if (!b)
162 {
163 error("UE_divg:zero-division ");
164 return(ERROR);
165 }
166 if (!a || b==(INT)1)
167 return(a);
168 s = a;
169 j = b;
170 i = Charakteristik-2L;
171 while(i>(INT)0)
172 {
173 while(!i % 2L)
174 {
175 i /= 2L;
176 j =(j*j) % Charakteristik;
177 if (j==(INT)1)
178 return(s);
179 }
180 i--;
181 s = (s*j) % Charakteristik;
182 }
183 return(s);
184 }
185
186
187 /******************************************************************************/
188 /* Gaussalgorithmen : Algorithmen fuer Gleichungssystemloesung */
189 /* */
190 /* Verfasser : Ulrich Eidt */
191 /* Stand : 07.11.91 */
192 /******************************************************************************/
193
194 /******************************************************************************/
195 /* Funktion gausszerlegu fuehrt die Dreieckszerlegung PA = LR durch */
196 /* Uebergabeparameter : Mat : ist die Matrix */
197 /* n : Dimension der Matrix */
198 /* P : Platz fuer Permutationsvektor */
199 /* */
200 /* Rueckgabeparameter : 0 falls Matrix singulaer */
201 /* 1 falls Zerlegung erfolgreich durchgefuehrt */
202 /* */
203 /* Bemerkungen : - Die Eintraege der Matrix Mat sind Zeile fuer Zeile von oben*/
204 /* nach unten in Mat eingetragen. */
205 /* - Die Funktionen add,sub,mult,div werden verwendet. */
206 /* Diese stehen in EndlArithmet.c */
207 /******************************************************************************/
gausszerlegu(Mat,n,P)208 static INT gausszerlegu(Mat,n,P) INT **Mat; INT n; INT *P;
209 {
210 INT i,j,k=(INT)0,StellePermutation,Zwischenspeicher;
211 /*
212 { INT ii,jj; printf("(1)\n"); for (ii=0;ii<n;ii++)
213 { for (jj=0;jj<n;jj++) printf("%ld ",Mat[ii][jj]); printf("\n"); }}
214 */
215
216 for (k=(INT)0;k<n;k++)
217 {
218
219 /* Sollte ein Eintrag = 1 sein, dann sind wir optimal */
220 /* ansonsten nehmen wir den ersten Eintrag <> 0 */
221 StellePermutation = -1;
222 for (i=k;i<n;i++)
223 if (Mat[i][k] == 1)
224 {
225 StellePermutation = i;
226 i = n+1;
227 }
228 if (StellePermutation < 0)
229 for (i=k;i<n;i++)
230 if (Mat[i][k] > 0)
231 {
232 StellePermutation = i;
233 i = n+1;
234 }
235
236 /* Falls kein Eintrag <> 0 : Abbruch da Matrix singulaer */
237 if (StellePermutation < (INT)0)
238 {
239 /*
240 { INT ii,jj; printf("(2)\n"); for (ii=0;ii<n;ii++)
241 { for (jj=0;jj<n;jj++) printf("%ld ",Mat[ii][jj]); printf("\n"); }}
242 */
243
244 return((INT)0);
245 }
246
247 /* Permutation speichern */
248 P[k] = StellePermutation;
249
250 /* Vertauschung falls notwendig */
251 if (StellePermutation > k)
252 for (j=(INT)0;j<n;j++)
253 {
254 Zwischenspeicher = Mat[k][j];
255 Mat[k][j] = Mat[StellePermutation][j];
256 Mat[StellePermutation][j] = Zwischenspeicher;
257 }
258
259 /* Berechnung von L */
260 Zwischenspeicher = Mat[k][k];
261 if (Zwischenspeicher != (INT)1)
262 {
263 Zwischenspeicher = UE_divg((INT)1,Zwischenspeicher);
264 for (i=k+(INT)1;i<n;i++)
265 Mat[i][k] = UE_MULTG(Mat[i][k],Zwischenspeicher);
266 }
267
268 /* Spaltenweise Berechnung der Untermatrix */
269 for (j=k+(INT)1;j<n;j++)
270 {
271 Zwischenspeicher = Mat[k][j];
272 for (i=k+(INT)1;i<n;i++)
273 Mat[i][j] = UE_subg(Mat[i][j],UE_MULTG(Mat[i][k], Mat[k][j]));
274 }
275 }
276 if (!Mat[n-1][n-1])
277 {
278 return((INT)0);
279 }
280
281 return((INT)1);
282 }
283
284
285
286 /******************************************************************************/
287 /* Funktion gaussaufloes berechnet die Loesung des Gleichungssystems : */
288 /* LRx = Pb */
289 /* Uebergabeparameter : Mat : ist die Matrix mit den Informationen zu L und R*/
290 /* n : Dimension der Matrix */
291 /* b : rechte Seite des Permutationsvektors */
292 /* P : Permutationsvektor */
293 /* */
294 /* Bemerkungen : - Die Funktion ist ohne Rueckgabeparameter. */
295 /* - Der Vektor b enthaelt nach der Aktion das Ergebnis */
296 /* - Die Funktionen UE_addg,UE_subg,UE_multg,UE_divg werden verwendet. */
297 /******************************************************************************/
gaussaufloes(Mat,n,b,P)298 static INT gaussaufloes(Mat,n,b,P) INT **Mat, n, *b, *P;
299 {
300 INT i,k=0,Zwischenspeicher;
301
302 /* b := Pb */
303 for (k=(INT)0;k<n-(INT)1;k++)
304 if (k<P[k])
305 {
306 Zwischenspeicher = b[k];
307 b[k] = b[P[k]];
308 b[P[k]] = Zwischenspeicher;
309 }
310
311 /* b := L^-1b */
312 for (k=(INT)0;k<n-(INT)1;k++)
313 for (i=k+(INT)1;i<n;i++)
314 b[i] = UE_subg(b[i],UE_MULTG(Mat[i][k],b[k]));
315
316 /* b := R^-1b */
317 for (k=n-(INT)1;k>=(INT)0;k--)
318 {
319 b[k] = UE_divg(b[k],Mat[k][k]);
320 for (i=(INT)0;i<=k-(INT)1;i++)
321 b[i] = UE_subg(b[i],UE_MULTG(Mat[i][k],b[k]));
322 }
323 return OK;
324 }
325
326
327 /******************************************************************************/
328 /* Funktion reduzierpoly fuehrt die Reduktion eines Polynoms modulo eines */
329 /* anderen durch. Funktion nur fuer endliche Koerper verwendbar. */
330 /* */
331 /* Bemerkungen : - Funktion ohne Rueckgabeparameter. */
332 /* - Polynome werden in Potenzaufsteigender Reihenfolge */
333 /* sortiert, beginnend bei 0. ZB. Pol = x^2 + x + 3 wird */
334 /* uebergeben als : Pol[0] = 3, Pol[1] = 1, Pol[3] = 1. */
335 /* - ReduzierPolynom wird als normiert vorrausgesetzt, dh. in */
336 /* der Funktion wird der Koeffizient der hoechsten Potenz */
337 /* automatisch als 1 angenommen. */
338 /* - Polynom wird in der Funktion geaendert und enthaelt */
339 /* beim Abschluss der Funktion das reduzierte Polynom. */
340 /* - die Funktionen UE_multg,UE_addg,UE_subg werden verwendet. */
341 /* */
342 /* Autor : Ulrich Eidt */
343 /* Stand : 04.11.91 */
344 /******************************************************************************/
reduzierpoly(Polynom,Grad,ReduzierPolynom,GradReduzierPol)345 static INT reduzierpoly(Polynom,Grad,ReduzierPolynom,GradReduzierPol)
346
347 INT *Polynom; /* enthaelt das Polynom vor Reduktion */
348 INT Grad; /* Grad des Polynoms vorher */
349 INT *ReduzierPolynom; /* Polynom nach dem reduziert wird */
350 INT GradReduzierPol; /* Grad des Polynoms nach dem reduziert wird */
351
352 {
353 INT Polynomzeiger, i, Stelle, Faktor;
354
355 /* falls Grad < GradReduzierPol ohne Aenderung zurueck */
356 if (Grad < GradReduzierPol)
357 {
358 return OK;
359 }
360 Polynomzeiger = Grad;
361
362 /* Reduzieren, solange der Grad reduzierten Polynoms < Grad ReduzierPolynoms */
363 while (Polynomzeiger >= GradReduzierPol)
364 {
365 Faktor = Polynom[Polynomzeiger];
366
367 /* Reduzierung nur noetig, falls der Koeffizient <> 0 */
368 if (Faktor)
369 {
370 Polynom[Polynomzeiger] = (INT)0;
371 for (i=(INT)0;i<GradReduzierPol;i++)
372 {
373 Stelle = Polynomzeiger+i-GradReduzierPol;
374
375 /* Hier findet die Reduktion statt */
376 Polynom[Stelle] = UE_subg(Polynom[Stelle], UE_MULTG(Faktor,
377 ReduzierPolynom[i]));
378 }
379 }
380 Polynomzeiger--;
381 }
382 return OK;
383 }
384
385
ff_ende()386 INT ff_ende()
387 /* AK 170393 */
388 {
389 INT i;
390 if (Mult_Tafel_Grad != NULL)
391 {
392 SYM_free((char *) Mult_Tafel_Grad);
393 Mult_Tafel_Grad=NULL;
394 }
395
396 if (Mult_Tafel_Charakteristik != NULL)
397 {
398 SYM_free((char *) Mult_Tafel_Charakteristik);
399 Mult_Tafel_Charakteristik=NULL;
400 }
401
402 if (Mult_Tafel_Speicher != NULL)
403 {
404 for (i=0;i<Mult_Tafel_Counter; i++)
405 SYM_free((char*) Mult_Tafel_Speicher[i]);
406 SYM_free((char *) Mult_Tafel_Speicher);
407 Mult_Tafel_Speicher=NULL;
408 }
409
410 if (UE_Platz_Mult_Speicher != NULL)
411 {
412 for (i=0;i<Mult_Tafel_Counter; i++)
413 SYM_free((char*) UE_Platz_Mult_Speicher[i]);
414 SYM_free((char *) UE_Platz_Mult_Speicher);
415 UE_Platz_Mult_Speicher=NULL;
416 }
417
418 Mult_Tafel=NULL;
419 UE_Platz_Mult=NULL;
420
421 if (Faktor_eins != NULL) { SYM_free(Faktor_eins); Faktor_eins=NULL; }
422 Faktor_eins_size = 0;
423 if (Faktor_zwei != NULL) { SYM_free(Faktor_zwei); Faktor_zwei=NULL; }
424 Faktor_zwei_size = 0;
425 return OK;
426 }
427
insert_mt()428 static INT insert_mt() /* AK 070294 */
429 /* fuegt in globalen speicher ein */
430 {
431 Mult_Tafel_Counter++;
432 if (Mult_Tafel_Counter > 1) {
433 Mult_Tafel_Speicher = (INT ***) SYM_realloc(Mult_Tafel_Speicher,
434 sizeof(INT**)* Mult_Tafel_Counter);
435 Mult_Tafel_Grad = (INT *) SYM_realloc(Mult_Tafel_Grad,
436 sizeof(INT)* Mult_Tafel_Counter);
437 Mult_Tafel_Charakteristik = (INT *) SYM_realloc(Mult_Tafel_Charakteristik,
438 sizeof(INT)* Mult_Tafel_Counter);
439 UE_Platz_Mult_Speicher = (INT **) SYM_realloc(UE_Platz_Mult_Speicher,
440 sizeof(INT*)* Mult_Tafel_Counter);
441 }
442 else {
443 Mult_Tafel_Speicher = (INT ***) SYM_malloc(
444 sizeof(INT**)* Mult_Tafel_Counter);
445 Mult_Tafel_Grad = (INT *) SYM_malloc(
446 sizeof(INT)* Mult_Tafel_Counter);
447 Mult_Tafel_Charakteristik = (INT *) SYM_malloc(
448 sizeof(INT)* Mult_Tafel_Counter);
449 UE_Platz_Mult_Speicher = (INT **) SYM_malloc(
450 sizeof(INT*)* Mult_Tafel_Counter);
451 }
452 Mult_Tafel_Speicher[Mult_Tafel_Counter-1] = Mult_Tafel;
453 Mult_Tafel_Grad[Mult_Tafel_Counter-1] = UE_Erw_Grad;
454 Mult_Tafel_Charakteristik[Mult_Tafel_Counter-1] = Charakteristik;
455 UE_Platz_Mult_Speicher[Mult_Tafel_Counter-1] = UE_Platz_Mult;
456 return OK;
457 }
458
459 /******************************************************************************/
460 /* Funktion erzmulttafel berechnet die Multiplikationstafel fuer die */
461 /* Normalbasis. */
462 /* */
463 /* Uebergabeparameter : */
464 /* - Erweiterungsgrad : Gibt den gewuenschten Erweiterungsgrad an */
465 /* - zweitAufruf : 1=Aufruf aus erzeugePol, 0 normaler Aufruf */
466 /* -1=Aufruf aus erzeugePol mit Tracepolynombergabe */
467 /* - Tracepolynom : Tracepolynom, falls bueergeben */
468 /* */
469 /* Rueckgabeparameter : 0 falls Tafel nicht erzeugt werden konnte. */
470 /* 1 sonst. */
471 /* */
472 /* Bemerkungen: */
473 /* - Funktionen, die benutzt werden (also eingebunden sein */
474 /* muessen) : */
475 /* liestracepol : aufgerufen von erzmulttafel() */
476 /* zu finden in LiesTracePol.c */
477 /* reduzierpoly : aufgerufen von erzmulttafel() */
478 /* zu finden in ReduzierPoly.c */
479 /* gausszerlegu : aufgerufen in erzmulttafel() */
480 /* zu finden in GaussAlgorit.c */
481 /* gaussaufloes : aufgerufen in erzmulttafel() */
482 /* zu finden in GaussAlgorit.c */
483 /* UE_addg,UE_subg,UE_multg,UE_divg : aufgerufen von reduzierpoly(), */
484 /* gausszerlegu() */
485 /* zu finden in EndlArithmet.c */
486 /* */
487 /* Zur Implementierung: */
488 /* Zunaechst wird das Tracecompatible Polynom eingelesen, und falls dies */
489 /* erfolgreich war die noetigen Speicherbelegungen durchgefuehrt. */
490 /* */
491 /* Dann wird die Normalbasis in der Polynomialen Basis ermittelt und sowohl */
492 /* in Tafel als auch in Gaussmatrix abgespeichert. Dafuer wird immer in */
493 /* Grosspolynom das letzte Basiselement^Erweiterungsgrad (= Frobeniushomom.)*/
494 /* eingelesen und nach Tracepolynom reduziert. */
495 /* */
496 /* Mit Gausszerlegu() wird die Basistransformation (Gleichungssystem) */
497 /* Polynomialbasis -> Normalbasis ermoeglicht. */
498 /* */
499 /* Diese Transformation wird auf die gewuenschten x - Potenzen in Polynomial-*/
500 /* basis angewendet, die man erhaelt, indem die in Tafel abgespeicherten */
501 /* Polynome mit x multipliziert, und dann reduziert. */
502 /* */
503 /* Autoer : Ulrich Eidt */
504 /* Stand : 05.11.91 */
505 /******************************************************************************/
506
507 #define FASTCHECKMULTTAFEL(grad) \
508 /* AK 221104 V3.0 */ \
509 do { \
510 INT i; \
511 for (i=0, Mult_Tafel =NULL ;i<Mult_Tafel_Counter; i++) \
512 if ((grad == Mult_Tafel_Grad[i]) && \
513 (Charakteristik == Mult_Tafel_Charakteristik[i])) \
514 { \
515 Mult_Tafel = Mult_Tafel_Speicher [i]; \
516 UE_Erw_Grad = grad; \
517 } \
518 } while(0)
519
erzmulttafel(Erweiterungsgrad,zweitAufruf,para_Tracepolynom)520 static INT erzmulttafel(Erweiterungsgrad,zweitAufruf,para_Tracepolynom)
521 INT Erweiterungsgrad;
522 INT zweitAufruf; /* UWH */
523 /* 1 heisst ja, 0 heisst nein, -1 heisst
524 ja mit bergabe von Tracepolynom */
525 INT *para_Tracepolynom; /* UWH */
526 /* Tracecompatibles Polynom */
527 {
528 INT *Gaussmatrix; /* Matrix fuer Basistransformation */
529 INT **Gau; /* Zeigersystem fuer Gaussmatrix */
530 INT *Grosspolynom; /* Platz fuer Polynome mit Grad > Erweiterungsgrad */
531 INT Grosspolzeiger;/* Hilfszeiger fuer Grosspolynom */
532 INT Gradgrosspol; /* Gibt den Grad von Grosspolynom an */
533 INT *Tracepolynom; /* Tracecompatibles Polynom */
534 INT *Permutation; /* Permutationsvektor bei Gleichungssystemloesung */
535 INT i,j; /* Laufvariable */
536 INT *ax;
537 int k;
538
539 #ifdef UNDEF
540 Mult_Tafel=NULL;
541 /* schaue ob schon von frueher da AK 070294 */
542 for (i=0;i<Mult_Tafel_Counter; i++)
543 {
544 if ((Erweiterungsgrad == Mult_Tafel_Grad[i]) &&
545 (Charakteristik == Mult_Tafel_Charakteristik[i]))
546 {
547 Mult_Tafel = Mult_Tafel_Speicher [i];
548 UE_Erw_Grad = Erweiterungsgrad;
549 return OK;
550 }
551 }
552 #endif
553 FASTCHECKMULTTAFEL(Erweiterungsgrad);
554 if (Mult_Tafel != NULL) return OK;
555
556 /* also noch nicht frueher berechnet */
557
558 if (UE_Erw_Grad && !zweitAufruf) /* UWH */
559 Erweiterungsgrad = UE_kgv(UE_Erw_Grad,Erweiterungsgrad);
560
561 /* Tracecompatibles Polynom wird eingelesen,
562 falls nicht moeglich Zurueck */
563 /* falls moeglich Speicher freimachen */
564
565 if (zweitAufruf>=0) /* UWH */
566 { /* UWH */
567 Tracepolynom = (INT *) SYM_calloc(Erweiterungsgrad,sizeof(INT));
568 if (liestracepol(Erweiterungsgrad,Tracepolynom,zweitAufruf) != OK) /* UWH */
569 {
570 SYM_free((char *) Tracepolynom);
571 return error("ff.c: internal error FF-41");
572 /* printf("Tracecompatibles Polynom nicht beschaffbar!\n"); */
573 } /* UWH */
574 }
575 else
576 Tracepolynom = para_Tracepolynom; /* AK 040294 */
577
578 /* Bestehende Tafeln freimachen, falls nicht Aufruf aus erzeugePol */
579 for (i=0;i<Mult_Tafel_Counter; i++)
580 {
581 if (Erweiterungsgrad == Mult_Tafel_Grad[i] &&
582 Charakteristik == Mult_Tafel_Charakteristik[i])
583 {
584 Mult_Tafel = Mult_Tafel_Speicher [i];
585 UE_Erw_Grad = Erweiterungsgrad;
586 if (zweitAufruf>=0) /* UWH */
587 SYM_free((char *) Tracepolynom);
588 return OK;
589 }
590 }
591 UE_Platz_Mult = (INT *) UE_malloc(Erweiterungsgrad
592 *Erweiterungsgrad*
593 sizeof(INT));
594
595 /* Abspeichern der jeweiligen Zeilenanfaenge der Matrix,
596 um Multiplikationen */
597 /* bei der Addressierung zu vermeiden */
598 Mult_Tafel = (INT **) UE_malloc(Erweiterungsgrad*sizeof(INT*));
599
600 k=(INT)0;
601 for (i=(INT)0;i<Erweiterungsgrad;i++)
602 {
603 Mult_Tafel[i] = & UE_Platz_Mult[k];
604 k += Erweiterungsgrad;
605 }
606
607
608 if (Erweiterungsgrad == (INT)1)
609 {
610 if (zweitAufruf>=0) SYM_free((char *) Tracepolynom);
611 Mult_Tafel[0][0] = (INT)1;
612 UE_Erw_Grad = (INT)1;
613 insert_mt();
614 return(OK);
615 }
616
617 Grosspolynom = (INT *) SYM_calloc(Erweiterungsgrad*Charakteristik, sizeof(INT));
618 Gaussmatrix = (INT *) UE_malloc(Erweiterungsgrad*Erweiterungsgrad* sizeof(INT));
619 Permutation = (INT *) UE_malloc(Erweiterungsgrad*sizeof(INT));
620
621 /* Abspeichern der jeweiligen Zeilenanfaenge der Matrix,
622 um Multiplikationen */
623 /* bei der Addressierung zu vermeiden */
624 Gau = (INT **) UE_malloc(Erweiterungsgrad*sizeof(INT*));
625 k=(INT)0;
626 ax = Gaussmatrix;
627 for (i=(INT)0;i<Erweiterungsgrad;i++)
628 {
629 Gau[i] = ((INT *)Gaussmatrix) + (int)k;
630 ax = Gaussmatrix;
631 for (j=0;j<k;j++)
632 ax = ax++;
633 k += (int)Erweiterungsgrad;
634 }
635
636 /* Initialisierung der Gaussmatrix und Zwischenspeichern der Potenzen */
637 for (i=(INT)0;i<Erweiterungsgrad;i++)
638 {
639 (Gau[i])[0] = (INT)0;
640 Mult_Tafel[0][i] = (INT)0;
641 }
642 Gau[1][0] = (INT)1;
643 Mult_Tafel[0][1] = (INT)1;
644 for (i=(INT)1;i<Erweiterungsgrad;i++)
645 {
646 for (j=0;j<Erweiterungsgrad;j++) Grosspolynom[j] = 0;
647 Grosspolzeiger = (INT)0;
648 for (j=0;j<Erweiterungsgrad;j++)
649 {
650
651 /* Grosspolynom = letztes Polynom ^ Charakteristik (Frobenius)*/
652 if (Gau[j][i-1])
653 {
654 Grosspolynom[Grosspolzeiger] = Gau[j][i-1];
655 Gradgrosspol = Grosspolzeiger;
656 }
657 Grosspolzeiger += Charakteristik;
658 }
659
660 /* Grosspolynom wird nach Tracepolynom reduziert und abgespeichert */
661 reduzierpoly(Grosspolynom,Gradgrosspol,Tracepolynom, Erweiterungsgrad);
662
663 for (j=0;j<Erweiterungsgrad;j++)
664 {
665 Gau[j][i] = Grosspolynom[j];
666 Mult_Tafel[i][j] = Grosspolynom[j];
667 }
668 }
669
670 /* Gaussdreieckszerlegung */
671 if(!gausszerlegu(Gau,Erweiterungsgrad,Permutation))
672 {
673 error("ff.c: internal error FF6");
674 SYM_free((char *) Gaussmatrix);
675 SYM_free((char *) Grosspolynom);
676 if (zweitAufruf>=0) /* UWH */
677 SYM_free((char *) Tracepolynom);
678 SYM_free((char *) Permutation);
679 SYM_free((char *) Gau);
680 error("internal error FF200");
681 return ERROR;
682 }
683
684 /* Berechnung der Tafeleintraege von x*x^(p^i) in der Normalbasis */
685 for (i=(INT)0;i<Erweiterungsgrad;i++)
686 {
687
688 /* Grosspolynom wird belegt mit x*x^(p^i) in Polynomialbasis */
689 Grosspolynom[0] = (INT)0;
690 for (j=(INT)0;j<Erweiterungsgrad;j++)
691 Grosspolynom[j+1] = Mult_Tafel[i][j];
692
693 /* Grosspolynom wird reduziert und der Basiswechsel durchgefuehrt */
694 reduzierpoly(Grosspolynom,Erweiterungsgrad,Tracepolynom, Erweiterungsgrad);
695 gaussaufloes(Gau,Erweiterungsgrad,Grosspolynom, Permutation);
696
697 /* Abschliessend wird das Ergebnis gespeichert */
698 for (j=(INT)0;j<Erweiterungsgrad;j++)
699 Mult_Tafel[i][j] = Grosspolynom[j];
700 }
701
702 /* Speicher wieder freigeben */
703 SYM_free((char *) Gaussmatrix);
704 SYM_free((char *) Grosspolynom);
705 if (zweitAufruf>=0) /* UWH */
706 SYM_free((char *) Tracepolynom);
707 SYM_free((char *) Permutation);
708 SYM_free((char *) Gau);
709 UE_Erw_Grad = Erweiterungsgrad;
710
711 insert_mt();
712 return OK;
713 }
714
715
716
717 /******************************************************************************/
718 /* Funktion UE_kgv berechnet das kleinste gemeinsame Vielfache von zwei */
719 /* Integerzahlen. */
720 /******************************************************************************/
UE_kgv(a,b)721 static INT UE_kgv(a,b) INT a,b;
722 {
723 INT c,d;
724 if (a==1) return b;
725 if (b==1) return a;
726 c = a;
727 d = b;
728 while(c && d)
729 {
730 c = c % d;
731 if(c)
732 d = d % c;
733 }
734 if(c)
735 return(a*b/c);
736 else
737 return(a*b/d);
738 }
739
740
741
742 #ifdef UNDEF
743 /******************************************************************************/
744 /* Funktion UE_sqrt berechnet die abgerundete integer-Wurzel einer Integerzahl*/
745 /******************************************************************************/
UE_sqrt(x)746 static INT UE_sqrt(x) INT x;
747 {
748 INT i;
749 if (x==(INT)0)
750 return((INT)0);
751 for (i=(INT)1;i<x;i++)
752 if (i*i > x)
753 return(i-(INT)1);
754 return((INT)1);
755 }
756
757 #endif
758
759 /******************************************************************************/
760 /* Funktion UE_power berechnet die y-te Potenz von x */
761 /******************************************************************************/
UE_power(x,y)762 static INT UE_power(x,y) INT x,y;
763 {
764 INT i, s = (INT)1;
765 for (i=(INT)0;i<y;i++)
766 s *= x;
767 return(s);
768 }
769
770
771
772 #ifdef UNDEF
773 /******************************************************************************/
774 /* Funktion UE_prim prueft, ob p eine Primzahl ist. */
775 /* Rueckgabewert: 1, falls p Primzahl, 0 sonst. */
776 /******************************************************************************/
UE_prim(p)777 static INT UE_prim(p)
778 INT p;
779 {
780 INT i, s;
781
782 s = UE_sqrt(p);
783 if (p < 2L)
784 return((INT)0);
785 if (p > 2 && ((p % 2L) == (INT)0))
786 return((INT)0);
787 else
788 {
789 for (i=3L;i<=s;i+=2L)
790 {
791 if ((p % i) == (INT)0)
792 return((INT)0);
793 }
794 }
795 return((INT)1);
796 }
797
798 #endif
799
800 /******************************************************************************/
801 /* FUNKTIONEN FUER ENDLICHE KOERPER */
802 /* Die folgenden Funktionen stellen eine Arithmetik fuer endliche Koerper in */
803 /* Normalbasenrepraesentation dar. Ein Koerperelement wird wie folgt */
804 /* abgespeichert: */
805 /* e[0] enthaelt den Erweiterungsgrad, die weiteren <e[0]> */
806 /* Stellen die Eintraege des es bezueglich der entsprechenden */
807 /* Normalbasis. e[0] = 0 ist gleichbedeutend mit 'nicht definiert'. */
808 /* */
809 /* Verfasser : Ulrich Eidt */
810 /* Stand : 04.11.91 */
811 /******************************************************************************/
812
813 /******************************************************************************/
814 /* Funktion minimalErw stellt den Koerper mit dem kleinsten Erweiterungsgrad */
815 /* fest, in dem ein e enthalten ist. Ist dieser kleiner als e[0] */
816 /* so wird die Speicherung des ees auf den kleinsten moeglichen Erwei- */
817 /* terungsgrad angepasst. */
818 /* Ein e ist genau dann aus einem Unterkoerper, wenn fuer einen Teiler */
819 /* m des Erweiterungsgrades sich die Eintraege immer nach m Eintraegen wieder-*/
820 /* holen. */
821 /******************************************************************************/
minimalErw(e)822 static INT minimalErw(e) INT **e;
823 {
824 INT i,j,maximum=(*e)[0]/2L,Grad=(*e)[0],minGrad=(INT)0;
825 INT erfolgreich;
826 /* falls nicht definiert keine Aenderungen */
827 if ((*e)[0] == 0) return OK;
828
829 /* Teiler suchen nur bis zum maximalen Teiler */
830 while(minGrad<=maximum)
831 {
832 minGrad++;
833 /* Nur Teiler muessen ueberprueft werden */
834 if (!(Grad % minGrad))
835 {
836 erfolgreich = 1;
837 for (i=minGrad;i<Grad;i+=minGrad)
838 for (j=(INT)1;j<=minGrad;j++)
839 if ((*e)[j] != (*e)[i+j])
840 {
841 /* Keine Wiederholung -> minGrad nicht der minimale Erweiterungsgrad */
842 erfolgreich = 0;
843 j = minGrad+(INT)1;
844 i = Grad;
845 }
846 if (erfolgreich) { **e = minGrad; goto endeme; }
847 }
848 }
849 endeme:
850 return OK;
851 }
852
s_ff_ci(a)853 INT s_ff_ci(a) OP a;
854 /* AK 080306 V3.0 */
855 /* select finite field characteristik as INT */
856 {
857 return S_V_II(a,0);
858 }
859
s_ff_c(a)860 OP s_ff_c(a) OP a;
861 /* AK 080306 V3.0 */
862 /* select finite field characteristik */
863 {
864 return S_V_I(a,0);
865 }
866
s_ff_di(a)867 INT s_ff_di(a) OP a;
868 /* select finite field degree as INT */
869 /* AK 130704 V3.0 */
870 {
871 return S_FF_II(a,0);
872 }
873
874
875
876
copy_ff(a,b)877 INT copy_ff(a,b) OP a,b;
878 /* AK 100393 */
879 /* AK 221104 V3.0 */
880 {
881 INT erg = OK;
882 {
883 OBJECTSELF ma,mb;
884 INT al,i;
885 init_ff(b);
886 COPY(S_FF_C(a),S_FF_C(b)); /*characteristic*/
887 COPY(S_FF_ME(a),S_FF_ME(b)); /* minimal extension ??*/
888 ma = S_O_S(S_V_I(a,1));
889 al = *(S_O_S(S_V_I(a,1)).ob_INTpointer);
890 UE_Erw_Grad=al;
891 mb.ob_INTpointer = (INT *) UE_malloc((al+1) * sizeof(INT));
892 for (i=0;i<=al;i++)
893 *(mb.ob_INTpointer+i) = *(ma.ob_INTpointer+i);
894 C_O_S(S_V_I(b,1),mb);
895 }
896 ENDR("copy_ff");
897 }
898
scan_ff(a)899 INT scan_ff(a) OP a;
900 {
901 OP b;
902 INT erg = OK;
903 b = callocobject();
904 printeingabe("Enter the Characteristik of the finite field");
905 erg += scan(INTEGER,b);
906 Charakteristik = S_I_I(b);
907 erg += init_ff(a); /* AK 160594 */
908 erg += copy(b,S_FF_C(a));
909 erg += UE_scan(& S_FF_IP(a));
910 erg += freeall(b);
911 ENDR("scan_ff");
912 }
913
914 /******************************************************************************/
915 /* Funktion UE_scan uebernimmt das Einlesen der Koerperelemente */
916 /* */
917 /* Struktur : 0-te Stelle enthaelt den Grad der Koerpererweiterung */
918 /* Die darauffolgenden <Grad> Stellen enthalten das e */
919 /******************************************************************************/
UE_scan(Koerperzeiger)920 static INT UE_scan(Koerperzeiger) INT **Koerperzeiger;
921 {
922 INT i,j=(INT)0,ZeichenZeiger = (INT)1,*Koerperelement;
923 char *Zeichen;
924 Koerperelement = *Koerperzeiger;
925 Zeichen = (char *) SYM_calloc(500,sizeof(char));
926 printeingabe("input of a finite field element");
927 printeingabe("degree of extension");
928 scanf( "%" SCNINT ,&i);
929 SYM_free((char *) Koerperelement);
930 Koerperelement = (INT *) UE_malloc((i+1)*sizeof(INT));
931 *Koerperzeiger = Koerperelement;
932 for (j=(INT)0;j<=i;j++)
933 Koerperelement[j] = (INT)0;
934 fprintf(stderr, "input of %" PRIINT " entries, separated by comma" ,i);
935 fprintf(stderr,"\nmissing entries are 0\n");
936 scanf("%s",Zeichen);
937 j = (INT)1;
938 ZeichenZeiger = (INT)0;
939 while (j<=i)
940 {
941 /* 44 = 'Komma' */
942 while (Zeichen[ZeichenZeiger]!=44 && Zeichen[ZeichenZeiger]!=0)
943 {
944 Koerperelement[j] = Koerperelement[j] * 10 +
945 Zeichen[ZeichenZeiger] - 48;
946 ZeichenZeiger++;
947 }
948 ZeichenZeiger++;
949 j++;
950 }
951 for (j=(INT)1;j<=i;j++)
952 Koerperelement[j] %= Charakteristik;
953 Koerperelement[0] = i;
954 UE_Erw_Grad = i;
955 /* minimalErw(Koerperzeiger); */
956 SYM_free(Zeichen); /* AK 051093 */
957 return OK;
958 }
959
960
961
962 /******************************************************************************/
963 /* Funktion UE_Platz stellt ein undefiniertes Koerperelement bereit. */
964 /******************************************************************************/
UE_Platz(Koerperzeiger)965 static INT UE_Platz(Koerperzeiger) INT **Koerperzeiger;
966 {
967 if (UE_Erw_Grad < 0)
968 {
969 error("ff.c: internal error FF331");
970 }
971 *Koerperzeiger = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
972 (*Koerperzeiger)[0] = (INT)0;
973 return OK;
974 }
975
UE_Free(a)976 static INT UE_Free(a) INT **a; /* AK 060294 */
977 {
978 SYM_free(*a);
979 *a = NULL;
980 return OK;
981 }
982
983
984 #ifdef UNDEF
985 /******************************************************************************/
986 /* Funktion UE_Zeige gibt ein Koerperelement auf dem Bildschirm aus. */
987 /******************************************************************************/
UE_Zeige(Koerperzeiger)988 static INT UE_Zeige(Koerperzeiger) INT **Koerperzeiger;
989 {
990 return UE_fZeige(stdout,Koerperzeiger);
991 }
992 #endif
993
994 /******************************************************************************/
995 /* Funktion UE_fZeige gibt ein Koerperelement auf f aus. */
996 /******************************************************************************/
UE_fZeige(f,Koerperzeiger)997 static INT UE_fZeige(f,Koerperzeiger) INT **Koerperzeiger; FILE *f;
998 /* AK 201204 V3.0 */
999 {
1000 INT i,*Koerperelement;
1001 if ((*Koerperzeiger)[0] == (INT)0)
1002 {
1003 return error("ff.c: internal error FF1");
1004 }
1005 /* minimalErw(Koerperzeiger); */
1006 Koerperelement = *Koerperzeiger;
1007 for (i=(INT)1;i<Koerperelement[0];i++)
1008 {
1009 fprintf(f, "%" PRIINT "," ,Koerperelement[i]);
1010 if (f == stdout) {
1011 zeilenposition += (intlog_int(Koerperelement[i])+1);
1012 }
1013 }
1014 fprintf(f, "%" PRIINT ,Koerperelement[Koerperelement[0]]);
1015 if (f == stdout) {
1016 zeilenposition += intlog_int(Koerperelement[Koerperelement[0]]);
1017 }
1018
1019 return OK;
1020 }
1021
1022 #endif /* FFTRUE */
1023
comp_ff(a,b)1024 INT comp_ff(a,b) OP a,b;
1025 /* AK 280704 V3.0 */
1026 {
1027 INT erg = OK;
1028 CTO(FF,"comp_ff(1)",a);
1029 CTO(FF,"comp_ff(2)",b);
1030 SYMCHECK (S_FF_CI(a) != S_FF_CI(b), "comp_ff:different characteristic");
1031 {
1032 #ifdef FFTRUE
1033 INT res,res2;
1034
1035 if (S_FF_DI(a) == S_FF_DI(b)) {
1036 INT i;
1037 for (i=1;i<=S_FF_DI(a);i++)
1038 if (S_FF_II(a,i) != S_FF_II(b,i)) {
1039 res = S_FF_II(a,i)-S_FF_II(b,i);
1040 goto re;
1041 }
1042 res=0;
1043 }
1044 else if (S_FF_DI(a)==1) /* AK 180607 */
1045 {
1046 INT i;
1047 for (i=1;i<=S_FF_DI(b);i++)
1048 if (S_FF_II(a,1) != S_FF_II(b,i)) {
1049 res = S_FF_II(a,1)-S_FF_II(b,i);
1050 goto re;
1051 }
1052 res=0;
1053 }
1054 else if (S_FF_DI(b)==1) /* AK 180607 */
1055 {
1056 INT i;
1057 for (i=1;i<=S_FF_DI(a);i++)
1058 if (S_FF_II(a,i) != S_FF_II(b,1)) {
1059 res = S_FF_II(a,i)-S_FF_II(b,1);
1060 goto re;
1061 }
1062 res=0;
1063 }
1064 else /* if the expansion degree different */
1065 res= UE_ist_gleich(& S_FF_IP(a), & S_FF_IP(b));
1066 re:
1067 return res;
1068 #endif /* FFTRUE */
1069 }
1070 ENDR("comp_ff");
1071 }
1072
addinvers_apply_ff(a)1073 INT addinvers_apply_ff(a) OP a;
1074 /* AK 160393 */
1075 /* AK 280704 V3.0 */
1076 {
1077 INT erg = OK;
1078 CTO(FF,"addinvers_apply_ff(1)",a);
1079 {
1080 #ifdef FFTRUE
1081 erg += UE_negativ(& S_FF_IP(a), & S_FF_IP(a));
1082 #endif
1083 }
1084 ENDR("addinvers_apply_ff");
1085 }
1086
invers_apply_ff(a)1087 INT invers_apply_ff(a) OP a;
1088 /* AK 190707 V3.0 */
1089 {
1090 INT erg = OK;
1091 CTO(FF,"invers_apply_ff(1)",a);
1092 {
1093 #ifdef FFTRUE
1094 erg += UE_invers(& S_FF_IP(a), & S_FF_IP(a));
1095 #endif
1096 }
1097 ENDR("invers_apply_ff");
1098 }
1099
1100
null_ff_given_q(q,b)1101 INT null_ff_given_q(q,b) OP b; OP q;
1102 /* builds the zero element in the finite field with q elements */
1103 /* AK 020304 */
1104 /* AK 210704 V3.0 */
1105 {
1106 INT erg = OK;
1107 CTO(INTEGER,"null_ff_given_q(1)",q);
1108 SYMCHECK(S_I_I(q) < 2,"null_ff_given_q:q<2");
1109 {
1110 #ifdef FFTRUE
1111 OP v;
1112 INT i,*ip;
1113 v = CALLOCOBJECT();
1114 erg += factorize_integer(q,v);
1115 if (S_V_II(v,0)!=S_V_II(v,S_V_LI(v)-1))
1116 {
1117 erg += error("null_ff_given_q:q no prime power");
1118 FREEALL(v);
1119 goto endr_ende;
1120 }
1121 Charakteristik=S_V_II(v,0);
1122 UE_Erw_Grad=S_V_LI(v);
1123 erg += init_ff(b); ip = S_FF_IP(b);
1124 for (i=0;i<UE_Erw_Grad;i++) ip[i+1]=0;
1125 ip[0]=UE_Erw_Grad;
1126 M_I_I(Charakteristik,S_FF_C(b));
1127 erg += erzmulttafel(UE_Erw_Grad,(INT)0,NULL); /* UWH */
1128 FREEALL(v);
1129 #endif
1130 }
1131 ENDR("null_ff_given_q");
1132 }
1133
eins_ff_given_q(q,b)1134 INT eins_ff_given_q(q,b) OP b; OP q;
1135 /* builds the unit element in the finite field with q elements */
1136 /* AK 020304 */
1137 /* AK 210704 V3.0 */
1138 {
1139 INT erg = OK;
1140 CTO(INTEGER,"eins_ff_given_q(1)",q);
1141 SYMCHECK(S_I_I(q) < 2,"eins_ff_given_q:q<2");
1142 {
1143 #ifdef FFTRUE
1144 OP v;
1145 INT i,*ip;
1146 v = CALLOCOBJECT();
1147 erg += factorize_integer(q,v);
1148 if (S_V_II(v,0)!=S_V_II(v,S_V_LI(v)-1))
1149 {
1150 erg += error("eins_ff_given_q:q no prime power");
1151 FREEALL(v);
1152 goto endr_ende;
1153 }
1154 Charakteristik=S_V_II(v,0);
1155 UE_Erw_Grad=S_V_LI(v);
1156 erg += init_ff(b); ip = S_FF_IP(b);
1157 for (i=0;i<UE_Erw_Grad;i++) ip[i+1]=1;
1158 ip[0]=UE_Erw_Grad;
1159 M_I_I(Charakteristik,S_FF_C(b));
1160 erg += erzmulttafel(UE_Erw_Grad,(INT)0,NULL); /* UWH */
1161 FREEALL(v);
1162 #endif
1163 }
1164 ENDR("eins_ff_given_q");
1165 }
1166
1167
random_ff_given_q(q,b)1168 INT random_ff_given_q(q,b) OP b; OP q;
1169 /* AK 020304 */
1170 /* random element with given field size q */
1171 /* AK 210704 V3.0 */ /* AK 211106 V3.1 */
1172 {
1173 INT erg = OK;
1174 CTO(INTEGER,"random_ff_given_q(1)",q);
1175 SYMCHECK(prime_power_p(q) ==FALSE,"random_ff_given_q:q no prime power");
1176 {
1177 #ifdef FFTRUE
1178 OP v;
1179 v = CALLOCOBJECT();
1180 erg += factorize_integer(q,v);
1181 Charakteristik=S_V_II(v,0);
1182 UE_Erw_Grad=S_V_LI(v);
1183 FREEALL(v);
1184 erg += random_ff(b);
1185 #endif
1186 }
1187 CTO(FF,"random_ff_given_q(2e)",b);
1188 ENDR("random_ff_given_q");
1189 }
1190
random_ff(b)1191 INT random_ff(b) OP b;
1192 /* AK 170393 */
1193 /* AK 210704 V3.0 */
1194 {
1195 INT erg = OK;
1196 {
1197 #ifdef FFTRUE
1198 if (Charakteristik == (INT)0) /* not yet set */
1199 Charakteristik = (INT)5;
1200 if( UE_Erw_Grad==(INT)0)
1201 UE_Erw_Grad=(INT)9;
1202 erg += init_ff(b);
1203 erg += UE_Random( & S_FF_IP(b));
1204 M_I_I(Charakteristik,S_FF_C(b));
1205 erg += erzmulttafel(UE_Erw_Grad,(INT)0,NULL); /* UWH */
1206 SYMCHECK (S_FF_II(b,1) > Charakteristik, "random_ff:internal error 070295");
1207 SYMCHECK (S_FF_II(b,1) < 0, "random_ff:internal error 170304");
1208 #endif
1209 }
1210 ENDR("random_ff");
1211 }
1212
random_char_ff(a,b)1213 INT random_char_ff(a,b) OP a,b;
1214 /* AK 220294 */
1215 /* AK 280704 V3.0 */
1216 {
1217 INT erg = OK;
1218 CTO(INTEGER,"random_char_ff(1)",a);
1219 SYMCHECK(not primep(a),"random_char_ff: no prime");
1220 {
1221 #ifdef FFTRUE
1222 Charakteristik = S_I_I(a);
1223 return random_ff(b);
1224 #endif
1225 }
1226 ENDR("random_char_ff");
1227 }
1228
1229
addinvers_ff(a,b)1230 INT addinvers_ff(a,b) OP a,b;
1231 /* AK 280704 V3.0 */
1232 {
1233 INT erg = OK;
1234 CTO(FF,"addinvers_ff(1)",a);
1235 {
1236 #ifdef FFTRUE
1237 Charakteristik = S_FF_CI(a);
1238 erg += init_ff(b);
1239 erg += UE_negativ(& S_FF_IP(a), & S_FF_IP(b));
1240 erg += m_i_i(Charakteristik,S_FF_C(b));
1241 SYMCHECK (S_FF_II(b,1) > Charakteristik, "addinvers_ff:internal error 070295");
1242 SYMCHECK (S_FF_II(b,1) < 0, "addinvers_ff:internal error 170304");
1243 #endif
1244 }
1245 ENDR("addinvers_ff");
1246 }
1247
invers_ff(a,b)1248 INT invers_ff(a,b) OP a,b;
1249 /* AK 280704 V3.0 */
1250 {
1251 INT erg = OK;
1252 CTO(FF,"invers_ff(1)",a);
1253 {
1254 #ifdef FFTRUE
1255 Charakteristik = S_FF_CI(a);
1256 erg += init_ff(b);
1257 erg += UE_invers(& S_FF_IP(a), & S_FF_IP(b));
1258 erg += m_i_i(Charakteristik,S_FF_C(b));
1259 SYMCHECK (S_FF_II(b,1) > Charakteristik, "invers_ff:internal error 070295");
1260 SYMCHECK (S_FF_II(b,1) < 0, "invers_ff:internal error 170304");
1261 #endif
1262 }
1263 ENDR("invers_ff");
1264 }
1265
1266
mult_ff_integer(a,b,c)1267 INT mult_ff_integer(a,b,c) OP a,b,c;
1268 /* AK 070802 */
1269 /* AK 280704 V3.0 */
1270 {
1271 INT erg = OK;
1272 CTO(FF,"mult_ff_integer(1)",a);
1273 CTO(INTEGER,"mult_ff_integer(2)",b);
1274 CTO(EMPTY,"mult_ff_integer(3)",c);
1275 {
1276 #ifdef FFTRUE
1277 OP d;
1278 d = CALLOCOBJECT();
1279 COPY_INTEGER(b,d);
1280 cast_apply_ff(d);
1281 erg += mult_ff_ff(a,d,c);
1282 FREEALL(d);
1283 #endif
1284 }
1285 ENDR("mult_ff_integer");
1286 }
1287
mult_ff_ff(a,b,c)1288 INT mult_ff_ff(a,b,c) OP a,b,c;
1289 /* AK 070802 */
1290 /* AK 280704 V3.0 */
1291 {
1292 INT erg = OK;
1293 CTO(FF,"mult_ff_ff(1)",a);
1294 CTO(FF,"mult_ff_ff(2)",b);
1295 if (S_O_K(c) != FF) FREESELF(c);
1296 CTTO(FF,EMPTY,"mult_ff_ff(3)",c);
1297 SYMCHECK(S_FF_CI(a) != S_FF_CI(b),"mult_ff_ff:different characteristic");
1298 {
1299 #ifdef FFTRUE
1300 Charakteristik = S_FF_CI(a);
1301
1302 if (S_O_K(c) != FF)
1303 erg += init_ff(c);
1304 else {
1305 INT *ap,*bp;
1306 ap =S_FF_IP(a);
1307 bp =S_FF_IP(c);
1308 // printf("*ap = %d *bp = %d\n",*ap,*bp);
1309 if (*ap > *bp)
1310 bp = (INT*) SYM_realloc(bp,(S_FF_DI(a)+1)*sizeof(INT));
1311 bp[0]=*ap;
1312 C_FF_IP(c,bp);
1313 M_I_I(0,S_FF_ME(c));
1314 // println(c);
1315 }
1316 M_I_I(Charakteristik,S_FF_C(c));
1317 if ((S_FF_DI(a)==1) && (S_FF_DI(b)==1)) /* AK 270705 */
1318 {
1319 INT *cp;
1320 cp = S_FF_IP(c);
1321 cp[0]=1; cp[1]=(S_FF_II(a,1)*S_FF_II(b,1)) % Charakteristik;
1322 }
1323 else
1324 UE_mult(& S_FF_IP(a), & S_FF_IP(b), & S_FF_IP(c) );
1325 SYMCHECK (S_FF_II(c,1) > Charakteristik, "mult_ff_ff:internal error 070295");
1326 SYMCHECK (S_FF_II(c,1) < 0, "mult_ff_ff:internal error 170304");
1327 #endif
1328 }
1329 ENDR("mult_ff_ff");
1330 }
1331
1332
einsp_ff(a)1333 INT einsp_ff(a) OP a;
1334 {
1335 #ifdef FFTRUE
1336 if (UE_ist_eins(& S_FF_IP(a)) == (INT)1) return TRUE;
1337 #endif
1338 return FALSE;
1339 }
1340
1341
add_ff(a,b,c)1342 INT add_ff(a,b,c) OP a,b,c;
1343 {
1344 INT erg = OK;
1345 #ifdef FFTRUE
1346 if (NULLP(b))
1347 return copy(a,c);
1348 if (S_O_K(b) != FF) /* AK 230294 */
1349 cast_apply_ff(b);
1350 if ((S_O_K(a) != FF) || (S_O_K(b) != FF))
1351 return WTT("add_ff",a,b);
1352
1353 if (S_FF_CI(a) != S_FF_CI(b))
1354 error("add_ff:different characteristic");
1355 Charakteristik = S_FF_CI(a);
1356 erg += init_ff(c);
1357 erg += UE_add(& S_FF_IP(a), &S_FF_IP(b), &S_FF_IP(c));
1358 erg += m_i_i(Charakteristik,S_FF_C(c));
1359
1360 SYMCHECK (S_FF_II(c,1) > Charakteristik, "add_ff:internal error 070295");
1361 SYMCHECK (S_FF_II(c,1) < 0, "add_ff:internal error 170304");
1362 #endif /* FFTRUE */
1363 ENDR("add_ff");
1364 }
1365
t_INTEGER_FF(a,b,c)1366 INT t_INTEGER_FF(a,b,c) OP a,b,c;
1367 /* AK 070394 */ /* AK 091204 V3.0 */
1368 /* a is INTEGER
1369 b is INTEGER = Charakteristik
1370 c becomes FF */
1371 {
1372 INT erg = OK;
1373 CTO(INTEGER,"t_INTEGER_FF(1)",a);
1374 CTO(INTEGER,"t_INTEGER_FF(2)",b);
1375 /* CE3(a,b,c,t_INTEGER_FF); AK 200802 */
1376 {
1377 #ifdef FFTRUE
1378 INT i;
1379 Charakteristik = S_I_I(b);
1380 i = S_I_I(a) % Charakteristik; /* AK 210802 mod added */
1381 while (i<0) i += Charakteristik; /* AK 070295 */
1382 erg += init_ff(c); /* c must not be empty */
1383 erg += UE_Int_Aequivalent(i, &S_FF_IP(c));
1384 M_I_I(Charakteristik,S_FF_C(c));
1385 #endif /* FFTRUE */
1386 }
1387 ENDR("t_INTEGER_FF");
1388
1389 }
1390
cast_apply_ff(a)1391 INT cast_apply_ff(a) OP a;
1392 /* AK 230294 */
1393 {
1394 INT erg = OK,i;
1395 #ifdef FFTRUE
1396 switch (S_O_K(a)) {
1397 case INTEGER:
1398 i = S_I_I(a);
1399 erg += init_ff(a);
1400 erg += UE_Int_Aequivalent(i, &S_FF_IP(a));
1401 erg += m_i_i(Charakteristik,S_FF_C(a));
1402 break;
1403 default:
1404 printobjectkind(a);
1405 erg += error("cast_apply_ff: transfer not possible");
1406 break;
1407 }
1408 SYMCHECK (S_FF_II(a,1) > Charakteristik, "cast_apply_ff:internal error 070295");
1409 SYMCHECK (S_FF_II(a,1) < 0, "cast_apply_ff:internal error 170304");
1410 #endif /* FFTRUE */
1411 ENDR("cast_apply_ff");
1412 }
1413
1414
minimal_extension(ff)1415 INT minimal_extension(ff) OP ff;
1416 {
1417 INT erg = OK;
1418 CTO(FF,"minimal_extension(1)",ff);
1419 {
1420 erg = reduce_ff(ff);
1421 }
1422 ENDR("minimal_extension");
1423 }
1424
1425 #ifdef FFTRUE
1426
1427 /******************************************************************************/
1428 /* Funktion UE_add belegt Ergebzeig mit seins+szwei */
1429 /******************************************************************************/
UE_add(seins,szwei,Ergebzeig)1430 static INT UE_add(seins,szwei,Ergebzeig) INT **seins; INT **szwei, **Ergebzeig;
1431 {
1432 INT i,j,k,*Summ1hilf,*Summ2hilf,*Summand_eins,*Summand_zwei,*Ergebnis;
1433 INT h1=0,h2=0;
1434 Summand_eins = *seins;
1435 Summand_zwei = *szwei;
1436 Ergebnis = *Ergebzeig;
1437
1438
1439 /* Falls der Grad einer der Summanden nicht Den Erweiterungsgrad teilt, */
1440 /* Wird eine Koerpererweiterung noetig */
1441 if (!UE_Erw_Grad ||
1442 (UE_Erw_Grad % Summand_eins[0]+UE_Erw_Grad%Summand_zwei[0]))
1443 {
1444 minimalErw(seins);
1445 minimalErw(szwei);
1446 }
1447 if (!UE_Erw_Grad ||
1448 (UE_Erw_Grad % Summand_eins[0]+UE_Erw_Grad%Summand_zwei[0]))
1449 {
1450 k = UE_kgv(Summand_eins[0],Summand_zwei[0]);
1451 if ( erzmulttafel(k,(INT)0,NULL) != OK) /* UWH */
1452 return error("ff.c:internal error FF70");
1453 }
1454
1455 /* ist der Grad einer der Summanden m nicht gleich dem aktuellen Grad, so */
1456 /* muss eine Einbettung vorgenommen werden, indem man die Koeffizienten */
1457 /* (<aktueller Grad> / m)-mal wiederholt. */
1458 if (Summand_eins[0] != UE_Erw_Grad)
1459 {
1460 k=1;
1461 Summ1hilf = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
1462 h1=1;
1463 for (i=(INT)0;i<UE_Erw_Grad/Summand_eins[0];i++)
1464 for (j=(INT)1;j<=Summand_eins[0];j++)
1465 {
1466 Summ1hilf[k++] = Summand_eins[j];
1467 }
1468 }
1469 else
1470 Summ1hilf = Summand_eins;
1471
1472 if (Summand_zwei[0] != UE_Erw_Grad)
1473 {
1474 k=1;
1475 h2=1;
1476 Summ2hilf = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
1477 for (i=0;i<UE_Erw_Grad/Summand_zwei[0];i++)
1478 for (j=1;j<=Summand_zwei[0];j++)
1479 Summ2hilf[k++] = Summand_zwei[j];
1480 }
1481 else
1482 Summ2hilf = Summand_zwei;
1483
1484 /* Der Grad des Ergebniselementes muss korrekt sein */
1485 if (Ergebnis[0]!=UE_Erw_Grad)
1486 {
1487 Ergebnis = (INT *) SYM_realloc(Ergebnis, (UE_Erw_Grad+1)*sizeof(INT));
1488 Ergebnis[0] = UE_Erw_Grad;
1489 *Ergebzeig = Ergebnis;
1490 }
1491
1492 /* Addition */
1493 for (i=1;i<=UE_Erw_Grad;i++)
1494 Ergebnis[i] = UE_ADDG(Summ1hilf[i],Summ2hilf[i]);
1495
1496 if (h1==1) /* AK 160393 */ SYM_free(Summ1hilf);
1497 if (h2==1) /* AK 160393 */ SYM_free(Summ2hilf);
1498 return OK;
1499 }
1500
1501
1502
1503
1504 /******************************************************************************/
1505 /* Funktion UE_mult belegt Ergebzeig mit feins+Fakt2zeig */
1506 /******************************************************************************/
UE_mult(feins,Fakt2zeig,Ergebzeig)1507 static INT UE_mult(feins,Fakt2zeig,Ergebzeig) INT **feins, **Fakt2zeig, **Ergebzeig;
1508 {
1509 INT i,j,k,l,m,*Fakt1hilf,*Fakt2hilf, *Ergebnis,zwisch;
1510
1511 /* AK 190802 */
1512 if (Faktor_eins == NULL) {
1513 Faktor_eins_size = 100;
1514 Faktor_eins = (INT *) UE_malloc(Faktor_eins_size*sizeof(INT));
1515 }
1516 else if (Faktor_eins_size < ((*feins)[0]+1)) {
1517 Faktor_eins_size = ((*feins)[0]+1)+100;
1518 Faktor_eins = (INT *) UE_realloc(Faktor_eins,Faktor_eins_size*sizeof(INT));
1519 }
1520
1521 memcpy(Faktor_eins, *feins, ((*feins)[0]+1) * sizeof(INT));
1522
1523 /* AK 190802 */
1524 if (Faktor_zwei == NULL) {
1525 Faktor_zwei_size = 100;
1526 Faktor_zwei = (INT *) UE_malloc(Faktor_zwei_size*sizeof(INT));
1527 }
1528 else if (Faktor_zwei_size < ((*Fakt2zeig)[0]+1)) {
1529 Faktor_zwei_size = ((*Fakt2zeig)[0]+1)+100;
1530 Faktor_zwei = (INT *) UE_realloc(Faktor_zwei,Faktor_zwei_size*sizeof(INT));
1531 }
1532
1533 memcpy(Faktor_zwei, *Fakt2zeig, ((*Fakt2zeig)[0]+1) * sizeof(INT));
1534 Ergebnis = *Ergebzeig;
1535
1536
1537 /* Falls der Grad einer der Faktoren nicht Den Erweiterungsgrad teilt, */
1538 /* Wird eine Koerpererweiterung noetig */
1539
1540 if (globalno!=1) /* AK else bad recusrion for degree = 6,10,
1541 product of diff primes */
1542 {
1543 FASTCHECKMULTTAFEL(UE_Erw_Grad);
1544 if (Mult_Tafel == NULL) erzmulttafel(UE_Erw_Grad,(INT)0,NULL);
1545 }
1546
1547 if (!UE_Erw_Grad || (UE_Erw_Grad%Faktor_eins[0] + UE_Erw_Grad%Faktor_zwei[0]))
1548 {
1549 minimalErw(feins);
1550 minimalErw(Fakt2zeig);
1551 }
1552 if (!UE_Erw_Grad ||
1553 (UE_Erw_Grad%Faktor_eins[0] + UE_Erw_Grad%Faktor_zwei[0])
1554 )
1555 {
1556 FASTCHECKMULTTAFEL(UE_kgv(Faktor_eins[0],Faktor_zwei[0]));
1557 if (Mult_Tafel == NULL)
1558 erzmulttafel(UE_kgv(Faktor_eins[0],Faktor_zwei[0]),(INT)0,NULL);
1559 }
1560 #ifdef UNDEF
1561 if (erzmulttafel(UE_kgv(Faktor_eins[0],Faktor_zwei[0]),(INT)0,NULL) != OK) /* UWH */
1562 {
1563 return error("ff.c: internal error (FF3)");
1564 }
1565 #endif
1566
1567 /* ist der Grad einer der Faktoren m nicht gleich dem aktuellen Grad, so */
1568 /* muss eine Einbettung vorgenommen werden, indem man die Koeffizienten */
1569 /* (<aktueller Grad> / m)-mal wiederholt. */
1570 if (Faktor_eins[0] != UE_Erw_Grad)
1571 {
1572 k=(INT)1;
1573 Fakt1hilf = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
1574 for (i=(INT)0;i<UE_Erw_Grad/Faktor_eins[0];i++)
1575 for (j=(INT)1;j<=Faktor_eins[0];j++)
1576 Fakt1hilf[k++] = Faktor_eins[j];
1577 }
1578 else
1579 Fakt1hilf = Faktor_eins;
1580
1581 if (Faktor_zwei[0] != UE_Erw_Grad)
1582 {
1583 k=1;
1584 Fakt2hilf = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
1585 for (i=0;i<UE_Erw_Grad/Faktor_zwei[0];i++)
1586 for (j=1;j<=Faktor_zwei[0];j++)
1587 Fakt2hilf[k++] = Faktor_zwei[j];
1588 }
1589 else
1590 Fakt2hilf = Faktor_zwei;
1591
1592 /* der Grad des Ergebnisselementes muss korrekt sein */
1593 if (Ergebnis[0]!=UE_Erw_Grad)
1594 {
1595 Ergebnis = (INT *) SYM_realloc(Ergebnis, (UE_Erw_Grad+1)*sizeof(INT) );
1596 Ergebnis[0] = UE_Erw_Grad;
1597 *Ergebzeig = Ergebnis;
1598 }
1599
1600 /* Ergebniselement mit 0 vobelegen */
1601 for (i=1;i<=UE_Erw_Grad;i++) Ergebnis[i] = 0;
1602
1603 /* Multiplikation mittels Multiplikationstafel */
1604 for (i=1;i<=UE_Erw_Grad;i++)
1605 {
1606 if(Fakt1hilf[i])
1607 {
1608 l=0;
1609 for (j=UE_Erw_Grad-i+1;j<=UE_Erw_Grad-1;j++)
1610 {
1611 l++;
1612 if (Fakt2hilf[l])
1613 {
1614 zwisch=UE_MULTG(Fakt1hilf[i],Fakt2hilf[l]);
1615 m=0;
1616 for (k=UE_Erw_Grad-i+(INT)1;k<=UE_Erw_Grad-(INT)1;k++)
1617 {
1618 m++;
1619 if (Mult_Tafel[j][k])
1620 Ergebnis[m]=UE_ADDG(Ergebnis[m],
1621 UE_MULTG(zwisch,Mult_Tafel[j][k])
1622 );
1623 }
1624 for (k=(INT)0;k<=UE_Erw_Grad-i;k++)
1625 {
1626 m++;
1627 if (Mult_Tafel[j][k])
1628 Ergebnis[m] = UE_ADDG(Ergebnis[m],
1629 UE_MULTG(zwisch,Mult_Tafel[j][k])
1630 );
1631 }
1632 }
1633 }
1634 for (j=(INT)0;j<=UE_Erw_Grad-i;j++)
1635 {
1636 l++;
1637 if (Fakt2hilf[l])
1638 {
1639 zwisch = UE_MULTG(Fakt1hilf[i],Fakt2hilf[l]);
1640 m=(INT)0;
1641 for (k=UE_Erw_Grad-i+(INT)1;k<=UE_Erw_Grad-(INT)1;k++)
1642 {
1643 m++;
1644 if (Mult_Tafel[j][k])
1645 Ergebnis[m] = UE_ADDG(Ergebnis[m],
1646 UE_MULTG(zwisch,Mult_Tafel[j][k]));
1647 }
1648 for (k=(INT)0;k<=UE_Erw_Grad-i;k++)
1649 {
1650 m++;
1651 if (Mult_Tafel[j][k])
1652 Ergebnis[m] = UE_ADDG(Ergebnis[m],
1653 UE_MULTG(zwisch,Mult_Tafel[j][k]));
1654 }
1655 }
1656 }
1657 }
1658 }
1659
1660 if (Faktor_eins!=Fakt1hilf) SYM_free ((char *) Fakt1hilf);
1661 if (Faktor_zwei!=Fakt2hilf) SYM_free ((char *) Fakt2hilf);
1662 return OK;
1663 }
1664
1665
1666
1667 /******************************************************************************/
1668 /* Funktion UE_negativ belegt Ergebnis mit -e */
1669 /******************************************************************************/
UE_negativ(e,Ergebnis)1670 static INT UE_negativ(e,Ergebnis) INT **e,**Ergebnis;
1671 /* e and Ergebnis may be equal */
1672 {
1673 INT i;
1674 /* minimalErw(e); */
1675 /* 0 e */
1676 if ((*e)[0] == (INT)1 && (*e)[1] == (INT)0)
1677 {
1678 (*Ergebnis)[0] = (INT)1;
1679 (*Ergebnis)[1] = (INT)0;
1680 return OK;
1681 }
1682 /* Ergebniselement muss korrekte Erweiterung haben */
1683 if ((*Ergebnis)[0] < (*e)[0])
1684 {
1685 SYM_free((char*) (*Ergebnis));
1686 *Ergebnis = (INT *) UE_malloc(((*e)[0] +1)*sizeof(INT));
1687 }
1688
1689 (*Ergebnis)[0] = (*e)[0];
1690 for (i=(INT)1;i<=(*e)[0];i++)
1691 if ((*e)[i])
1692 /* Negativbildung modulo Charakteristik */
1693 (*Ergebnis)[i] = Charakteristik-(*e)[i];
1694 else
1695 (*Ergebnis)[i] = (INT)0;
1696 return OK;
1697 }
1698
1699
1700 /******************************************************************************/
1701 /* Funktion UE_hoch berechnet e^m und gibt das Ergebnis in Ergebzeig aus*/
1702 /******************************************************************************/
UE_hoch(e,m,Ergebnis)1703 static INT UE_hoch(e,m,Ergebnis) INT **e, m, **Ergebnis;
1704 {
1705 INT *Elemhelp,i;
1706 /* minimalErw(e); AK 231296 */
1707 if ((*e)[0] == 1 && (*e)[1] == 0)
1708 {
1709 (*Ergebnis)[0] = (INT)1;
1710 (*Ergebnis)[1] = (INT)0;
1711 return OK;
1712 }
1713
1714 /* falls Einselement */
1715 if ((*e)[0] == 1 && (*e)[1] == 1)
1716 {
1717 (*Ergebnis)[0] = (INT)1;
1718 (*Ergebnis)[1] = (INT)1;
1719 return OK;
1720 }
1721
1722 /* Erzeugung eines Hilfselementes */
1723 Elemhelp = (INT *) UE_malloc(((*e)[0] +(INT)1)*sizeof(INT));
1724 for (i=(INT)0;i<=(*e)[0];i++)
1725 Elemhelp[i] = (*e)[i];
1726
1727 /* falls Ergebniselement nicht den benoetigten Erweiterungsgrad hat */
1728 if ((*Ergebnis)[0] < Elemhelp[0])
1729 {
1730 SYM_free((char*) (*Ergebnis));
1731 *Ergebnis = (INT *) UE_malloc(((*e)[0] +(INT)1)*sizeof(INT));
1732 }
1733
1734 for (i=(INT)0;i<=(*e)[0];i++)
1735 (*Ergebnis)[i] = (*e)[i];
1736 i = m-(INT)1;
1737 while(i>(INT)0)
1738 {
1739 while(!(i % 2L))
1740 {
1741 i /= 2L;
1742 UE_mult(&Elemhelp,&Elemhelp,&Elemhelp);
1743 }
1744 i--;
1745 UE_mult(Ergebnis,&Elemhelp,Ergebnis);
1746 }
1747 SYM_free((char *) Elemhelp);
1748 return OK;
1749 }
1750
1751
1752
1753 /******************************************************************************/
1754 /* Funktion invers berechnet 1/e und gibt das Ergebnis in Ergebzeig aus.*/
1755 /******************************************************************************/
UE_invers(e,Ergebnis)1756 static INT UE_invers(e,Ergebnis) INT **e,**Ergebnis;
1757 {
1758 INT i;
1759 if ((*e)[0] == 1 && (*e)[1] == (INT)0)
1760 {
1761 return error("UE_invers:division by 0");
1762 /*
1763 (*Ergebnis)[0] = (INT)0;
1764 return OK;
1765 */
1766 }
1767
1768 /* 1/e = e^(Charakteristik^(Erweiterungsgrad des ees)-2) */
1769 i = UE_power(Charakteristik,(*e)[0])-2;
1770 UE_hoch(e,i,Ergebnis);
1771 return OK;
1772 }
1773
1774
1775
1776 /******************************************************************************/
1777 /* Funktion UE_ist_null testet, ob e = 0 */
1778 /* Rueckgabewert : 1 falls e = 0, 0 sonst */
1779 /******************************************************************************/
UE_ist_null(e)1780 static INT UE_ist_null(e) INT **e;
1781 {
1782 /* AK 020304 */
1783 /*
1784 INT i;
1785 for (i=(*e)[0];i>0;i--) if ((*e)[i] != 0) return 0;
1786 return 1;
1787 */
1788 UE_IST_NULL(e);
1789 }
1790
1791 /******************************************************************************/
1792 /* Funktion UE_ist_eins testet, ob e = 1 */
1793 /* Rueckgabewert : 1 falls e = 1, 0 sonst */
1794 /******************************************************************************/
UE_ist_eins(e)1795 static INT UE_ist_eins(e) INT **e;
1796 {
1797 /* AK 020304 */
1798 INT i;
1799 for (i=1;i<=(*e)[0];i++) if ((*e)[i] != 1) return 0;
1800 return 1;
1801 }
1802
1803
1804
1805 /******************************************************************************/
1806 /* Funktion Int_Aequivalent berechnet zu einer Integerzahl a das zugehoerige */
1807 /* Grundkoerperelement und belegt Ergebnis damit. */
1808 /******************************************************************************/
UE_Int_Aequivalent(a,Ergebnis)1809 static INT UE_Int_Aequivalent(a,Ergebnis) INT a; INT **Ergebnis;
1810 {
1811 /* falls Ergebniselement nicht den benoetigten Erweiterungsgrad hat */
1812 if ((*Ergebnis)[0] < (INT)1)
1813 {
1814 SYM_free((char*) (*Ergebnis));
1815 *Ergebnis = (INT *) UE_malloc(2*sizeof(INT));
1816 }
1817 (*Ergebnis)[0] = 1;
1818 (*Ergebnis)[1] = a % Charakteristik;
1819 if ( (*Ergebnis)[1] < 0 ) (*Ergebnis)[1]=(*Ergebnis)[1] +Charakteristik; /* AK 170304 */
1820 UE_Erw_Grad = 1; /* AK 190100 */
1821 return OK;
1822 }
1823
1824
1825
1826
1827 /******************************************************************************/
1828 /* Funktion UE_ist_gleich vergleicht e_eins mit e_zwei */
1829 /* Rueckgabewert : 1 falls e_eins > e_zwei, */
1830 /* -1 falls e_eins < e_zwei, */
1831 /* 0 falls e_eins = e_zwei. */
1832 /******************************************************************************/
UE_ist_gleich(e_eins,e_zwei)1833 static INT UE_ist_gleich(e_eins,e_zwei) INT **e_eins, **e_zwei;
1834 {
1835 INT i,j,k,*Elem1hilf,*Elem2hilf;
1836 INT gemein_grad;
1837
1838 /* falls die ee verschiedene Erweiterungsgrade ueber dem Grundkoerper */
1839 /* haben, muessen sie in den gemeinsammen Erweiterungskoerper eingebettet */
1840 /* werden. */
1841 if ((*e_eins)[0] != (*e_zwei)[0])
1842 {
1843 gemein_grad = UE_kgv((*e_eins)[0],(*e_zwei)[0]);
1844 if ((*e_eins)[0] != gemein_grad)
1845 {
1846 k=(INT)1;
1847 Elem1hilf = (INT *) UE_malloc((gemein_grad+1)*sizeof(INT));
1848 for (i=(INT)0;i<gemein_grad/(*e_eins)[0];i++)
1849 for (j=(INT)1;j<=(*e_eins)[0];j++)
1850 Elem1hilf[k++] = (*e_eins)[j];
1851 }
1852 else
1853 Elem1hilf = *e_eins;
1854
1855 if ((*e_zwei)[0] != gemein_grad)
1856 {
1857 k=(INT)1;
1858 Elem2hilf = (INT *) UE_malloc((gemein_grad+1)*sizeof(INT));
1859 for (i=(INT)0;i<gemein_grad/(*e_zwei)[0];i++)
1860 for (j=(INT)1;j<=(*e_zwei)[0];j++)
1861 Elem2hilf[k++] = (*e_zwei)[j];
1862 }
1863 else
1864 Elem2hilf = *e_zwei;
1865 }
1866 else
1867 {
1868 Elem1hilf = *e_eins;
1869 Elem2hilf = *e_zwei;
1870 gemein_grad = (*e_eins)[0] ; /* AK 230395 */
1871 }
1872
1873 /* Vergleich */
1874 k = 0;
1875 for (i=1;i<=gemein_grad;i++)
1876 if (Elem1hilf[i] != Elem2hilf[i])
1877 {
1878 k = i;
1879 i = gemein_grad+(INT)1;
1880 }
1881
1882 if (k > 0 && Elem1hilf[k] < Elem2hilf[k])
1883 k = -1;
1884
1885 if (k > 0 && Elem1hilf[k] > Elem2hilf[k])
1886 k = 1;
1887
1888 /* Speicher, fallsbenoetigt freigeben */
1889 if (*e_eins!=Elem1hilf) SYM_free ((char *) Elem1hilf);
1890 if (*e_zwei!=Elem2hilf) SYM_free ((char *) Elem2hilf);
1891
1892 return(k);
1893 }
1894
1895
1896
order_ff(a,b)1897 INT order_ff(a,b) OP a,b;
1898 /* AK 170194 */
1899 {
1900 INT erg = OK;
1901 if (a == b)
1902 return ERROR;
1903 CTO(FF,"order_ff",a);
1904 erg += erzmulttafel(UE_Erw_Grad,0,NULL); /* UWH */
1905 erg += m_i_i(UE_order( & S_FF_IP(a) ), b);
1906 ENDR("order_ff");
1907 }
1908
1909 /******************************************************************************/
1910 /* Funktion UE_order berechnet das kleinste m mit e^m = 1 */
1911 /* Rueckgabewert : die berechnete Ordnung. */
1912 /******************************************************************************/
UE_order(e)1913 static INT UE_order(e) INT **e;
1914 {
1915 INT maxord = UE_power(Charakteristik,(*e)[0])-(INT)1;
1916 INT maxteiler = maxord/2L;
1917
1918 INT i,*Ergebnis;
1919 UE_Platz(&Ergebnis);
1920 for (i=(INT)1;i<=maxteiler;i++)
1921 if (!(maxord % i))
1922 {
1923 UE_hoch(e,i,&Ergebnis);
1924 if (UE_ist_eins(&Ergebnis))
1925 {
1926 SYM_free(Ergebnis);
1927 return i;
1928 }
1929 }
1930 UE_Free(&Ergebnis);
1931 return(maxord);
1932 }
1933
1934
1935
1936 /******************************************************************************/
1937 /* Funktion UE_Random erzeugt ein zufaelliges e im Koerper des aktuellen*/
1938 /* Grades. */
1939 /******************************************************************************/
UE_Random(e)1940 static INT UE_Random(e) INT **e;
1941 {
1942 INT i;
1943 /* Der Erweiterungsgrad des ees muss mit dem aktuellen uebereinstimmen */
1944 SYM_free(*e); /* AK 170393 */
1945 *e = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
1946 (*e)[0] = UE_Erw_Grad;
1947 /* Zufallserzeugung */
1948 for (i=(INT)1;i<=UE_Erw_Grad;i++)
1949 (*e)[i] = rand() % Charakteristik;
1950 /* minimalErw(e); */ /* AK 020304 */
1951 return OK;
1952 }
1953
1954
1955
1956
1957 #ifdef UNDEF
UE_main()1958 UE_main()
1959 {
1960 INT u=1,i,j=0,*test,*test_eins,*test_zwei;
1961 UE_Erw_Grad = (INT)0;
1962 do {
1963 printf("Geben sie die gewuenschte Charakteristik ein ");
1964 scanf("%d",&Charakteristik);
1965 fflush(stdout);
1966 j = UE_prim(Charakteristik);
1967 if (!j)
1968 printf("\n Dies ist keine Primzahl!\n");
1969 } while (!j);
1970 while(u)
1971 {
1972 UE_Platz(&test);
1973 UE_scan(&test);
1974 printf("\n");
1975 UE_Platz(&test_eins);
1976 UE_scan(&test_eins);
1977 printf("\n");
1978 UE_Platz(&test_zwei);
1979 UE_add(&test,&test_eins,&test_zwei);
1980 UE_Zeige(&test);
1981 printf(" + \n");
1982 UE_Zeige(&test_eins);
1983 printf(" = \n");
1984 UE_Zeige(&test_zwei);
1985 if (UE_ist_null(&test_zwei))
1986 printf("ist Null\n");
1987 if (UE_ist_eins(&test_zwei))
1988 printf("ist Eins\n");
1989 printf("\n\n");
1990 UE_mult(&test,&test_eins,&test_zwei);
1991 UE_Zeige(&test);
1992 printf(" * \n");
1993 UE_Zeige(&test_eins);
1994 printf(" = \n");
1995 UE_Zeige(&test_zwei);
1996 if (UE_ist_null(&test_zwei))
1997 printf("ist Null\n");
1998 if (UE_ist_eins(&test_zwei))
1999 printf("ist Eins\n");
2000 printf("\n\n");
2001 UE_invers(&test_zwei,&test_eins);
2002 printf("1/ ");
2003 UE_Zeige(&test_zwei);
2004 printf(" = ");
2005 UE_Zeige(&test_eins);
2006 if (UE_ist_null(&test_eins))
2007 printf("ist Null\n");
2008 if (UE_ist_eins(&test_eins))
2009 printf("ist Eins\n");
2010 printf("\n\n");
2011 UE_negativ(&test_zwei,&test_eins);
2012 printf("0- ");
2013 UE_Zeige(&test_zwei);
2014 printf(" = ");
2015 UE_Zeige(&test_eins);
2016 if (UE_ist_null(&test_eins))
2017 printf("ist Null\n");
2018 if (UE_ist_eins(&test_eins))
2019 printf("ist Eins\n");
2020 UE_Free(&test);
2021 UE_Free(&test_eins);
2022 UE_Free(&test_zwei);
2023 printf("Momentane Koerpererweiterung: %d\n",UE_Erw_Grad);
2024 printf("Ende = 1 Weiter = 2 neuer Grad und weiter = 3 ");
2025 scanf("%d",&i);
2026 if (i==1)
2027 u=(INT)0;
2028 if (i==3)
2029 {
2030 printf("Grad :");
2031 scanf("%ld",&UE_Erw_Grad);
2032 erzmulttafel(UE_Erw_Grad,0,NULL); /* UWH */
2033 }
2034 }
2035 }
2036 #endif /* UNDEF */
2037
init_ff(a)2038 static INT init_ff(a) OP a;
2039 {
2040 INT erg = OK;
2041 erg += m_il_v(3L,a);
2042 /* first = characteristic
2043 second = vector of components of ff
2044 third = minimalErw = y=1/unknown=0
2045 */
2046 C_O_K(a,FINITEFIELD);
2047 erg += UE_Platz(&S_FF_IP(a));
2048 M_I_I(0,S_FF_ME(a));
2049 return erg;
2050 }
2051
2052
debugprint_ff(a)2053 INT debugprint_ff(a) OP a;
2054 /* AK 160393 */
2055 {
2056 INT i;
2057 INT *iv;
2058 for (i=(INT)0;i<doffset;i++) fputc(' ',stderr);
2059 fprintf(stderr,"ff:Charakteristik =\n");
2060 doffset += 2L;
2061 debugprint(s_v_i(a,(INT)0));
2062 doffset -= 2L;
2063 fprintf(stderr,"ff:reduce_info =\n");
2064 doffset += 2L;
2065 debugprint(s_v_i(a,(INT)2));
2066 doffset -= 2L;
2067 iv = S_O_S(S_V_I(a,(INT)1)).ob_INTpointer;
2068 for (i=(INT)0;i<doffset;i++) fputc(' ',stderr);
2069 fprintf(stderr,"ff:INT vektor =\n");
2070 for (i=(INT)0;i<doffset;i++) fputc(' ',stderr);
2071 for (i=(INT)0;i<= *iv;i++)
2072 fprintf(stderr, "%" PRIINT " " ,*(iv+i));
2073 fprintf(stderr,"\n");
2074 return OK;
2075 }
2076
2077
reduce_ff(a)2078 INT reduce_ff(a) OP a;
2079 /* AK 290304 */
2080 /* computes the minimal extension over the
2081 prime field, where a lives in */
2082 {
2083 INT erg = OK;
2084 CTO(FF,"reduce_ff(1)",a);
2085 {
2086 INT *ai;
2087 if (S_FF_MEI(a) != 1) {
2088 ai = S_O_S(S_V_I(a,1)).ob_INTpointer;
2089 minimalErw(&ai);
2090 M_I_I(1,S_FF_ME(a)); /* 1 = this is a minimal extension */
2091 }
2092 }
2093 ENDR("reduce_ff");
2094 }
2095
primep_ff(a)2096 INT primep_ff(a) OP a;
2097 /* AK 130704 */
2098 /* returns true if a is an element of the prime field */
2099 /* AK 130704 V3.0 */
2100 {
2101 INT erg = OK;
2102 CTO(FF,"primep_ff(1)",a);
2103 {
2104 INT deg = S_FF_DI(a);
2105 if (S_FF_MEI(a)==1) /* is the minimal extension */
2106 {
2107 if (deg == 1) return TRUE;
2108 else return FALSE;
2109 }
2110 else
2111 {
2112 INT i,vi=S_FF_II(a,0); /* first entry */
2113 for (i=1;i<deg;i++) if (S_FF_II(a,i) != vi) return FALSE;
2114 /* the degree could be reduced */
2115 return TRUE;
2116 }
2117 }
2118 ENDR("primep_ff");
2119 }
2120
2121
hash_ff(a)2122 INT hash_ff(a) OP a;
2123 /* AK 200104 */
2124 /* AK 130704 V3.0 */
2125 {
2126 INT erg = OK;
2127 CTO(FF,"hash_ff(1)",a);
2128 {
2129 INT i,res,deg;
2130 // reduce_ff(a); /* minimal extension*/
2131 deg=S_FF_DI(a);
2132 res = 11011;
2133 for (i=0;i<=deg;i++)
2134 res = res*11+S_FF_II(a,i);
2135
2136 return res;
2137 }
2138 ENDR("hash_ff");
2139 }
2140
fprint_ff(f,a)2141 INT fprint_ff(f,a) OP a; FILE *f;
2142 /* AK 180194 *//* AK 260594 */
2143 /* AK 080704 V3.0 */
2144 {
2145 INT erg = OK;
2146 CTO(FF,"fprint_ff(2)",a);
2147
2148 {
2149 fputc('[',f);
2150 erg += UE_fZeige(f,& S_FF_IP(a));
2151 fputc(']',f);
2152 if (f == stdout) zeilenposition += 2;
2153 }
2154
2155 ENDR("fprint_ff");
2156 }
2157
2158
objectwrite_ff(f,a)2159 INT objectwrite_ff(f,a) FILE *f; OP a;
2160 /* AK 040304 */
2161 /* AK 130704 V3.0 */
2162 {
2163 INT erg = OK;
2164 COP("objectread_ff(1)",f);
2165 CTO(FF,"objectwrite_ff(2)",a);
2166 {
2167 INT i,*ip;
2168 fprintf(f, "%" PRIINT "\n%ld\n%" PRIINT " " ,
2169 (INT)FF,S_FF_CI(a),S_FF_DI(a));
2170 ip = S_FF_IP(a);
2171 for (i=0;i<S_FF_DI(a);i++) fprintf(f,"%" PRIINT " ",ip[i+1]);
2172 fputc('\n',f);
2173 }
2174 ENDR("objectwrite_bruch");
2175 }
2176
2177
2178
objectread_ff(f,a)2179 INT objectread_ff(f,a) FILE *f; OP a;
2180 /* AK 040304 */
2181 /* AK 130704 V3.0 */
2182 {
2183 INT erg = OK;
2184 COP("objectread_ff(1)",f);
2185 {
2186 INT i,j,*ip;
2187 fscanf(f, "%" SCNINT ,&i);Charakteristik=i;
2188 fscanf(f, "%" SCNINT ,&i);UE_Erw_Grad=i;
2189 init_ff(a);ip = S_FF_IP(a);
2190 for (j=0;j<UE_Erw_Grad;j++) { fscanf(f, "%" SCNINT ,&i); ip[j+1]=i;}
2191 ip[0]=UE_Erw_Grad;
2192 M_I_I(Charakteristik,S_V_I(a,0));
2193 }
2194 CTO(FF,"objectread_ff(i)",a);
2195 ENDR("objectread_ff");
2196 }
2197
2198
2199
2200
sprint_ff(f,a)2201 INT sprint_ff(f,a) OP a; char *f;
2202 /* AK 040304 */
2203 {
2204 INT erg = OK,i,j;
2205 sprintf(f, "[%" PRIdPTR "," ,S_FF_CI(a)); i = strlen(f); f = f+i;
2206 for (i=0;i<S_FF_DI(a)-1;i++) {
2207 sprintf(f,"%d,",S_FF_II(a,i));
2208 j=strlen(f);f=f+j;
2209 }
2210 sprintf(f,"%d]",S_FF_II(a,i));
2211 return erg;
2212 }
2213
2214
m_vector_ff(a,b,c)2215 INT m_vector_ff(a,b,c) OP a,b,c;
2216 /* AK 170194 */ /* a Charakteristik, b INTEGERVECTOR */
2217 /* AK 310106 V3.0 */
2218 {
2219 INT erg = OK;
2220 INT i;
2221 INT *bi;
2222
2223 if (check_equal_3(a,b,c,m_vector_ff,&erg) == EQUAL)
2224 goto mve;
2225
2226 if (S_O_K(a) != INTEGER)
2227 return WTT("m_vector_ff",a,b);
2228 if (not VECTORP(b))
2229 return WTT("m_vector_ff",a,b);
2230
2231 Charakteristik = S_I_I(a);
2232 UE_Erw_Grad = S_V_LI(b);
2233 init_ff(c);
2234 erg += UE_Platz(&S_FF_IP(c));
2235 bi = S_FF_IP(c);
2236 *bi = S_V_LI(b);
2237 for (i=(INT)0;i<S_V_LI(b);i++)
2238 *(bi+i+1) = S_V_II(b,i);
2239
2240 erg += m_i_i(Charakteristik,S_V_I(c,(INT)0));
2241 erg += erzmulttafel(UE_Erw_Grad,0,NULL); /* UWH */
2242 mve:
2243 ENDR("m_vector_ff");
2244 }
2245
m_ff_vector(a,b)2246 INT m_ff_vector(a,b) OP a,b;
2247 /* AK 230395 */
2248 {
2249 INT erg = OK;
2250 INT i;
2251 CTO(FINITEFIELD,"m_ff_vector(1)",a);
2252 CE2(a,b,m_ff_vector);
2253
2254 erg += m_il_v(S_FF_DI(a),b);
2255 for (i=0;i<S_V_LI(b);i++)
2256 M_I_I(S_FF_II(a,i+1),S_V_I(b,i));
2257 C_O_K(b,INTEGERVECTOR);
2258 ENDR("m_ff_vector");
2259 }
2260
first_ff(a,b,c)2261 INT first_ff(a,b,c) OP a,b,c;
2262 /* AK 170194 a Charakteristik, b Grad der Erweiterung */
2263 {
2264 INT erg = OK;
2265 CTO(INTEGER,"first_ff(1)",a);
2266 CTO(INTEGER,"first_ff(2)",b);
2267 {
2268 OP d;
2269 d = callocobject();
2270 erg += m_il_nv(S_I_I(b),d);
2271 erg += m_vector_ff(a,d,c);
2272 FREEALL(d);
2273 }
2274 ENDR("first_ff");
2275 }
2276
first_ff_given_q(q,c)2277 INT first_ff_given_q(q,c) OP q,c;
2278 /* AK 290304 */
2279 /* AK 210704 V3.0 */
2280 {
2281 INT erg = OK;
2282 CTO(INTEGER,"first_ff_given_q(1)",q);
2283 SYMCHECK(S_I_I(q) < 2,"first_ff_given_q:q<2");
2284 SYMCHECK(prime_power_p(q) ==FALSE,"first_ff_given_q:q no prime power");
2285 {
2286 OP v;
2287 v = CALLOCOBJECT();
2288 erg += factorize_integer(q,v);
2289 erg += first_ff(S_V_I(v,0),S_V_L(v),c);
2290 FREEALL(v);
2291 }
2292 ENDR("first_ff_given_q");
2293 }
2294
next_apply_ff(a)2295 INT next_apply_ff(a) OP a;
2296 /* AK 090804 V3.0 */
2297 {
2298 return next_ff(a,a);
2299 }
2300
next_ff(a,b)2301 INT next_ff(a,b) OP a,b;
2302 /* a and b may be equal */
2303 /* AK 090804 V3.0 */
2304 {
2305 INT erg = OK;
2306 CTO(FF,"next_ff(1)",a);
2307 {
2308 INT i,*ai,l;
2309 Charakteristik = S_V_II(a,(INT)0);
2310 if (a != b) copy(a,b);
2311 ai = S_O_S(S_V_I(b,(INT)1)).ob_INTpointer;
2312 UE_Erw_Grad = *ai;
2313 l = *ai;
2314 for (i=l;i>0;i--)
2315 if ( *(ai+i) < (Charakteristik-1) )
2316 {
2317 *(ai+i) = *(ai+i) + 1;
2318 for (i++;i<=l;i++)
2319 {
2320 *(ai+i) = 0;
2321 }
2322 return OK;
2323 }
2324 if (i == 0)
2325 return LAST_FF;
2326 }
2327 erg = ERROR;
2328 ENDR("next_ff");
2329 }
2330
2331 /****************************************************************************/
2332 /* Funktion einfuegTrace fuegt ein neu berechnetes Polynom in die */
2333 /* entsprechende Datei ein. */
2334 /* bergabeparameter Grad Erweiterungsgrad der Datei */
2335 /* tracePolynom einzutragendes Polynom */
2336 /****************************************************************************/
einfuegTrace(Grad,tracePolynom)2337 void einfuegTrace(Grad,tracePolynom) INT Grad; INT *tracePolynom;
2338 {
2339 INT j;
2340 INT i;
2341 INT Laenge;
2342 char Zeichenkette[50];
2343 /* "G<GRAD>:" */
2344 if (Datei==NULL) {
2345 // error("internal error FF311");
2346 return;
2347 }
2348
2349 Laenge = getString(Grad,Zeichenkette);
2350 fseek(Datei,0,2);
2351 putc('G',Datei);
2352 for (i=0;i<Laenge;i++)
2353 putc(Zeichenkette[i],Datei);
2354 putc(':',Datei);
2355
2356 /* Polynomkoeffizienten */
2357 for (j=0;j<Grad;j++)
2358 {
2359 Laenge = getString(tracePolynom[j],Zeichenkette);
2360 for (i=0;i<Laenge;i++)
2361 putc(Zeichenkette[i],Datei);
2362 putc(' ',Datei);
2363 }
2364 putc('\n',Datei);
2365 fflush(Datei);
2366 return;
2367 }
2368
2369
2370
2371
2372 /****************************************************************************/
2373 /* Funktion spezGrad ermittelt den Grad von Polynom */
2374 /* */
2375 /* Uebergabeparameter : Polynom,Grad */
2376 /* */
2377 /* Rueckgabeparameter Grad des Polynoms */
2378 /****************************************************************************/
spezGrad(Polynom,Grad)2379 static INT spezGrad(Polynom,Grad) INT *Polynom; INT Grad;
2380 {
2381 INT i;
2382 for (i=Grad;i>=0;i--)
2383 {
2384 if (Polynom[i])
2385 {
2386 return(i);
2387 }
2388 }
2389 return(-1);
2390 }
2391
2392
2393
2394
2395 /****************************************************************************/
2396 /* Funktion spezNormiert normiert Polynom */
2397 /* bergabeparameter : Polynom, NormalPolynom,Grad */
2398 /****************************************************************************/
spezNormiert(Polynom,Grad)2399 static INT *spezNormiert(Polynom,Grad) INT *Polynom; INT Grad;
2400 {
2401 INT i;
2402 INT maxGrad = spezGrad(Polynom,Grad);
2403 INT Faktor = Polynom[maxGrad];
2404 if (Faktor==1)
2405 return(Polynom);
2406 Faktor = UE_divg(1,Faktor);
2407 for (i=maxGrad;i>=0;i--)
2408 Polynom[i] = UE_multg(Polynom[i],Faktor);
2409 return(Polynom);
2410 }
2411
2412
2413
2414 /***************************************************************************/
2415 /* Funktion spezEinsGGT berprft, ob GGT(Pol1,Pol2) = 1 */
2416 /* bergabeparameter Pol1, Pol2, Grad = Grad der Polynome */
2417 /* Rckgabewert : 1, falls GGT = 1, 0 sonst */
2418 /***************************************************************************/
spezEinsGGT(Pol1,Pol2,Grad)2419 static INT spezEinsGGT(Pol1,Pol2,Grad) INT *Pol1; INT *Pol2; INT Grad;
2420 {
2421 INT i;
2422 INT *hilf1pol;
2423 INT *hilf2pol;
2424 if (!(hilf1pol = (INT *) UE_malloc((Grad+1)*sizeof(INT))))
2425 return no_memory();
2426
2427 if (!(hilf2pol = (INT *) UE_malloc((Grad+1)*sizeof(INT))))
2428 {
2429 SYM_free((char *) hilf1pol);
2430 return no_memory();
2431 }
2432 for (i=0;i<=Grad;i++)
2433 {
2434 hilf1pol[i] = Pol1[i];
2435 hilf2pol[i] = Pol2[i];
2436 }
2437 while (spezGrad(hilf1pol,Grad)>=0 && spezGrad(hilf2pol,Grad)>=0)
2438 {
2439 reduzierpoly(hilf1pol,spezGrad(hilf1pol,Grad),spezNormiert(hilf2pol,Grad),spezGrad(hilf2pol,Grad));
2440 if(spezGrad(hilf1pol,Grad)>=0)
2441 reduzierpoly(hilf2pol,spezGrad(hilf2pol,Grad),spezNormiert(hilf1pol,Grad),spezGrad(hilf1pol,Grad));
2442 }
2443
2444 /* Grad = 0 bedeutet von 0 verschiedenes Grundkoerperelement */
2445 if (spezGrad(hilf1pol,Grad)==0)
2446 {
2447 SYM_free((char *) hilf1pol);
2448 SYM_free((char *) hilf2pol);
2449 return (INT)1;
2450 }
2451
2452 /* hilf1pol = 0 und hilf2pol von 0 verschiedenes Grundkorperelement */
2453 if (spezGrad(hilf1pol,Grad)<0)
2454 if (spezGrad(hilf2pol,Grad)==0)
2455 {
2456 SYM_free((char *) hilf1pol);
2457 SYM_free((char *) hilf2pol);
2458 return (INT) 1;
2459 }
2460
2461 SYM_free((char *) hilf1pol);
2462 SYM_free((char *) hilf2pol);
2463 return(INT)0;
2464 }
2465
2466
2467
2468 /****************************************************************************/
2469 /* Funktion spezMult Multiplikation zweier Koerperelemente Modulo */
2470 /* NormalPolynom */
2471 /* bergabeparameter : Faktor1, Faktor2, Ergebnis, NormalPolynom, Grad */
2472 /* */
2473 /* Rckgabeparameter 1, falls ohne Probleme durchgefuehrt, 0 sonst. */
2474 /****************************************************************************/
spezMult(Faktor1,Faktor2,Ergebnis,NormalPolynom,Grad)2475 static INT spezMult(Faktor1,Faktor2,Ergebnis,NormalPolynom,Grad)
2476 INT *Faktor1;
2477 INT *Faktor2;
2478 INT *Ergebnis;
2479 INT *NormalPolynom;
2480 INT Grad;
2481 {
2482 INT i;
2483 INT j;
2484 INT ergebnisGrad=0;
2485 INT *zwischenErgebnis;
2486 zwischenErgebnis = (INT *) SYM_calloc(Grad+Grad,sizeof(INT));
2487
2488 for (i=0;i<Grad;i++)
2489 for(j=0;j<Grad;j++)
2490 if(Faktor1[i] && Faktor2[j])
2491 {
2492 if (ergebnisGrad < i+j)
2493 ergebnisGrad = i+j;
2494 zwischenErgebnis[i+j] = UE_addg(zwischenErgebnis[i+j],
2495 UE_multg(Faktor1[i],Faktor2[j]));
2496 }
2497
2498 reduzierpoly(zwischenErgebnis,ergebnisGrad,NormalPolynom,Grad);
2499
2500 for (i=0;i<Grad;i++)
2501 Ergebnis[i] = zwischenErgebnis[i];
2502
2503 SYM_free((char *) zwischenErgebnis);
2504 return(1);
2505 }
2506
2507 /*******************************************************************************/
2508 /* Funktion spezHoch berechnet Element^m und gibt das Ergebnis in Ergebzeig aus*/
2509 /*******************************************************************************/
spezHoch(Element,m,Ergebnis,NormalPolynom,Grad)2510 static int spezHoch(Element,m,Ergebnis,NormalPolynom,Grad) INT *Element;
2511 INT m;
2512 INT *Ergebnis;
2513 INT *NormalPolynom;
2514 INT Grad;
2515 {
2516 INT *Elemhelp,i;
2517
2518 /* Erzeugung eines Hilfselementes */
2519 if(!(Elemhelp = (INT *) UE_malloc(Grad*sizeof(INT))))
2520 {
2521 return(0);
2522 }
2523 for (i=0;i<Grad;i++)
2524 Elemhelp[i] = Element[i];
2525
2526 for (i=0;i<Grad;i++)
2527 Ergebnis[i] = Element[i];
2528
2529 i = m-1;
2530 while(i>0)
2531 {
2532 while(!(i % 2))
2533 {
2534 i /= 2;
2535 spezMult(Elemhelp,Elemhelp,Elemhelp,NormalPolynom,Grad);
2536 }
2537 i--;
2538 spezMult(Ergebnis,Elemhelp,Ergebnis,NormalPolynom,Grad);
2539 }
2540 SYM_free((char *) Elemhelp);
2541 return(1);
2542 }
2543
2544 /****************************************************************************/
2545 /* Funktion triang bildet Dreiecksmatrix von Matrix */
2546 /****************************************************************************/
triang(Matrix,Deg)2547 static void triang(Matrix,Deg) INT **Matrix; INT Deg;
2548
2549 {
2550 INT i,j,k,l,pp,u;
2551 for(i=0;i<Deg;i++)
2552 {
2553 j=i;
2554 while((!(Matrix[i])[j]) && (j<Deg-1))
2555 j++;
2556 if(!(Matrix[i])[j])
2557 {
2558 j=0;
2559 while((j<i) && ((!(Matrix[i])[j]) || (Matrix[j][j])))
2560 j++;
2561 }
2562 if (Matrix[i][j])
2563 {
2564 u = UE_divg(1,Matrix[i][j]);
2565 for(k=i;k<Deg;k++)
2566 Matrix[k][j] = UE_multg(Matrix[k][j],u);
2567 for(k=0;k<Deg;k++)
2568 if (k!=j)
2569 {
2570 u = UE_subg(0,Matrix[i][k]);
2571 if (Matrix[i][k])
2572 for(l=i;l<Deg;l++)
2573 {
2574 Matrix[l][k] = UE_addg(Matrix[l][k],UE_multg(u,Matrix[l][j]));
2575 }
2576 }
2577 if (i!=j)
2578 for(k=i;k<Deg;k++)
2579 {
2580 pp = Matrix[k][i];
2581 Matrix[k][i] = Matrix[k][j];
2582 Matrix[k][j] = pp;
2583 }
2584 }
2585 }
2586 }
2587
2588
2589
2590
2591 /****************************************************************************/
2592 /* Funktion testirrPolynom testet, ob Polynom irreduzibel ist. */
2593 /* Uebergabeparameter NormaltestPolynom,Grad */
2594 /* Rueckgabewert 1, falls NormaltestPolynom irreduzibel, 0 sonst */
2595 /****************************************************************************/
testirrPolynom(NormaltestPolynom,Grad)2596 static INT testirrPolynom(NormaltestPolynom,Grad)
2597 INT *NormaltestPolynom;
2598 INT Grad;
2599 {
2600 INT i;
2601 INT j;
2602 INT *Ableitung,*hf,*x,*q_mat;
2603 INT **Matrix;
2604 Ableitung = (INT *) SYM_calloc(Grad+1,sizeof(INT));
2605 /* Bildung der Ableitung */
2606 for(i=0;i<Grad-1;i++)
2607 Ableitung[i] = UE_multg(NormaltestPolynom[i+1],i+1);
2608 Ableitung[Grad-1] = Grad % Charakteristik;
2609
2610 for(i=0;i<Grad;i++)
2611 if(Ableitung[i] != 0)
2612 i = Grad + 1;
2613 /* Alle EINTraege = 0 -> Ableitung = 0 -> nicht irreduzibel */
2614 if (i == Grad)
2615 {
2616 SYM_free((char *) Ableitung);
2617 return(0);
2618 }
2619
2620 if (!spezEinsGGT(NormaltestPolynom,Ableitung,Grad))
2621 {
2622 SYM_free((char *) Ableitung);
2623 return(0);
2624 }
2625
2626 hf = (INT *) SYM_calloc(Grad,sizeof(INT));
2627 q_mat = (INT *) SYM_calloc(Grad*Grad,sizeof(INT));
2628 x = (INT *) SYM_calloc(Grad*2,sizeof(INT));
2629 Matrix = (INT **) SYM_calloc(Grad,sizeof (INT *));
2630
2631 i=0;
2632 for (j=0;j<Grad;j++)
2633 {
2634 Matrix[j]=q_mat+(j*Grad);
2635 }
2636
2637 (Matrix[0])[0] = 1;
2638 x[1] = 1;
2639 spezHoch(x,Charakteristik,x,NormaltestPolynom,Grad);
2640 for(i=1;i<Grad;i++)
2641 {
2642 for(j=0;j<Grad;j++)
2643 {
2644 hf[j] = (Matrix[i-1])[j];
2645 }
2646 spezMult(hf,x,hf,NormaltestPolynom,Grad);
2647 for(j=0;j<Grad;j++)
2648 {
2649 (Matrix[i])[j] = hf[j];
2650 }
2651 }
2652 for(i=0;i<Grad;i++)
2653 (Matrix[i])[i]=UE_subg((Matrix[i])[i],1);
2654 triang(Matrix,Grad);
2655 j=0;
2656 for(i=0;i<Grad;i++)
2657 if ((Matrix[i])[i]==1)
2658 j++;
2659 SYM_free((char *) hf);
2660 SYM_free((char *) x);
2661 SYM_free((char *) q_mat);
2662 SYM_free((char *) Matrix);
2663 SYM_free((char *) Ableitung);
2664 if(j==(Grad-1))
2665 return(1);
2666 return(0);
2667 }
2668
2669
2670
2671
2672
2673 /****************************************************************************/
2674 /* Funktion testNormalPol berprft, ob Polynom NormalPolynom ist. */
2675 /* */
2676 /* bergabeparameter : NormalPolynom, Grad */
2677 /* */
2678 /* Rckgabeparameter : 1, falls Normalpolynom, 0 sonst */
2679 /****************************************************************************/
testNormalPol(NormaltestPolynom,Grad)2680 static INT testNormalPol(NormaltestPolynom,Grad)
2681 INT *NormaltestPolynom;
2682 INT Grad;
2683 {
2684 INT i;
2685 INT j;
2686 INT *Permutation;
2687 INT *NormalPolynom;
2688 INT *a_Hoch_q;
2689 INT **Pol1;
2690
2691 if(!(NormalPolynom = (INT *) UE_malloc(Grad*sizeof(INT))))
2692 {
2693 return no_memory();
2694 }
2695
2696 for (i=0;i<Grad;i++)
2697 NormalPolynom[i] = NormaltestPolynom[i];
2698
2699 if(!(Permutation = (INT *) UE_malloc(Grad*sizeof(INT))))
2700 {
2701 SYM_free((char *) NormalPolynom);
2702 return no_memory();
2703 }
2704
2705 if(!(Pol1 = (INT **) UE_malloc((Grad+1)*sizeof(INT*))))
2706 {
2707 SYM_free((char *) NormalPolynom);
2708 SYM_free((char *) Permutation);
2709 return(0);
2710 }
2711
2712 if(!(a_Hoch_q = (INT *) SYM_calloc(Charakteristik+1,sizeof(INT))))
2713 {
2714 SYM_free((char *) NormalPolynom);
2715 SYM_free((char *) Permutation);
2716 SYM_free((char *) Pol1);
2717 return(0);
2718 }
2719
2720 /* Belegung von ax^(m-1)+a^qx^(m-2)+...a^(q^(m-1)) */
2721 for (i=0;i<=Grad;i++)
2722 if(!(Pol1[i] = (INT *) SYM_calloc(Grad,sizeof(INT))))
2723 {
2724 SYM_free ((char *) a_Hoch_q);
2725 SYM_free((char *) NormalPolynom);
2726 SYM_free((char *) Permutation);
2727 for (j=i-1;i>=0;j--)
2728 SYM_free((char *) Pol1[j]);
2729 SYM_free((char *) Pol1);
2730 return(0);
2731 }
2732
2733
2734 Pol1[Grad-1][1] = 1; /* a */
2735
2736 a_Hoch_q[Charakteristik] = 1;
2737 reduzierpoly(a_Hoch_q,Charakteristik,NormalPolynom,Grad);
2738 for (i=0;i<Grad && i<=Charakteristik;i++)
2739 Pol1[Grad-2][i] = a_Hoch_q[i];
2740 SYM_free ((char *) a_Hoch_q);
2741
2742
2743 for (i=Grad-3;i>=0;i--)
2744 spezHoch(Pol1[i+1],Charakteristik,Pol1[i],NormalPolynom,Grad);
2745
2746
2747 if (!gausszerlegu(Pol1,Grad,Permutation))
2748 {
2749 for (i=0;i<=Grad;i++)
2750 SYM_free((char *) Pol1[i]);
2751 SYM_free((char *) Pol1);
2752 SYM_free((char *) Permutation);
2753 SYM_free((char *) NormalPolynom);
2754 return(0);
2755 }
2756 else
2757 {
2758 for (i=0;i<=Grad;i++)
2759 SYM_free((char *) Pol1[i]);
2760 SYM_free((char *) Pol1);
2761 SYM_free((char *) Permutation);
2762 SYM_free((char *) NormalPolynom);
2763 return(1);
2764 }
2765
2766 }
2767
2768
2769 /****************************************************************************/
2770 /* Funktion getNormalPol erzeugt ein Normalpolynom. */
2771 /* */
2772 /* Uebergabeparameter : NormalPolynom, Grad */
2773 /* */
2774 /* Rueckgabeparameter : OK falls erfolgreich, ERROR sonst */
2775 /****************************************************************************/
getNormalPol(NormalPolynom,Grad)2776 static INT getNormalPol(NormalPolynom,Grad) INT *NormalPolynom, Grad;
2777 {
2778 INT i;
2779 INT j;
2780
2781 /* Vorbelegung von NormalPolynom */
2782 for (i=1;i<Grad-1;i++)
2783 NormalPolynom[i] = 0;
2784 NormalPolynom[0] = 1;
2785 NormalPolynom[Grad-1] = UE_subg(0,1);
2786 NormalPolynom[Grad] = 1;
2787
2788 while(!(testirrPolynom(NormalPolynom,Grad) && testNormalPol(NormalPolynom,Grad)))
2789 {
2790 j = 0;
2791 while(NormalPolynom[j]==(Charakteristik-1))
2792 {
2793 if (j>0)
2794 NormalPolynom[j] = 0;
2795 else
2796 NormalPolynom[0] = 1;
2797 j++;
2798 if (j==Grad-1)
2799 return(ERROR);
2800 }
2801 if (j==Grad-1)
2802 return(ERROR);
2803 NormalPolynom[j]++;
2804 }
2805 return(OK);
2806 }
2807
2808
2809 /****************************************************************************/
2810 /* Funktion minimalPolynom berechnet zu einem Element in */
2811 /* Normalbasenreprsentation das Minimalpolynom, */
2812 /* bergabeparameter : Element (Element[0] = Grad, dann die EINTrge a,a^p,.*/
2813 /* minPolynom : Grad eINTrge Platz (da normiert) */
2814 /* (aufsteigende x-Potenzen */
2815 /* Rckgabewert : 1, falls Minimalpoylom berechnet., 0 sonst */
2816 /****************************************************************************/
minimalPolynom(Element,minPolynom)2817 static INT minimalPolynom(Element,minPolynom) INT *Element; INT *minPolynom;
2818 {
2819 INT rueckwert = 1;
2820 INT Grad = Element[0];
2821 INT i;
2822 INT j;
2823 INT *ElementPotenz;
2824 INT *MinusElementPotenz;
2825 INT *zwischElement;
2826 INT **Polynom;
2827 if(!(Polynom = (INT **) UE_malloc((Grad+1)*sizeof(INT *))))
2828 return no_memory();
2829
2830 UE_Platz(&ElementPotenz);
2831 UE_Platz(&MinusElementPotenz);
2832 for (i=0;i<=Grad;i++)
2833 ElementPotenz[i] = Element[i];
2834
2835 UE_negativ(&ElementPotenz,&MinusElementPotenz);
2836 UE_Platz(&zwischElement);
2837
2838 /* Minimalpolynom mit 0 vorbelegen */
2839 for(i=0;i<=Grad;i++)
2840 {
2841 UE_Platz(&Polynom[i]);
2842 Polynom[i][0] = (INT)1;
2843 Polynom[i][1] = (INT)0;
2844 }
2845
2846 /* Fuer die Multiplikation mit x-a^q^i starten wir bei der hchsten
2847 Potenz, auf diese Weise kann das Schiften fr die x-Multiplikation
2848 vernachlssigt werden */
2849
2850 Polynom[Grad][1] = (INT)1;
2851 for(i=0;i<=Grad;i++)
2852 Polynom[Grad-1][i] = MinusElementPotenz[i];
2853
2854 /* Berechnung des Minimalpolynoms */
2855 for(i=Grad;i>1;i--)
2856 {
2857 UE_hoch(&ElementPotenz,Charakteristik,&ElementPotenz);
2858 UE_negativ(&ElementPotenz,&MinusElementPotenz);
2859 for(j=i;j<=Grad;j++)
2860 {
2861 UE_mult(&MinusElementPotenz,&Polynom[j-1],&zwischElement);
2862 UE_add(&Polynom[j-2],&zwischElement,&Polynom[j-2]);
2863 }
2864 UE_add(&MinusElementPotenz,&Polynom[Grad-1],&Polynom[Grad-1]);
2865 }
2866 /* berprfung ob Ergebnispolynom nur aus Skalaren besteht */
2867 for (i=0;i<Grad;i++)
2868 {
2869 minimalErw(&Polynom[i]);
2870 #ifdef UNDEF
2871 if(Polynom[i][0] != 1)
2872 {
2873 for(j=0;j<Grad;j++)
2874 UE_Zeige(&Polynom[j]);
2875 rueckwert = 0;
2876 }
2877 #endif
2878 minPolynom[i] = (Polynom[i])[1];
2879 UE_Free(& Polynom[i]);
2880 }
2881 UE_Free(& Polynom[Grad]);
2882 SYM_free(Polynom);
2883 UE_Free(& ElementPotenz);
2884 UE_Free(& MinusElementPotenz);
2885 UE_Free(&zwischElement);
2886 return(rueckwert);
2887 }
2888
2889
2890
2891 /******************************************************************************/
2892 /* erzeugePol erzeugt ein Tracecompatibles Polynom */
2893 /* Uebergabeparameter : */
2894 /* Datei = Dateizeiger, Grad = gewuenschter Erweiterungsgrad, */
2895 /* tracePolynom = Zeiger auf Tracecompatibles Polynom */
2896 /* */
2897 /* Rueckgabe = 1 falls Erzeugung erfolgreich, 0 sonst. */
2898 /******************************************************************************/
erzeugePol(Grad,tracePolynom,DateiOffen)2899 static INT erzeugePol(Grad,tracePolynom,DateiOffen)
2900 INT Grad; /* gewnschter Erweiterungsgrad */
2901 INT *tracePolynom; /* Platz fr tracecompatibles Polynom */
2902 INT DateiOffen; /*1 falls zweitaufruf */
2903
2904 {
2905 INT Gradsich ;
2906 INT i=2;
2907 INT j;
2908 INT k;
2909 INT spur,hll;
2910
2911 INT *kleinPolynom; /* Tracepolynom p^(n-1) */
2912 INT kleinGrad; /* Grad von kleinPolynom */
2913 INT *kleinElement; /* Element in GF(p^(n-1)) */
2914 INT *grossElement; /* Element in GF(p^n) */
2915 INT *minPolynom; /* Minimalpolynom von kleinElement */
2916 INT *xHOCHmPLUS1; /* Polynom x^m+1 */
2917 INT *Faktor; /* Faktor zu x^p^(Grad-1) - 1 */
2918
2919 INT anzahlPrimfakt = 0; /* Anzahl der Primpotenzfaktoren */
2920 INT Basis[20]; /* Basen der Primpotenzen */
2921 INT Potenz[20]; /* Potenzen der Primpotenzen */
2922 INT **multTafel[20]; /* Zeiger auf Multiplikationstafeln */
2923
2924 INT **Gauss; /* fr Gaussalgorithmus */
2925 INT *Permutation; /* fr Gaussalgorithmus */
2926 INT *NormalPolynom; /* Platz fr Normalpolynom */
2927 INT **hilfsZeiger; /* Hilfszeiger */
2928
2929 /* Zerlegung von Grad in Primfaktoren */
2930 Gradsich = Grad;
2931 while (Gradsich > 1)
2932 {
2933 while(!(Gradsich%i) && Gradsich > 1)
2934 {
2935 Gradsich /= i;
2936 if (anzahlPrimfakt>0 && Basis[anzahlPrimfakt-1] == i)
2937 Potenz[anzahlPrimfakt-1] ++;
2938 else
2939 {
2940 Basis[anzahlPrimfakt] = i;
2941 Potenz[anzahlPrimfakt] = 1;
2942 anzahlPrimfakt++;
2943 }
2944 }
2945 i++;
2946 }
2947
2948 /* Falls nur eine Primpotenz -> Erzeugung, andernfalls Berechnung aus
2949 Multiplikationstabellen bestehender Erweiterungspolynome ->
2950 Rekursiver Aufruf */
2951
2952 if (anzahlPrimfakt==1) /* Starten des Erzeugungsvorgangs */
2953 {
2954 /* Erzeugen eines Normalpolynoms */
2955 UE_Erw_Grad = Grad; /* AK 130197 */
2956 kleinGrad = Grad/Basis[0];
2957 UE_Platz(&kleinElement);
2958
2959 if(!(NormalPolynom = (INT *) UE_malloc((Grad+1)*sizeof(INT))))
2960 return no_memory();
2961
2962 if(getNormalPol(NormalPolynom,Grad) != OK)
2963 {
2964 SYM_free((char *) NormalPolynom);
2965 /*
2966 printf("Kann kein Normalpolynom zum Grad %d erzeugen.\n",Grad);
2967 return(0);
2968 */
2969 error("ff.c: internal error FF-40");
2970 }
2971
2972 /* Hole Polynom vom Grad p^(n-1) */
2973 if(!(kleinPolynom = (INT *) UE_malloc((kleinGrad+1)*sizeof(INT))))
2974 {
2975 SYM_free((char *) NormalPolynom);
2976 return no_memory();
2977 }
2978
2979 if(!(minPolynom = (INT *) UE_malloc((Grad+1)*sizeof(INT))))
2980 {
2981 SYM_free((char *) NormalPolynom);
2982 SYM_free((char *) kleinPolynom);
2983 return no_memory();
2984 }
2985
2986 if(liestracepol(kleinGrad,kleinPolynom,DateiOffen) != OK)
2987 {
2988 SYM_free((char *) NormalPolynom); SYM_free((char *) minPolynom);
2989 SYM_free((char *) kleinPolynom);
2990 return error("internal error FF201");
2991 }
2992
2993 if(erzmulttafel(Grad,-1,NormalPolynom) != OK)
2994 {
2995 SYM_free((char *) NormalPolynom); SYM_free((char *) minPolynom);
2996 SYM_free((char *) kleinPolynom);
2997 return error("internal error FF202");
2998 }
2999 kleinElement[0] = kleinGrad;
3000 for(i=1;i<=kleinGrad;i++)
3001 kleinElement[i] = 0;
3002 k = 1;
3003 while(k)
3004 {
3005 j = 1;
3006 while(kleinElement[j]==Charakteristik-1)
3007 {
3008 kleinElement[j] = 0;
3009 j++;
3010 if (j>kleinGrad)
3011 {
3012 SYM_free((char *) NormalPolynom);
3013 SYM_free((char *) kleinPolynom);
3014 SYM_free((char *) minPolynom);
3015 UE_Free(& kleinElement);
3016 error("internal error FF203");
3017 return ERROR;
3018 }
3019 }
3020 if (j>kleinGrad)
3021 {
3022 SYM_free((char *) NormalPolynom);
3023 SYM_free((char *) kleinPolynom);
3024 SYM_free((char *) minPolynom);
3025 UE_Free(& kleinElement);
3026 error("internal error FF204");
3027 return ERROR;
3028 }
3029 kleinElement[j]++;
3030
3031 /* spur wird mit -Spur von Kleinelement belegt. fuer Trace-kompatibilitaet ist
3032 spur == 1 erforderlich auaerdem mua der 1. Koeffizient
3033 <> 0 sein, da andernfalls das Element (geschiftet) bereits
3034 berprft wurde */
3035
3036 spur = 0;
3037 for (i=1;i<=kleinGrad;i++)
3038 spur = UE_addg(spur,kleinElement[i]);
3039
3040 if(kleinElement[1] && spur == 1)
3041 {
3042 minimalPolynom(kleinElement,minPolynom);
3043 for(i=0;i<kleinGrad;i++)
3044 if(minPolynom[i] != kleinPolynom[i])
3045 i = kleinGrad + 1;
3046 if(i==kleinGrad)
3047 k = 0;
3048 }
3049 }
3050
3051 SYM_free((char*)NormalPolynom);
3052 UE_Platz(&grossElement);
3053 xHOCHmPLUS1 = (INT *) SYM_calloc(Grad+1,sizeof(INT));
3054 xHOCHmPLUS1[0] = UE_subg(0,1);
3055 xHOCHmPLUS1[Grad] = 1;
3056 Faktor = (INT *) SYM_calloc(Basis[0],sizeof(INT));
3057 Faktor[0] = 0;
3058 grossElement[0] = Grad;
3059
3060 for (i=1;i<=kleinGrad;i++)
3061 grossElement[i-1] = kleinElement[i];
3062
3063 UE_Free(&kleinElement);
3064
3065 for (i=kleinGrad;i<=Grad;i++)
3066 grossElement[i] = 0;
3067 k = 1;
3068 while(k && !spezEinsGGT(xHOCHmPLUS1,grossElement,Grad))
3069 {
3070 j = 0;
3071 while(Faktor[j]==Charakteristik-1)
3072 {
3073 Faktor[j] = 0;
3074 grossElement[j] = UE_subg(grossElement[j],1);
3075 grossElement[kleinGrad+j] = UE_addg(grossElement[kleinGrad+j],1);
3076 j++;
3077 if (j==Basis[0])
3078 {
3079 SYM_free((char *) kleinPolynom);
3080 SYM_free((char *) minPolynom);
3081 SYM_free((char *) grossElement);
3082 error("internal error FF206");
3083 return ERROR;
3084 }
3085 }
3086 Faktor[j]++;
3087 grossElement[j] = UE_subg(grossElement[j],1);
3088 grossElement[kleinGrad+j] = UE_addg(grossElement[kleinGrad+j],1);
3089 }
3090 SYM_free((char*)xHOCHmPLUS1); /* AK 030294 */
3091 SYM_free((char*)minPolynom); /* AK 030294 */
3092 SYM_free((char *) kleinPolynom); /* AK 040293 */
3093 SYM_free((char*)Faktor); /* AK 030294 */
3094 for (i=Grad;i>0;i--)
3095 grossElement[i] = grossElement[i-1];
3096 grossElement[0] = Grad;
3097 minimalPolynom(grossElement,tracePolynom);
3098 UE_Free(& grossElement); /* AK 030294 */
3099 }
3100 /****************************************************************************/
3101 else /* Polynom erzeugen aus bestehenden
3102 Polynomen */
3103 {
3104 /* Belegung von Basis[i] mit Basis[i]^Potenz[i] */
3105 for(i=0;i<anzahlPrimfakt;i++)
3106 Basis[i] = UE_power(Basis[i],Potenz[i]);
3107
3108
3109 /* Erzeugung der bentigten Multiplikationstabellen */
3110 for (i=0;i<anzahlPrimfakt;i++)
3111 {
3112 if (erzmulttafel(Basis[i],1,NULL) != OK)
3113 {
3114 error("internal error FF207");
3115 return ERROR;
3116 }
3117 else
3118 multTafel[i]=Mult_Tafel;
3119 }
3120
3121 /* Erzeugung der Multiplikationsmatrix aus den berechneten Tafeln */
3122 if(!(Mult_Tafel = (INT **) UE_malloc(Grad*sizeof(INT*))))
3123 {
3124 return no_memory();
3125 }
3126
3127 if(!(UE_Platz_Mult = (INT *) UE_malloc(Grad*Grad*sizeof(INT))))
3128 {
3129 return no_memory();
3130 }
3131
3132 k = 0;
3133 for (i=0;i<Grad;i++)
3134 {
3135 Mult_Tafel[i] = &UE_Platz_Mult[k];
3136 k += Grad;
3137 }
3138
3139 for(j=0;j<Grad*Grad;j++)
3140 UE_Platz_Mult[j] = 1;
3141
3142 for(k=0;k<Grad;k++)
3143 for(j=0;j<Grad;j++)
3144 for(i=0;i<anzahlPrimfakt;i++)
3145 Mult_Tafel[k][j] *= multTafel[i][k%Basis[i]][j%Basis[i]];
3146
3147
3148 /* Um aus der Multiplikationstafel das zugehrige Polynom zu berechnen
3149 geht man wie folgt vor:
3150 Aufstellen der Basisdarstellung von 1,a,a^2,a^3, ... in Normalbasen-
3151 reprsentation == Matrix A
3152 Aufstellen des Vektors a^Grad in Normalbasenreprsentation = Vektor v
3153 Lsen des Gleichungssystems Ax = v -> Lsung x ist a^Grad in Basis
3154 1,a,a^2,a^3, ... Tracecompatibles Polynom
3155 f(x) = x^Grad-v[Grad-1]*x^(Grad-1)-v[Grad-2]*x^(Grad-2)-....-v[0] . */
3156
3157 /* Vorbereitungen */
3158 UE_Erw_Grad = Grad;
3159 if(!(Permutation = (INT *) UE_malloc(Grad*sizeof(INT))))
3160 return no_memory();
3161 if(!(Gauss = (INT **) UE_malloc(Grad*sizeof(INT*))))
3162 {
3163 SYM_free((char *) Permutation);
3164 return no_memory();
3165 }
3166
3167 if(!(hilfsZeiger = (INT **) UE_malloc((Grad+1)*sizeof(INT*))))
3168 {
3169 SYM_free((char *) Permutation);
3170 SYM_free((char *) Gauss);
3171 return no_memory();
3172 }
3173
3174 for(i=0;i<=Grad;i++)
3175 UE_Platz(&hilfsZeiger[i]);
3176
3177 /* Belegung des 1-Elementes */
3178 hilfsZeiger[0][0] = Grad;
3179 for(i=1;i<=Grad;i++)
3180 hilfsZeiger[0][i] = 1;
3181 /* Belegung von a^1 */
3182 hilfsZeiger[1][0] = Grad;
3183 hilfsZeiger[1][1] = 1;
3184 for(i=2;i<=Grad;i++)
3185 hilfsZeiger[1][i] = 0;
3186
3187 /* Belegung von a^2 bis a^(Grad-1) */
3188 for(i=2;i<=Grad;i++)
3189 {
3190 globalno=1; /* AK 260104*/
3191 UE_mult(&hilfsZeiger[1],&hilfsZeiger[i-1],&hilfsZeiger[i]);
3192 globalno=0;
3193 }
3194
3195 for(i=0;i<Grad;i++)
3196 Gauss[i] = &hilfsZeiger[i][1];
3197
3198 /* transponieren von Gauss */
3199 for(i=0;i<Grad-1;i++)
3200 for(j=i+1;j<Grad;j++)
3201 {
3202 k = Gauss[i][j];
3203 Gauss[i][j] = Gauss[j][i];
3204 Gauss[j][i] = k;
3205 }
3206
3207 if (!gausszerlegu(Gauss,Grad,Permutation))
3208 {
3209 for(i=0;i<=Grad;i++)
3210 UE_Free(& hilfsZeiger[i]);
3211
3212 SYM_free((char *) Permutation);
3213 SYM_free((char *) Gauss);
3214 SYM_free((char *) hilfsZeiger);
3215 error("internal error FF208"); return ERROR;
3216 }
3217 gaussaufloes(Gauss,Grad,&hilfsZeiger[Grad][1],Permutation);
3218 for(i=1;i<=Grad;i++)
3219 tracePolynom[i-1] = UE_subg(0,hilfsZeiger[Grad][i]);
3220 for(i=0;i<=Grad;i++)
3221 UE_Free(& hilfsZeiger[i]);
3222
3223 SYM_free((char *) Permutation);
3224 SYM_free((char *) Gauss);
3225 SYM_free((char *) hilfsZeiger);
3226 SYM_free((char *) Mult_Tafel);
3227 SYM_free((char *) UE_Platz_Mult);
3228
3229 }
3230 einfuegTrace(Grad,tracePolynom);
3231 return OK;
3232 }
3233
3234
3235 /******************************************************************************/
3236 /* Funktion getString verwandelt eine Zahl in einen entsprechenden String im */
3237 /* 10 'ner System. */
3238 /* bergabeparameter Zahl : umzuwandelnde Zahl */
3239 /* String : Zeiger auf Platz fr String */
3240 /* */
3241 /* Rckgabeparameter : Lnge : Lnge des Zugehrigen Strings */
3242 /******************************************************************************/
getString(Zahl,String)3243 static INT getString(Zahl,String) INT Zahl; char *String;
3244 {
3245 INT i=49;
3246 char hilfsString[50];
3247
3248 if(Zahl == 0) { String[0] = '0'; return(1); }
3249 while(Zahl)
3250 {
3251 hilfsString[i--] = 48 + (Zahl % 10);
3252 Zahl /= 10;
3253 }
3254 Zahl = i;
3255 for (i=Zahl+1;i<=49;i++) String[i-Zahl-1] = hilfsString[i];
3256 return(49-Zahl);
3257 }
3258
3259
3260
get_ff_irred(OP p,OP deg,OP pol)3261 INT get_ff_irred(OP p , OP deg, OP pol)
3262 /* AK 211106 V3.1 */
3263 /* the irreducible polynomial of given characteristic and degree, which is
3264 used for the object type FF */
3265 {
3266 INT erg = OK;
3267 INT *tp,i;
3268 OP z;
3269 Charakteristik=S_I_I(p);
3270 tp=(INT*)SYM_calloc(S_I_I(deg)+3,sizeof(INT));
3271 liestracepol(S_I_I(deg),tp,0);
3272 init(MONOPOLY,pol);z=pol;
3273 for (i=0;i<S_I_I(deg);i++)
3274 {
3275 C_L_S(z,callocobject());
3276 b_sk_mo(callocobject(),callocobject(),S_L_S(z));
3277 m_i_i(i,S_PO_S(z));
3278 m_i_i(tp[i],S_PO_K(z));
3279 C_L_N(z,callocobject()); z = S_L_N(z); init(MONOPOLY,z);
3280 }
3281
3282 C_L_S(z,callocobject());
3283 b_sk_mo(callocobject(),callocobject(),S_L_S(z));
3284 m_i_i(i,S_PO_S(z));
3285 m_i_i(1,S_PO_K(z));
3286 SYM_free(tp);
3287 ENDR("get_ff_irred");
3288 }
3289
3290 /******************************************************************************/
3291 /* Funktion lies_tracepol liesst das tracecompatible Polynom zu gegebener */
3292 /* Charakteristik und gegebenen Erweiterungsgrad ein. */
3293 /* */
3294 /* In der Datei trace_??.pol (?? stehen fr die Charakterisktik bei */
3295 /* Charakteristik > 99 wird z.B. trac1021.pol gesucht) */
3296 /* wird nach 'G<GRAD>:' gesucht. Die nachfolgenden Zahlen enthalten die */
3297 /* Positionen a[0] bis a[GRAD-1] des zugehrigen Polynoms. */
3298 /* Sollte dieses nicht vorhanden sein, versucht das Programm es zu erzeugen.*/
3299 /* */
3300 /* Rueckgabewert : 0 , falls das Polynom nicht initialisiert werden konnte, */
3301 /* 1 , sonst. */
3302 /* */
3303 /* Verfasser: Ulrich Eidt */
3304 /* Stand : 16.01.94 */
3305 /******************************************************************************/
liestracepol(Grad,tracePolynom,DateiOffen)3306 static INT liestracepol(Grad,tracePolynom,DateiOffen)
3307 INT Grad; /* Gibt den gewuenschten Erweiterungsgrad an. */
3308 INT tracePolynom[]; /* Vektor mit Platz fuer die EINTraege des ermittelten */
3309 /* Polynoms (die i-te Stelle von tracePolynom gibt den */
3310 /* Koeffizienten zu x^i an der hoechste Koeffizient wird */
3311 /* (da normiert) nicht belegt)). */
3312 INT DateiOffen; /* Kennzeichen ob die Datei bereits offen ist */
3313 {
3314 INT datneu = 0; /* Kennzeichen ob Datei neu */
3315 INT gefunden = 0; /* Kennzeichen ob Polynom gefunden */
3316 INT zahl; /* Einlesevariable */
3317 /* INT gelesen=1;*/ /* Anzahl der gelesenen Zeichen, 0 falls Dateiende*/
3318 INT Pufferzeiger=0; /* Zeiger fuer Bearbeitung des Puffer */
3319 INT hilfsChar=Charakteristik;
3320 INT i;
3321 INT ret_val = OK; /* Rckgabewert */
3322 char Puffer[50]; /* Einlesepuffer */
3323 char Dateiname[15] ; /* Name der Datei */
3324 char Zeichen; /* Platz fuer ein Zeichen wird benutzt beim */
3325 /* Einlesen des Polynoms */
3326 strcpy(Dateiname,"trace_00.pol");
3327
3328 if (!DateiOffen)
3329 {
3330 /* Datei oeffnen und erstes Zeichen lesen */
3331 if(Charakteristik<100)
3332 {
3333 Dateiname[6] = 48+(Charakteristik / 10);
3334 Dateiname[7] = 48+(Charakteristik % 10);
3335 }
3336 else
3337 if(Charakteristik>=100000000)
3338 { error("ff.c:internal error FF50"); return(0); }
3339 else
3340 {
3341 i = 7;
3342 while(hilfsChar)
3343 {
3344 Dateiname[i--] = 48 + (hilfsChar % 10);
3345 hilfsChar /= 10;
3346 }
3347 }
3348
3349 Datei = fopen(Dateiname,"a+");
3350 if (Datei == NULL)
3351 {
3352 /*
3353 Datei = fopen(Dateiname,"w");
3354 if (Datei == NULL)
3355 {
3356 */
3357 /*printf("Die Datei %s ist nicht erstellbar !\n",Dateiname);*/
3358 // error("ff.c:internal error FF51");
3359 if (erzeugePol(Grad,tracePolynom,0) != OK)
3360 return error("ff.c: internal error FF516");
3361 return OK;
3362 /*
3363 }
3364 datneu = 1;
3365 */
3366 }
3367 }
3368 Puffer[0] = 'G';
3369 Pufferzeiger = getString(Grad,&(Puffer[1]));
3370 Puffer[Pufferzeiger+1] = ':';
3371 Pufferzeiger += 2;
3372
3373 /* Suchen des Strings ('G<GRAD>:') */
3374 fseek(Datei,0,0);
3375 i = 0;
3376 while(!gefunden && (Zeichen = getc(Datei)) != (char)EOF)
3377 {
3378 if(Zeichen==Puffer[i])
3379 i++;
3380 else
3381 i = 0;
3382
3383 if (i==Pufferzeiger)
3384 gefunden = 1;
3385 }
3386 /* falls gefunden -> Einlesen */
3387 if (gefunden)
3388 {
3389 for (i=0;i<Grad;i++)
3390 {
3391 /* */
3392 zahl = 0;
3393 while((Zeichen = getc(Datei)) != (char)32 &&
3394 Zeichen != (char)10 && (ret_val==OK))
3395 {
3396 if (Zeichen < (char)48 || Zeichen > (char)57)
3397 { error("ff.c: internal error FF55"); ret_val = ERROR; }
3398 else
3399 zahl = zahl*10+(int)Zeichen-48;
3400 }
3401 tracePolynom[i] = zahl;
3402 }
3403 }
3404 else
3405 {
3406 if (erzeugePol(Grad,tracePolynom,1) != OK)
3407 {
3408 error("ff.c: internal error FF56");
3409 fclose(Datei);
3410 ret_val = ERROR;
3411 }
3412 }
3413 if (!DateiOffen)
3414 {
3415 fclose(Datei);
3416 Datei = NULL; /* AK 260104 */
3417 }
3418 return(ret_val);
3419 }
3420
3421
generators_glnq(n,p,k,v)3422 INT generators_glnq(n,p,k,v) OP n,p,k,v;
3423 /* AK 210104 */
3424 /* Two generating matrices of GL(n,p^k) */
3425 {
3426 OP y,z; INT i,j;
3427 OP nv,ev,nev;
3428 INT erg = OK;
3429 CTO(INTEGER,"generators_glnq(1)",n);
3430 CTO(INTEGER,"generators_glnq(2)",p);
3431 CTO(INTEGER,"generators_glnq(3)",k);
3432
3433 SYMCHECK(S_I_I(n)<1,"generators_glnq:degree not > 0 ");
3434 SYMCHECK(S_I_I(k)<1,"generators_glnq:power not > 0 ");
3435 SYMCHECK(primep(p)==FALSE,"generators_glnq:p not prime ");
3436 CE4(n,p,k,v,generators_glnq);
3437 CALLOCOBJECT3(nv,ev,nev);
3438
3439 erg += m_l_nv(k,nv);
3440 erg += m_l_v(k,ev);FORALL(z,ev,{m_i_i(1,z);});
3441 erg += m_l_v(k,nev);FORALL(z,nev,{m_i_i(S_I_I(p)-1,z);});
3442 erg += m_il_v(2,v);
3443 z=S_V_I(v,0);
3444 erg += m_lh_m(n,n,z);
3445 FORALL(y,z,{ m_vector_ff(p,nv,y); });
3446 erg += m_vector_ff(p,ev,S_M_IJ(z,0,S_M_LI(z)-1));
3447 erg += m_vector_ff(p,nev,S_M_IJ(z,0,0));
3448 for (i=0;i<S_M_LI(z)-1;i++) m_vector_ff(p,nev,S_M_IJ(z,i+1,i));
3449 z=S_V_I(v,1);
3450 erg += m_lh_m(n,n,z);
3451 FORALL(y,z,{ m_vector_ff(p,nv,y); });
3452 erg += primitive_element_ff(p,k,S_M_IJ(z,0,0));
3453 for (i=1;i<S_M_LI(z);i++) m_vector_ff(p,ev,S_M_IJ(z,i,i));
3454 FREEALL3(nv,ev,nev);
3455 ENDR("generators_glnq");
3456 }
3457
3458
3459
3460
primitive_element_ff_given_q(q,b)3461 INT primitive_element_ff_given_q(q,b) OP b; OP q;
3462 /* AK 090304 */
3463 {
3464 INT erg = OK;
3465 CTO(INTEGER,"primitive_element_ff_given_q(1)",q);
3466 SYMCHECK(S_I_I(q) < 2,"primitive_element_ff_given_q:q<2");
3467 SYMCHECK(prime_power_p(q) ==FALSE,"primitive_element_ff_given_q:q no prime power");
3468 {
3469 OP v;
3470 v = CALLOCOBJECT();
3471 erg += factorize_integer(q,v);
3472 erg += primitive_element_ff(S_V_I(v,0),S_V_L(v),b);
3473 FREEALL(v);
3474 }
3475 ENDR("primitive_element_ff_given_q");
3476 }
3477
primitive_element_ff(p,k,c)3478 INT primitive_element_ff(p,k,c) OP p,k,c;
3479 /* AK 210104 */
3480 /* primitive element in GF(p^k) */
3481 {
3482 INT erg = OK;
3483 OP e,a;
3484 INT i;
3485 CE3(p,k,c,primitive_element_ff);
3486 CTO(INTEGER,"primitive_element_ff(1)",p);
3487 CTO(INTEGER,"primitive_element_ff(2)",k);
3488 SYMCHECK(S_I_I(k)<=0,"primitive_element_ff:degree>0");
3489 SYMCHECK(primep(p)==FALSE,"primitive_element_ff:ip not a prime");
3490 e=callocobject(),a=callocobject();
3491 hoch (p,k,a);
3492 first_ff(p,k,e); next(e,e); /* otherwise zero */
3493 do {
3494 copy(e,c);
3495 i = 1;
3496 bb:
3497 if (einsp(c) && (i==S_I_I(a)-1)) { copy(e,c); break; }
3498 if (einsp(c)) continue;
3499 i++; mult_apply(e,c);
3500 goto bb;
3501 } while(next(e,e));
3502 FREEALL2(a,e);
3503 ENDR("primitive_element_ff");
3504 }
3505
3506
generators_slnq(n,p,k,v)3507 INT generators_slnq(n,p,k,v) OP n,p,k,v;
3508 /* AK 220104 */
3509 /* generator of SL(n,p^k) */
3510 {
3511 OP y,z; INT i,j;
3512 OP nv,ev,nev;
3513 INT erg = OK;
3514 CTO(INTEGER,"generators_slnq(1)",n);
3515 CTO(INTEGER,"generators_slnq(2)",p);
3516 CTO(INTEGER,"generators_slnq(3)",k);
3517
3518 SYMCHECK(S_I_I(n)<1,"generators_slnq:degree not > 0 ");
3519 SYMCHECK(S_I_I(k)<1,"generators_slnq:power not > 0 ");
3520 SYMCHECK(primep(p)==FALSE,"generators_slnq:p not prime ");
3521 CE4(n,p,k,v,generators_slnq);
3522
3523 nv = callocobject(); m_l_nv(k,nv);
3524 ev = callocobject(); m_l_v(k,ev);FORALL(z,ev,{m_i_i(1,z);});
3525 nev = callocobject(); m_l_v(k,nev);FORALL(z,nev,{m_i_i(S_I_I(p)-1,z);});
3526 erg += m_il_v(2,v);
3527 z=S_V_I(v,0);
3528 erg += m_lh_m(n,n,z);
3529 FORALL(y,z,{ m_vector_ff(p,nv,y); });
3530 erg += m_vector_ff(p,ev,S_M_IJ(z,0,S_M_LI(z)-1));
3531 erg += m_vector_ff(p,nev,S_M_IJ(z,0,0));
3532 for (i=0;i<S_M_LI(z)-1;i++) m_vector_ff(p,nev,S_M_IJ(z,i+1,i));
3533 z=S_V_I(v,1);
3534 m_lh_m(n,n,z);
3535 FORALL(y,z,{ m_vector_ff(p,nv,y); });
3536
3537 if (((S_I_I(p)==2)||(S_I_I(p)==3) )&&(einsp(k)))
3538 {
3539 erg += m_vector_ff(p,ev,S_M_IJ(z,0,0));
3540 erg += m_vector_ff(p,ev,S_M_IJ(z,0,1));
3541 erg += m_vector_ff(p,ev,S_M_IJ(z,1,1));
3542 }
3543 else {
3544 erg += primitive_element_ff(p,k,S_M_IJ(z,0,0));
3545 erg += invers(S_M_IJ(z,0,0),S_M_IJ(z,1,1));
3546 }
3547 for (i=2;i<S_M_LI(z);i++) m_vector_ff(p,ev,S_M_IJ(z,i,i));
3548 FREEALL3(nv,ev,nev);
3549 ENDR("generators_slnq");
3550 }
3551
rank_ff(a,b)3552 INT rank_ff(a,b) OP a,b;
3553 /* number between 0 ... q-1
3554 for a from GF(q) */
3555 /* a and b may be equal */
3556 /* AK 151204 V3.0 */
3557 {
3558 INT erg = OK;
3559 CTO(FF,"rank_ff(1)",a);
3560 {
3561 OP res,q,ql,h;
3562 INT i;
3563 CALLOCOBJECT4(res,q,ql,h);
3564 M_I_I(0,res);
3565 M_I_I(S_FF_CI(a),q);
3566 M_I_I(1,ql);
3567
3568 for (i=0;i<S_FF_DI(a);i++)
3569 // for (i=S_FF_DI(a)-1;i>=0;i--) AK 290607
3570 {
3571 erg += m_i_i(S_FF_II(a,i+1),h);
3572 MULT_APPLY(ql,h);
3573 ADD_APPLY(h,res);
3574 MULT_APPLY(q,ql);
3575 }
3576 SWAP(b,res);
3577 FREEALL4(res,q,ql,h);
3578 }
3579 ENDR("rank_ff");
3580 }
3581
unrank_given_q_ff(a,q,b)3582 INT unrank_given_q_ff(a,q,b) OP a,q,b;
3583 /* a,b may be equal */
3584 /* AK 161204 V3.0 */
3585 {
3586 INT erg = OK;
3587 CTTO(INTEGER,LONGINT,"unrank_given_q_ff(1)",a);
3588 SYMCHECK(NEGP(a),"unrank_given_q_ff(1):negative number");
3589 CTO(INTEGER,"unrank_given_q_ff(2)",q);
3590 SYMCHECK(prime_power_p(q)==FALSE,"unrank_given_q_ff(2): no prime power");
3591 {
3592 OP v=CALLOCOBJECT();
3593 OP res=CALLOCOBJECT();
3594 OP ca=CALLOCOBJECT();
3595 OP h=CALLOCOBJECT();
3596 INT *ip,i;
3597 factorize(q,v); /* v is vector of equal primes */
3598 Charakteristik=S_V_II(v,0);
3599 UE_Erw_Grad=S_V_LI(v);
3600 erg += init_ff(res);
3601 M_I_I(Charakteristik,S_FF_C(res));
3602 ip = S_FF_IP(res);
3603 ip[0]=S_V_LI(v);
3604 COPY(a,ca);
3605 for (i=0;i<S_V_LI(v);i++)
3606 {
3607 mod(ca,S_V_I(v,0),h); ip[i+1]=S_I_I(h);
3608 ganzdiv(ca,S_V_I(v,0),ca);
3609 }
3610 SWAP(res,b);
3611 FREEALL4(v,res,ca,h);
3612 }
3613 ENDR("unrank_given_q_ff");
3614 }
3615
3616
3617 #endif /* FFTRUE */
3618
3619 /* outside because of macro */
freeself_ff(a)3620 INT freeself_ff(a) OP a;
3621 /* AK 100393 */ /* AK 290402 */
3622 /* AK 210704 V3.0 */
3623 {
3624 INT erg = OK;
3625 CTO(FF,"freeself_ff(1)",a);
3626 {
3627 #ifdef FFTRUE
3628 UE_Free( & S_FF_IP(a)); /* AK 200802 */
3629 C_O_K(a,VECTOR);
3630 freeself_vector(a);
3631 #endif
3632 }
3633 ENDR("freeself_ff");
3634 }
3635 /* outside because of macro */
add_apply_ff(a,b)3636 INT add_apply_ff(a,b) OP a,b;
3637 /* AK 170393 */ /* b = b+a */
3638 {
3639 INT erg = OK;
3640 #ifdef FFTRUE
3641 CTO(FF,"add_apply_ff(1)",a);
3642 if (S_O_K(b) == POLYNOM) /* AK 170304 */
3643 {
3644 OP c=callocobject();
3645 erg += m_scalar_polynom(a,c);
3646 ADD_APPLY(c,b);
3647 erg += freeall(c);
3648 goto endr_ende;
3649 }
3650 else if (S_O_K(b) != FF) /* AK 230294 */ cast_apply_ff(b);
3651 CTO(FF,"add_apply_ff(2)",b);
3652 SYMCHECK(S_FF_CI(a) != S_FF_CI(b), "add_ff:different characteristic");
3653
3654 if( (S_FF_DI(a) == 1) && (S_FF_DI(b)==1) ) { /* AK 270705 */
3655 INT *bp;
3656 bp = S_FF_IP(b);
3657 bp[1]=(S_FF_II(b,1)+S_FF_II(a,1)) % Charakteristik;
3658 }
3659 else
3660 erg += UE_add(& S_FF_IP(a), &S_FF_IP(b), &S_FF_IP(b));
3661 #endif
3662 ENDR("add_apply_ff");
3663 }
3664 /* outside because of macro */
3665
multadd_apply_ff(a,b,c)3666 INT multadd_apply_ff(a,b,c) OP a,b,c;
3667 /* AK 170607 */
3668 /* c += a*b */
3669 {
3670 INT erg =OK;
3671 SYMCHECK(S_FF_CI(a)!=S_FF_CI(b),"multadd_apply_ff:different characteristic");
3672 SYMCHECK(S_FF_CI(a)!=S_FF_CI(c),"multadd_apply_ff:different characteristic");
3673 if ((S_FF_DI(a)==1) && (S_FF_DI(b)==1) && (S_FF_DI(c)==1))
3674 {
3675 INT *ip,*jp,*kp;
3676 ip = S_FF_IP(a);
3677 jp = S_FF_IP(b);
3678 kp = S_FF_IP(c);
3679 kp[1]=kp[1]+ip[1]*jp[1];
3680 kp[1]=kp[1]%S_FF_CI(c);
3681 }
3682 else
3683 multadd_apply_default(a,b,c);
3684 ENDR("multadd_apply_ff");
3685 }
3686
3687
mult_apply_ff(a,b)3688 INT mult_apply_ff(a,b) OP a,b;
3689 /* AK 170393 */ /* AK 211204 V3.0 */
3690 {
3691 INT erg = OK;
3692 CTO(FF,"mult_apply_ff(1)",a);
3693 CE2A(a,b,mult_apply_ff);
3694 {
3695 switch(S_O_K(b))
3696 {
3697 case FF:
3698 {
3699 OP c; INT *ip, *jp;
3700 SYMCHECK(S_FF_CI(a)!=S_FF_CI(b),"mult_apply_ff:different characteristic");
3701 if ((S_FF_DI(a)==1) && (S_FF_DI(b)==1)) { /* easy multiplication */
3702 ip = S_FF_IP(a);
3703 jp = S_FF_IP(b);
3704 jp[1]*=ip[1];
3705 jp[1]=jp[1]%S_FF_CI(b);
3706 goto endr_ende;
3707 }
3708 c = CALLOCOBJECT();
3709 SWAP(b,c);
3710 erg += mult_ff_ff(a,c,b);
3711 FREEALL(c);
3712 goto endr_ende;
3713 }
3714 case MATRIX:
3715 case VECTOR:
3716 {
3717 OP z;
3718 FORALL(z,b,{ erg += mult_apply_ff(a,z); } );
3719 goto endr_ende;
3720 }
3721 default:
3722 erg+= mult_apply_default(a,b);
3723 break;
3724 }
3725 }
3726 ENDR("mult_apply_ff");
3727 }
3728
3729 /* outside because of macro */
nullp_ff(a)3730 INT nullp_ff(a) OP a;
3731 /* AK 110804 V3.0 */
3732 {
3733 #ifdef FFTRUE
3734 /* return UE_ist_null(& S_FF_IP(a)); */
3735 /* UE_IST_NULL( (& S_FF_IP(a))); */
3736 if (S_FF_DI(a) > MAXDEGREE) { UE_IST_NULL( (& S_FF_IP(a))); }
3737 else {
3738 INT *ip = S_FF_IP(a);
3739 INT res,res2;
3740 res=memcmp(ip+1, null_ip, S_FF_DI(a)* sizeof(INT));
3741 // res2=UE_ist_null(& S_FF_IP(a));
3742 // printf("res = %d is_null=%d\n", res, res2);
3743 if (res == 0) return 1; else return 0;
3744 // return res2;
3745 }
3746 #endif /* FFTRUE */
3747 }
3748
3749 /* outside because of macro */
mult_ff(a,b,c)3750 INT mult_ff(a,b,c) OP a,b,c;
3751 /* AK 070802 */
3752 {
3753 INT erg = OK;
3754 #ifdef FFTRUE
3755 CTO(FF,"mult_ff(1)",a);
3756 CTTO(FF,EMPTY,"mult_ff(3)",c);
3757 if (S_O_K(c)==FF) FREESELF(c);
3758 switch(S_O_K(b))
3759 {
3760 case INTEGER:
3761 erg += mult_ff_integer(a,b,c);
3762 break;
3763 case FF:
3764 if (nullp_ff(a))
3765 erg += null_ff(a,c);
3766 else
3767 erg += mult_ff_ff(a,b,c);
3768 break;
3769 case MATRIX: /* AK 300304 */
3770 erg += mult_scalar_matrix(a,b,c);
3771 break;
3772 case MONOM:
3773 erg += mult_scalar_monom(a,b,c);
3774 break;
3775 case POLYNOM:
3776 erg += mult_scalar_polynom(a,b,c);
3777 break;
3778
3779 #ifdef VECTORTRUE
3780 case INTEGERVECTOR:
3781 case VECTOR:
3782 erg += mult_scalar_vector(a,b,c);
3783 break;
3784 #endif /* VECTORTRUE */
3785
3786 default:
3787 WTO("mult_ff(2)",b);
3788 break;
3789 }
3790 #endif /* FFTRUE */
3791 ENDR("mult_ff");
3792 }
null_ff(a,b)3793 INT null_ff(a,b) OP a,b;
3794 /* given a finite field element, compute the corresponding 0 element */
3795 /* AK 040803 */
3796 /* AK 210704 V3.0 */
3797 {
3798 INT erg =OK;
3799 CTO(FF,"null_ff(1)",a);
3800 {
3801 #ifdef FFTRUE
3802
3803 INT i,*ip;
3804 Charakteristik=S_FF_CI(a);
3805 UE_Erw_Grad=S_FF_DI(a);
3806 erg += init_ff(b);
3807 ip = S_FF_IP(b);
3808 for (i=0;i<UE_Erw_Grad;i++) ip[i+1]=0;
3809 ip[0]=UE_Erw_Grad;
3810 M_I_I(Charakteristik,S_FF_C(b));
3811 erg += erzmulttafel(UE_Erw_Grad,(INT)0,NULL); /* UWH */
3812
3813 #endif
3814 }
3815 CTO(FF,"null_ff(2e)",b);
3816 ENDR("null_ff");
3817 }
3818
eins_ff(a,b)3819 INT eins_ff(a,b) OP a,b;
3820 /* given a finite field element, compute the corresponding 1 element */
3821 /* AK 040803 */
3822 /* AK 210704 V3.0 */
3823 {
3824 INT erg =OK;
3825 CTO(FF,"eins_ff(1)",a);
3826 {
3827 #ifdef FFTRUE
3828
3829 INT i,*ip;
3830 Charakteristik=S_FF_CI(a);
3831 UE_Erw_Grad=S_FF_DI(a);
3832 erg += init_ff(b);
3833 ip = S_FF_IP(b);
3834 for (i=0;i<UE_Erw_Grad;i++) ip[i+1]=1;
3835 ip[0]=UE_Erw_Grad;
3836 M_I_I(Charakteristik,S_FF_C(b));
3837 erg += erzmulttafel(UE_Erw_Grad,(INT)0,NULL); /* UWH */
3838 #endif
3839 }
3840 ENDR("eins_ff");
3841 }
3842
all_irred_polynomials(n,q,res)3843 INT all_irred_polynomials(n,q,res) OP n,q,res;
3844 /* all irreducible polynomials of degree n with coeffs
3845 from GF(q) q prime */
3846 /* AK 290304 */
3847 /* AK 210704 V3.0 */
3848 {
3849 INT erg = OK;
3850 CTO(INTEGER,"all_irred_polynomials(1)",n);
3851 SYMCHECK(S_I_I(n)<1,"all_irred_polynomials:degree < 1");
3852 CTO(INTEGER,"all_irred_polynomials(2)",q);
3853 SYMCHECK(prime_power_p(q)==FALSE,"all_irred_polynomials(2): no prime power");
3854 {
3855 #ifdef FFTRUE
3856 if (einsp(n) )
3857 {
3858 OP mox,mcons,ff; INT i=0;
3859 mox=CALLOCOBJECT(); m_iindex_monom(0,mox);
3860 eins_ff_given_q(q,S_PO_K(mox));
3861 CALLOCOBJECT2(ff,mcons);
3862 first_ff_given_q(q,ff);
3863 m_l_v(q,res);
3864 /* there are q different irreducible polynomials of degree 1 */
3865 do {
3866 m_scalar_polynom(ff,mcons);
3867 add(mcons,mox,S_V_I(res,i));
3868 i++;
3869 }
3870 while(next_apply(ff));
3871 FREEALL3(mox,mcons,ff);
3872 }
3873 else
3874 {
3875 OP nn,fac,ff2,d,c,mox,ff;INT i,j,k=1,l,counter=0;
3876 CALLOCOBJECT6(c,d,ff,ff2,fac,nn);
3877
3878 hoch(q,n,c);primitive_element_ff_given_q(c,ff);
3879 DEC(c);m_l_nv(c,c);m_il_v(0,res);
3880 mox=CALLOCOBJECT(); m_iindex_monom(0,mox);
3881 eins_ff_given_q(q,S_PO_K(mox));
3882 /* in bahnen zerlegen */
3883 for (i=0;i<S_V_LI(c);i++)
3884 if (S_V_II(c,i)==0) /* new orbit */
3885 {
3886 eins_ff_given_q(q,nn);
3887 l=1;j=i;
3888 ww:
3889 M_I_I(k,S_V_I(c,j));m_i_i(j,d);
3890 hoch(ff,d,ff2);addinvers_apply(ff2);
3891 add(mox,ff2,fac); /* fac = x-primitive^i */
3892 mult_apply(fac,nn);
3893
3894 j = (S_I_I(q)*j) % S_V_LI(c);
3895 if (S_V_II(c,j)==0) { l++; goto ww; }
3896 else if (S_V_II(c,j)==k) {
3897
3898 if (l==S_I_I(n)) {
3899 OP z;
3900 inc(res);
3901 FORALL(z,nn,{ reduce_ff(S_MO_K(z)); });
3902 swap(S_V_I(res,S_V_LI(res)-1),nn);
3903 }
3904 k++; continue;
3905 }
3906 else {
3907 error("all_irred_polynomials:internal");
3908 }
3909 }
3910 FREEALL3(c,ff,mox);FREEALL4(d,ff2,fac,nn);
3911 }
3912 #endif
3913 }
3914 ENDR("all_irred_polynomials");
3915 }
3916
3917
3918 static INT make_vector_given_q_co();
3919 static INT make_matrix_given_q_co();
3920
make_matrix_add_given_q(q,v)3921 INT make_matrix_add_given_q(q,v) OP q,v;
3922 { return make_matrix_given_q_co(q,v,0); }
make_matrix_mult_given_q(q,v)3923 INT make_matrix_mult_given_q(q,v) OP q,v;
3924 { return make_matrix_given_q_co(q,v,1); }
3925
make_vector_addinvers_given_q(q,v)3926 INT make_vector_addinvers_given_q(q,v) OP q,v;
3927 /* vector entry at position i is the rank number of the additiv invers to the
3928 GF(q) element with rank number i */
3929 { return make_vector_given_q_co(q,v,0); }
3930
make_vector_multinvers_given_q(q,v)3931 INT make_vector_multinvers_given_q(q,v) OP q,v;
3932 /* vector entry at position i is the rank number of the multiplikativ invers to the
3933 GF(q) element with rank number i */
3934 { return make_vector_given_q_co(q,v,1); }
make_vector_frobenius_given_q(q,v)3935 INT make_vector_frobenius_given_q(q,v) OP q,v;
3936 /* vector entry at position i is the rank number of the frobenius image to the
3937 GF(q) element with rank number i */
3938 { return make_vector_given_q_co(q,v,2); }
3939
make_matrix_given_q_co(q,v,s)3940 static INT make_matrix_given_q_co(q,v,s) OP q,v;INT s;
3941 {
3942 INT erg = OK;
3943 {
3944 OP l,r,m,n;
3945 INT i,j;
3946 CALLOCOBJECT4(m,l,r,n);
3947 m_lh_m(q,q,v);
3948 for (i=0;i<S_M_HI(v);i++)
3949 for (j=0;j<S_M_LI(v);j++)
3950 {
3951 m_i_i(i,r);
3952 m_i_i(j,m);
3953 unrank_given_q_ff(r,q,l);
3954 unrank_given_q_ff(m,q,n);
3955 if (s==0) add_apply_ff(l,n);
3956 else if (s==1) mult_apply_ff(l,n);
3957 rank_ff(n,m);
3958 SWAP(m,S_M_IJ(v,i,j));
3959 }
3960 FREEALL4(m,l,r,n);
3961 }
3962 ENDR("make_matrix_given_q_co");
3963 }
3964
make_vector_given_q_co(q,v,s)3965 static INT make_vector_given_q_co(q,v,s) OP q,v;INT s;
3966 {
3967 INT erg = OK;
3968 {
3969 OP l,r;
3970 INT i=0;
3971 CALLOCOBJECT2(l,r);
3972 m_l_v(q,v);
3973 m_i_i(0,r);
3974 do {
3975 unrank_given_q_ff(r,q,l);
3976 if (s==0) addinvers_apply_ff(l);
3977 else if (s==1) {
3978 if (i!=0) invers_apply_ff(l);
3979 }
3980 else if (s==2) {
3981 UE_hoch( & S_FF_IP(l) ,Charakteristik,& S_FF_IP(l) );
3982 }
3983 rank_ff(l,r);
3984 SWAP(r,S_V_I(v,i));
3985 i++;
3986 m_i_i(i,r);
3987 } while (lt(r,q));
3988 FREEALL2(l,r);
3989 }
3990 ENDR("make_vector_given_q_co");
3991
3992 }
3993
3994
3995
3996