This file is indexed.

/usr/share/gap/lib/polyconw.gi is in gap-libs 4r6p5-3.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
#############################################################################
##
#W  polyconw.gi                 GAP library                     Thomas Breuer
#W                                                              Frank Lübeck
##
##
#Y  Copyright (C)  1997,  Lehrstuhl D für Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
##  This file contains the implementation part of functions and data around
##  Conway polynomials.
##


###############################################################################
##
#F  PowerModEvalPol( <f>, <g>, <xpownmodf> )
##
InstallGlobalFunction( PowerModEvalPol, function( f, g, xpownmodf )
    local l, res, reslen, powlen, i;

    l:= Length( g );
    res:= [ g[l] ];
    reslen:= 1;
    powlen:= Length( xpownmodf );
    ConvertToVectorRep( res );
    for i in [ 1 .. l-1 ] do
      res:= ProductCoeffs( res, reslen, xpownmodf,
                powlen );                      # `res:= res * x^n;'
      reslen:= ReduceCoeffs( res, f );         # `res:= res mod f;'
      if reslen = 0 then
        res[1]:= g[l-i];                       # `res:= res + g_{l-i+1};'
        reslen:= 1;
      else
        res[1]:= res[1] + g[l-i];              # `res:= res + g_{l-i+1};'
      fi;
    od;
    ShrinkRowVector( res );
    return res;
end );


############################################################################
##
#V  CONWAYPOLYNOMIALS
##
##  This variable was used in GAP 4, version <= 4.4.4 for storing
##  coefficients of (pre)computed Conway polynomials. It is no longer used.
##  


############################################################################
##
#V  CONWAYPOLYNOMIALSINFO
##  
##  strings describing the origin of precomputed Conway polynomials, can be
##  accessed by 'InfoText'
## 
##  also used to remember which data files were read
##  
BindGlobal("CONWAYPOLYNOMIALSINFO",  rec(
 RP := "original list by Richard Parker (from 1980's)\n",
 GAP := "computed with the GAP function by Thomas Breuer, just checks\n\
conditions starting from 'smallest' polynomial\n",
 FL := "computed by a parallelized program by Frank Lübeck, computes\n\
minimal polynomial of all compatible elements (~2001)\n",
 KM := "computed by Kate Minola, a parallelized program for p=2, considering\n\
minimal polynomials of all compatible elements (~2004-2005)\n",
 RPn := "computed by Richard Parker (2004)\n",
 3\,21 := "for p=3, n=21 there appeared a polynomial in some lists/systems\n\
which was not the Conway polynomial; the current one in GAP is correct\n",
 JB := "computed by John Bray using minimal polynomials of consistent \
elements, respectively a similar algorithm as in GAP (~2005)\n",
 conwdat1 := false,
 conwdat2 := false,
 conwdat3 := false,
 # cache for p > 110000 
 cache := rec()
            
) );

############################################################################
##
#V  CONWAYPOLDATA
##  
##  List of lists caching (pre-)computed Conway polynomials.
##  
##  Format: The ConwayPolynomial(p, n) is cached in CONWAYPOLDATA[p][n].
##          The entry has the format [num, fld]. Here fld is one of the 
##          component names of CONWAYPOLYNOMIALSINFO and describes the
##          origin of the polynomial. num is an integer, encoding the 
##          polynomial as follows:
##          Let (a0 + a1 X + a2 X^2 + ... + X^n)*One(GF(p)) be the polynomial
##          where a0, a1, ... are integers in the range 0..p-1. Then 
##              num = a0 + a1 p + a2 p^2 + ... + a<n-1> p^(n-1).
##  
BindGlobal("CONWAYPOLDATA", []);

##  a utility function, checks consistency of a polynomial with Conway
##  polynomials of proper subfield. (But  doesn't check that it is the
##  "smallest" such polynomial  in the ordering used  to define Conway
##  polynomials.
BindGlobal( "IsConsistentPolynomial", function( pol )
  local n, p, ps, x, null, f;
  n := DegreeOfLaurentPolynomial(pol);
  p := Characteristic(pol);
  ps := Set(FactorsInt(n));
  x := IndeterminateOfLaurentPolynomial(pol);
  null := 0*pol;
  f := function(k)
    local kpol;
    kpol := ConwayPolynomial(p, k);
    return Value(kpol, PowerMod(x, (p^n-1)/(p^k-1), pol)) mod pol = null;
  end;
  
  if IsPrimitivePolynomial(GF(p), pol) then
    return ForAll(ps, p-> f(n/p));
  else
    return false;
  fi;
end);

##  This is now incorporated more intelligently in the 'FactInt' package.
##  Commented out, since it wasn't documented anyway.
##  BRENT_FACTORS_LIST := "not loaded, call `AddBrentFactorList();'";
##  AddBrentFactorList := function(    )
##    local str, get, comm, res, n, p, z, pos;
##    Print(
##    "Copying many prime factors of numbers a^n+1 / a^n-1 from Richard Brent's\n",
##    "list `factors.gz' (in \n",
##    "ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/factors/factors.gz\n");
##    str := "";
##    get := OutputTextString(str, false);
##    comm := "wget -q ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/factors/factors.gz -O - | gzip -dc ";
##    Process(DirectoryCurrent(), Filename(DirectoriesSystemPrograms(),"sh"),
##            InputTextUser(), get, ["-c", comm]);
##    res := [[],[]];
##    n := 0;
##    p := Position(str, '\n', 0);
##    while p <> fail do
##      z := str{[n+1..p-1]};
##      pos := Position(z, '-');
##      if pos = fail then
##        pos := Position(z, '+');
##      fi;
##      if pos <> fail then
##        Add(res[1], NormalizedWhitespace(z{[1..pos]}));
##        Add(res[2], Int(NormalizedWhitespace(z{[pos+2..Length(z)]})));
##      fi;
##      n := p;
##      p := Position(str, '\n', n);
##    od; 
##    for p in res[2] do 
##      AddSet(Primes2,p);
##    od;  
##    SortParallel(res[1], res[2]);
##    BRENT_FACTORS_LIST := res;
##  end;

##  A consistency check for the data, loading AddBrentFactorList() is useful
##  for the primitivity tests.
##  
##  # for 41^41-1
##  AddSet(Primes2, 5926187589691497537793497756719);
##  # for 89^89-1
##  AddSet(Primes2, 4330075309599657322634371042967428373533799534566765522517);
##  # for 97^97-1
##  AddSet(Primes2, 549180361199324724418373466271912931710271534073773);
##  AddSet(Primes2,  85411410016592864938535742262164288660754818699519364051241927961077872028620787589587608357877); 
##  for p in [2,113,1009] do IsCheapConwayPolynomial(p,1); od;
##  cp:=CONWAYPOLDATA;;
##  test := [];
##  for i in [1..Length(cp)] do 
##    if IsBound(cp[i]) then
##      for j in [1..Length(cp[i])] do 
##        if IsBound(cp[i][j]) then
##          a := IsConsistentPolynomial(ConwayPolynomial(i,j));
##          Print(i,"   ",j,"   ", a,"\n");
##          Add(test, [i, j, a]);
##        fi;
##      od;
##    fi;
##  od;

##  number of polynomials for GF(p^n) compatible with Conway polynomials for 
##  all proper subfields.
BindGlobal("NrCompatiblePolynomials", function(p, n)
  local ps, lcm;
  ps := Set(Factors(n));
  lcm := Lcm(List(ps, r-> p^(n/r)-1));
  return (p^n-1)/lcm;
end);

##  list of all cases wich less than 100*10^9 compatible polynomials, sorted
##  w.r.t. this number
ConwayCandidates := function()
  local cand, p, i;
  # read data
  for p in [2,113,1009] do
    ConwayPolynomial(p,1);
  od;
  cand := [];;
  for p in Primes{[1..31]} do
    for i in [1..200] do 
      if NrCompatiblePolynomials(p,i) < 100000000000 then
        Add(cand, [NrCompatiblePolynomials(p,i), p, i]);
      fi;
    od;
  od;
  Sort(cand);
  cand := Filtered(cand, a-> not IsBound(CONWAYPOLDATA[a[2]][a[3]]));
  return cand;
end;

##  
##  
####################   end of list of new polynomials   ####################

############################################################################
##
#F  ConwayPol( <p>, <n> ) . . . . . <n>-th Conway polynomial in charact. <p>
##
InstallGlobalFunction( ConwayPol, function( p, n )

    local F,          # `GF(p)'
          one,        # `One( F )'
          zero,       # `Zero( F )'
          eps,        # $(-1)^n$ in `F'
          x,          # indeterminate over `F', as coefficients list
          cpol,       # actual candidate for the Conway polynomial
          nfacs,      # all `n/d' for prime divisors `d' of `n'
          cpols,      # Conway polynomials for `d' in `nfacs'
          pp,         # $p^n-1$
          quots,      # list of $(p^n-1)/(p^d-1)$, for $d$ in `nfacs'
          lencpols,   # `Length( cpols )'
          ppmin,      # list of $(p^n-1)/d$, for prime factors $d$ of $p^n-1$
          found,      # is the actual candidate compatible?
          onelist,    # `[ one ]'
          pow,        # powers of several polynomials
          i,          # loop over `ppmin'
          xpownmodf,  # power of `x', modulo `cpol'
          c,          # loop over `cpol'
          e,          # 1 or -1, used to compute the next candidate
          linfac,     # for a quick precheck
          cachelist,  # list of known Conway pols for given p
          StoreConwayPol;  # maybe move out?

    # Check the arguments.
    if not ( IsPrimeInt( p ) and IsInt( n ) and n > 0 ) then
      Error( "<p> must be a prime, <n> a positive integer" );
    fi;

    # read data files if necessary
    if 1 < p and p <= 109 and CONWAYPOLYNOMIALSINFO.conwdat1 = false then
      ReadLib("conwdat1.g");
    elif 109 < p and p < 1000 and CONWAYPOLYNOMIALSINFO.conwdat2 = false then
      ReadLib("conwdat2.g");
    elif 1000 < p and p < 110000 and CONWAYPOLYNOMIALSINFO.conwdat3 = false then
      ReadLib("conwdat3.g");
    fi;

    if p < 110000 then
      if not IsBound( CONWAYPOLDATA[p] ) then
        CONWAYPOLDATA[p] := [];
      fi;
      cachelist := CONWAYPOLDATA[p];
    else
      if not IsBound( CONWAYPOLYNOMIALSINFO.cache.(String(p)) ) then
        CONWAYPOLYNOMIALSINFO.cache.(String(p)) := [];
      fi;
      cachelist := CONWAYPOLYNOMIALSINFO.cache.(String(p));
    fi;
    if not IsBound( cachelist[n] ) then

      Info( InfoWarning, 1,
            "computing Conway polynomial for p = ", p, " and n = ", n );

      F:= GF(p);
      one:= One( F );
      zero:= Zero( F );

      if n mod 2 = 1 then
        eps:= AdditiveInverse( one );
      else
        eps:= one;
      fi;

      # polynomial `x' (as coefficients list)
      x:= [ zero, one ];
      ConvertToVectorRep(x, p);

      # Initialize the smallest polynomial of degree `n' that is a candidate
      # for being the Conway polynomial.
      # This is `x^n + (-1)^n \*\ z' for the smallest primitive root `z'.
      # If the field can be realized in {\GAP} then `z' is just `Z(p)'.

      # Note that we enumerate monic polynomials with constant term
      # $(-1)^n \alpha$ where $\alpha$ is the smallest primitive element in
      # $GF(p)$ by the compatibility condition (and by existence of such a
      # polynomial).

      cpol:= ListWithIdenticalEntries( n, zero );
      cpol[ n+1 ]:= one;
      cpol[1]:= eps * PrimitiveRootMod( p );
      ConvertToVectorRep(cpol, p);

      if n > 1 then

        # Compute the list of all `n / l' for `l' a prime divisor of `n'
        nfacs:= List( Set( Factors( n ) ), d -> n / d );

        if nfacs = [ 1 ] then

          # `n' is a prime, we have to check compatibility only with
          # the degree 1 Conway polynomial.
          # But this condition is satisfied by choice of the constant term
          # of the candidates.
          cpols:= [];

        else

          # Compute the Conway polynomials for all values $<n> / d$
          # where $d$ is a prime divisor of <n>.
          # They are used for checking compatibility.
          cpols:= List( nfacs, d -> ConwayPol( p, d ) * one );
          List(cpols, f-> ConvertToVectorRep(f, p));
        fi;

        pp:= p^n-1;

        quots:= List( nfacs, x -> pp / ( p^x -1 ) );
        lencpols:= Length( cpols );
        ppmin:= List( Set( Factors( pp ) ), d -> pp/d );

        found:= false;
        onelist:= [ one ];
        # many random polynomials have linear factors, for small p we check 
        # this before trying to check primitivity
        if p < 256 then        
          linfac := List([0..p-2], i-> List([0..n], k-> Z(p)^(i*k)));
          List(linfac, a-> ConvertToVectorRep(a,p));
        else
          linfac := [];
        fi;
        while not found do

          # Test whether `cpol' is primitive.
          #  $f$ is primitive if and only if
          #  0. (check first for small p) there is no zero in GF(p),
          #  1. $f$ divides $X^{p^n-1} -1$, and
          #  2. $f$ does not divide $X^{(p^n-1)/l} - 1$ for every
          #     prime divisor $l$ of $p^n - 1$.
          found := ForAll(linfac, a-> a * cpol <> zero); 
          if found then
            pow:= PowerModCoeffs( x, 2, pp, cpol, n+1 );
            ShrinkRowVector( pow );
            found:= ( pow = onelist );
          fi; 

          i:= 1;
          while found and ( i <= Length( ppmin ) ) do
            pow:= PowerModCoeffs( x, 2, ppmin[i], cpol, n+1 );
            ShrinkRowVector( pow );
            found:= pow <> onelist;
            i:= i+1;
          od;

          # Test compatibility with polynomials in `cpols'.
          i:= 1;
          while found and i <= lencpols do

            # Compute $`cpols[i]'( x^{\frac{p^n-1}{p^m-1}} ) mod `cpol'$.
            xpownmodf:= PowerModCoeffs( x, quots[i], cpol );
            pow:= PowerModEvalPol( cpol, cpols[i], xpownmodf );
            # Note that we need *not* call `ShrinkRowVector'
            # since the list `cpols[i]' has always length at least 2,
            # and a final `ShrinkRowVector' call is done by `PowerModEvalPol'.
            # ShrinkRowVector( pow );
            found:= IsEmpty( pow );
            i:= i+1;

          od;

          if not found then

            # Compute the next candidate according to the chosen ordering.

            # We have $f$ smaller than $g$ for two polynomials $f$, $g$ of
            # degree $n$ with
            # $f = \sum_{i=0}^n (-1)^{n-i} f_i x^i$ and
            # $g = \sum_{i=0}^n (-1)^{n-i} g_i x^i$ if and only if exists
            # $m\leq n$ such that $f_m \< g_m$,
            # and $f_i = g_i$ for all $i > m$.
            # (Note that the thesis of W. Nickel gives a wrong definition.)

            c:= 0;
            e:= eps;
            repeat
              c:= c+1;
              e:= -1*e;
              cpol[c+1]:= cpol[c+1] + e;
            until cpol[c+1] <> zero;

          fi;

        od;

      fi;

      StoreConwayPol := function(cpol, cachelist)
        local found, p, n;
        if IsUnivariatePolynomial(cpol) then
          cpol := CoefficientsOfUnivariatePolynomial(cpol);
        fi;
        p := Characteristic(cpol[1]);
        n := Length(cpol)-1;
        cpol:= List( cpol, IntFFE );

        # Subtract `x^n', strip leading zeroes,
        # and store this polynomial in the global list.
        found:= ShallowCopy( cpol );
        Unbind( found[ n+1 ] );
        ShrinkRowVector( found );
        cachelist[n]:= [List([0..Length(found)-1], k-> p^k) * found, 
                              "GAP"];
      end;
      StoreConwayPol(cpol, cachelist);
    else

      # Decode the polynomial stored in the list (see description of
      # CONWAYPOLDATA above).
      c := cachelist[n][1];
      cpol:= [];
      while c <> 0 do
        Add(cpol, c mod p);
        c := (c - cpol[Length(cpol)]) / p;
      od;
      while Length( cpol ) < n do
        Add( cpol, 0 );
      od;
      Add( cpol, 1 );

    fi;

    # Return the coefficients list.
    return cpol;
end );


############################################################################
##
#F  ConwayPolynomial( <p>, <n> ) .  <n>-th Conway polynomial in charact. <p>
##
InstallGlobalFunction( ConwayPolynomial, function( p, n )
    local F, res;
    if IsPrimeInt( p ) and IsPosInt( n ) then
      F:= GF(p);
      res := UnivariatePolynomial( F, One( F ) * ConwayPol( p, n ) );
      if p < 110000 then
          Setter(InfoText)(res, CONWAYPOLYNOMIALSINFO.(
                  CONWAYPOLDATA[p][n][2]));
      else
          Setter(InfoText)(res, CONWAYPOLYNOMIALSINFO.cache.(
                  String(p))[n][2]);
      fi;
      return res;
    else
      Error( "<p> must be a prime, <n> a positive integer" );
    fi;
end );

InstallGlobalFunction( IsCheapConwayPolynomial, function( p, n )
  if IsPrimeInt( p ) and IsPosInt( n ) then
    # read data files if necessary
    if 1 < p and p <= 109 and CONWAYPOLYNOMIALSINFO.conwdat1 = false then
      ReadLib("conwdat1.g");
    elif 109 < p and p < 1000 and CONWAYPOLYNOMIALSINFO.conwdat2 = false then
      ReadLib("conwdat2.g");
    elif 1000 < p and p < 110000 and CONWAYPOLYNOMIALSINFO.conwdat3 = false then
      ReadLib("conwdat3.g");
    fi;
    if p < 110000 and IsBound(CONWAYPOLDATA[p]) and IsBound(CONWAYPOLDATA[p][n]) then
      return true;
  fi;
  if p >= 110000 and IsBound(CONWAYPOLYNOMIALSINFO.cache.(String(p))) 
     and IsBound(CONWAYPOLYNOMIALSINFO.cache.(String(p))[n]) then
      return true;
  fi;
    # this is not very precise, hopefully good enough for the moment
    if p < 41 then 
      if n < 100 and IsPrimeInt(n) then
        return true;
      fi;
    elif p < 100 then
      if n < 40 and IsPrimeInt(n) then
        return true;
      fi;
    elif p < 1000 then
      if n < 14 and IsPrimeInt(n) then
        return true;
      fi;
    elif p < 2^48 then
      if n in [1,2,3,5,7] then
        return true;
      fi;
    elif p < 2^60 then
        if n in [1,2,3,5] then
            return true;
        fi;    
    elif p < 2^120 then
        if n in [1,2,3] then
            return true;
        fi;    
    elif p < 2^200 then
        if n in [1,2] then
            return true;
        fi;    
    elif n = 1 then
        return false;
    fi;
  fi;
  return false;
end );

# arg: F, n[, i]
InstallGlobalFunction( RandomPrimitivePolynomial, function(arg)
  local F, n, i, pol, FF, one, fac, a;
  F := arg[1];
  n := arg[2];
  if Length(arg) > 2 then
    i := arg[3];
  else
    i := 1;
  fi;
  if IsUnivariatePolynomial(i) then
    i := IndeterminateNumberOfUnivariateRationalFunction(i);
  fi;
  if IsInt(F) then
    F := GF(F);
  fi;
  repeat pol := RandomPol(F, n, i);
  until IsIrreducibleRingElement(PolynomialRing(F), pol);
  FF := AlgebraicExtension(F, pol);
  one := One(FF);
  fac:=List(Set(Factors(Size(FF)-1)), p-> (Size(FF)-1)/p);
  repeat 
    a := Random(FF);
  until ForAll(fac, d-> a^d <> one);
  return MinimalPolynomial(F, a);
end );

##  # utility to write new data files in case of extensions
##  printConwayData := function(f)
##    local i, j, v;
##    for i in [1..Length(CONWAYPOLDATA)] do
##      if IsBound(CONWAYPOLDATA[i]) then
##        PrintTo(f, "CONWAYPOLDATA[",i,"]:=[\n");
##        for j in [1..Length(CONWAYPOLDATA[i])] do
##          if IsBound(CONWAYPOLDATA[i][j]) then
##            PrintTo(f,"[",CONWAYPOLDATA[i][j][1],",\"",CONWAYPOLDATA[i][j][2],
##                  "\"]");
##          fi;
##          PrintTo(f,",");
##        od;
##        PrintTo(f,"];\n");
##      fi;
##    od;
##  end;
##  f := OutputTextFile("guck.g", false);
##  SetPrintFormattingStatus(f, false);
##  printConwayData(f);
##  CloseStream(f);
##  # and then distribute into conwdat?.g


#############################################################################
##
#E