/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
|