This file is indexed.

/usr/include/eclib/legendre.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
// legendre.h: declarations of functions for solving legendre equations
//////////////////////////////////////////////////////////////////////////
//
// 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
// 
//////////////////////////////////////////////////////////////////////////
 
#ifndef _LEGENDRE_H
#define _LEGENDRE_H      1 //flags that this file has been included

#include "quadratic.h"

void minv(const bigint& a1, const bigint& a2, 
	  const bigint& b1, const bigint& b2, 
	  const bigint& c1, const bigint& c2, 
	  bigint& xmin, const bigint& ymin);

// (e+f*i) is (a+b*i) mod (c+d*i) in Z[i]
void GIreduce(const bigint& a, const bigint& b, const bigint& c, 
	      const bigint& d, bigint& e, bigint& f);
// (e+f*i) = gcd ( (a+b*i) , (c+d*i) ) in Z[i]
void GIgcd(const bigint& a, const bigint& b, const bigint& c, 
	   const bigint& d, bigint& e, bigint& f);

// Solve Legendre's equation ax^2+by^2+cz^2=0 using Rusin's reduction, 
// without assuming a,b,c pairwise coprime
// returns 0 if not soluble
int legendre_solve(const bigint& a, const bigint& b, const bigint& c, 
		    bigint& x, bigint& y, bigint& z,
		    int use_lll=0);

int legendre_solve(const bigint& a, const bigint& b, const bigint& c, 
		   const vector<bigint>& factorbase,
		    bigint& x, bigint& y, bigint& z,
		    int use_lll=0);

// Solve Legendre's equation ax^2+by^2+cz^2=0 using Rusin's reduction, 
// given "certificate" (n,p,q) satisfying a|n^2+bc, b|p^2+ac, c|q^2+ab.
// assumes a,b,c pairwise coprime
void legendre_solve_cert(const bigint& a, const bigint& b, const bigint& c, 
		    const bigint& n, const bigint& p, const bigint& q, 
		    bigint& x, bigint& y, bigint& z);

//Ensure that input is valid
int checkin(const bigint& a,const bigint& b,const bigint& c,
	    const bigint& n,const bigint& p,const bigint& q);

// Check that purported solution is OK
int check_leg(const bigint& a, const bigint& b, const bigint& c,
	      bigint& x, bigint& y, bigint& z);

// Check that purported solution is OK & in correct lattice
int check_leg(const bigint& a, const bigint& b, const bigint& c,
	      const bigint& n, const bigint& p, const bigint& q, 
	      bigint& x, bigint& y, bigint& z);

//Peel off a known square factor  u  from coefficient  a
void lem2a(const bigint& a, const bigint& b, const bigint& c, 
	   const bigint& n, const bigint& p, const bigint& q, 
	   const bigint& u,
	   bigint& x, bigint& y, bigint& z);

//Peel off a known square factor  u  from coefficient  b
void lem2b(const bigint& a, const bigint& b, const bigint& c, 
	   const bigint& n, const bigint& p, const bigint& q, 
	   const bigint& u,
	   bigint& x, bigint& y, bigint& z);

//Peel off a known square factor  u  from coefficient  c
void lem2c(const bigint& a, const bigint& b, const bigint& c, 
	   const bigint& n, const bigint& p, const bigint& q, 
	   const bigint& u,
	   bigint& x, bigint& y, bigint& z);


void lem4(const bigint& a, const bigint& b, const bigint& c, 
	  const bigint& n, const bigint& p, const bigint& q, 
	  bigint& x, bigint& y, bigint& z);

// Finds a certificate or returns 0 if none exists:
int make_certificate(const bigint& a, const bigint& b, const bigint& c, 
		     bigint& n, bigint& p, bigint& q);
int make_certificate(const bigint& a, const vector<bigint>& apdivs, 
		     const bigint& b, const vector<bigint>& bpdivs, 
		     const bigint& c, const vector<bigint>& cpdivs, 
		     bigint& n, bigint& p, bigint& q);

// Check to see if  b is congruent to  +- c  mod a  (assumed positive!)
//  if not, how much to divide  a  by to ensure that congruence holds?
bigint should(const bigint& a, const bigint& b, const bigint& c);

void legendre_reduce(const bigint& a, const bigint& b, const bigint& c, 
		     bigint& x0, bigint& y0, bigint& z0, int verb=0);
     // Given a, b, c,  ax^2+by^2+cz^2=0
     // reduces x, y, z in place using Mordell's method (page 48)
     // to achieve Holzer's bounds |z|<=sqrt(ab) etc.
  // (just permutes & passes to conic_mordell_reduce())

void new_legendre_reduce(const bigint& a, const bigint& b, const bigint& c, 
		     bigint& x0, bigint& y0, bigint& z0, int verb=0);
     // Given a, b, c,  ax^2+by^2+cz^2=0
     // reduces x, y, z in place using quadratics

void legendre_via_lll(const bigint& a, const bigint& b, const bigint& c, 
		      const bigint& k1, const bigint& k2, const bigint& k3, 
		      bigint& x, bigint& y, bigint& z);

//
// Given one solution, returns quadratics parametrizing all solutions,
// with discriminants -4bc, -4ac, -4ab.  Here a, b, c are assumed
// pairwise coprime but not square-free, and a>0, b>0, c<0.

void legendre_param(const bigint& a, const bigint& b, const bigint& c, 
		    const bigint& x0, const bigint& y0, const bigint& z0, 
		    quadratic& qx, quadratic& qy, quadratic& qz);

//These versions EITHER return 0 with a solution in x,y,z in the lattice
//               OR return 1, 2, 3 and a square factor u of a, b, c (resp)
//               OR return -1 if something fails (should not happen)
int legendre_solve_cert_1(const bigint& a, const bigint& b, const bigint& c, 
			  const bigint& n, const bigint& p, const bigint& q, 
			  bigint& x, bigint& y, bigint& z,
			  bigint& u);
int lem4_1(const bigint& a, const bigint& b, const bigint& c, 
	   const bigint& n, const bigint& p, const bigint& q, 
	   bigint& x, bigint& y, bigint& z,
	   bigint& u);

bigfloat holzer_measure(const bigint& a, const bigint& b, const bigint& c, 
			const bigint& x, const bigint& y, const bigint& z);
// max{|a|x^2,|b|y^2,|c|z^2}/|abc|   ( < 1 for a Holzer-reduced solution)

#endif