This file is indexed.

/usr/include/eclib/saturate.h is in libec-dev 20160101-1.

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
// saturate.h: declaration of class saturator for sieving E(Q)/pE(Q)
//////////////////////////////////////////////////////////////////////////
//
// Copyright 1990-2012 John Cremona
// 
// This file is part of the eclib package.
// 
// eclib is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2 of the License, or (at your
// option) any later version.
// 
// eclib is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
// for more details.
// 
// You should have received a copy of the GNU General Public License
// along with eclib; if not, write to the Free Software Foundation,
// Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
// 
//////////////////////////////////////////////////////////////////////////
 

// This is used for proving that points are p-saturated

// allow for multiple includes
#ifndef _SATURATE_
#define _SATURATE_

#ifndef MAX_REPEAT
#define MAX_REPEAT 10
#endif

// automatic saturation will only saturate at primes less than this,
// unless overridden by the sat_bd parameter:
const long SAT_MAX_PRIME = 100000;

class saturator {
private: 
  Curvedata *E;         // the curve 
  vector<Point> Plist;  // the points
  vector<Point> Plistp;  // the p-cotorsion
  vector<Point> Plistx;  // the points plus p-cotorsion
  vector<Point> AllTorsion; // all torsion on E
  vector<bigint> pdivpol; // coefficients of p-division poly (not always used)
  int rank;             // = #Plistx
  bigint disc;          // discriminant of E
  int p;                // current prime to saturate at
  int log_index;         // current points have index p^log_index in original
  primevar qvar;          // loops over possible sieving primes q
  vector<curvemodqbasis> Eqlist;   // E mod q for q=3,5,... (good reduction)
  vector<curvemodqbasis>::iterator Eqptr;
  int newq;               // =1 iff we are using q not yet cahced

  mat TLimage; 
  int TLrank, stuck_counter, verbose, use_div_pols;

  // apply TL map (mod current q) to P, result in (ntp*)[0..p-1]:
  vector<int> TLmap1(const Point& P);
  // apply TL map (mod current q) to Plistx, result is a (ntp*rank) matrix:
  mat TLmap();
  //

public:
  saturator(Curvedata* EE, int verb=0)
    :E(EE), verbose(verb)
    {
      use_div_pols=0;
      disc = getdiscr(*E);
      AllTorsion = torsion_points(*EE);
    }
  ~saturator() {; }
  
  // initialize point list
  void set_points(const vector<Point>& PP) {Plist = PP;}
  // find next usable q and use it
  void nextq();
  // keep on using q until saturated or stuck:
  int test_saturation(int pp, int ms=MAX_REPEAT);
  // try harder with same p (no initialization, but same point set)
  int test_saturation_extra(int pp, int ms=MAX_REPEAT);
  // enlarge basis if dim(kernel)>0:
  int enlarge();
  // repeat testing saturation and enlarging until done:
  // returns log_p of index
  int do_saturation(int pp, int maxntries=10);
  // As above but for all primes up to p, returns index
  int do_saturation_upto(int maxp, int maxntries=10);
  // As above but for all primes in plist, returns success flag, sets
  // index and unsat = list of primes in plist at which
  // saturation failed
  int do_saturation(vector<int> plist, 
		    bigint& index, vector<int>& unsat, int maxntries=10);
  int do_saturation(vector<long> plist, 
		    bigint& index, vector<long>& unsat, int maxntries=10);
  // auto-saturate, after finding an upper bound on saturation index
  int saturate(vector<long>& unsat, bigint& index, long sat_bd=-1, int egr=1, int maxntries=10, int odd_primes_only=0);

  // replace the generating points & reset matrices and ranks
  // (then can use test_saturation_extra())
  // (for re-saturating at a prime p already used)
  void reset_points(const vector<Point>& PP);

  // get p-rank of input + p-cotorsion
  long getprank() const {return rank;};
  // get rank of current image
  long getTLrank() const {return TLrank;};
  // get current q:
  long get_q() const {return (long)qvar;};
  // get current generators (not including p-cotorsion)
  vector<Point> getgens() const {return Plist;};
  // get current generators (including p-cotorsion)
  vector<Point> getxgens() const {return Plistx;};
  // get # steps since last rank increase
  long stuckfor() const {return stuck_counter;};
  // get a nonzero kernel vector (if any)
  vec kernel_vector();
  // test if saturated: 
  int is_saturated() {return rank==TLrank;}
};

// auxiliary functions, not part of the saturator class:

// Use this where Torsion already computed:
vector<Point> pCoTorsion(const vector<Point>& AllTorsion, int p);

// Use this for a one-off computation where Torsion not yet computed:
inline vector<Point> pCoTorsion(Curvedata* EE, int p)
{
  return pCoTorsion(torsion_points(*EE),p);
}

// Saturate the given points automatically (using egr strategy if set)
// Returns success flag and index, and (if success==0) a list of
// primes at which saturation failed.  The array points will be
// changed (if necessary) into a basis for the saturation.
// If sat_bd>-1 it is used to truncate the upper bound

int saturate_points(Curvedata& C, vector<Point>& points, 
		    bigint& index, vector<long>& unsat,  
		    long sat_bd=-1, int egr=1, int verbose=0);


// Bound for the index of saturation for the given set of points If
// egr is set it determines the egr subgroup of the group the points
// generate and only searches for points with egr, This might be faster
// in some cases...
bigint index_bound(Curvedata* C,  vector<Point>& points, 
		   int egr=1, int verbose=0);

// Tamagawa primes: primes dividing any Tamagawa number
vector<long> tamagawa_primes(const Curvedata& C);

#endif