/usr/include/eclib/gf.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 | // gf.h: interface for NTL's ZZ_p
//////////////////////////////////////////////////////////////////////////
//
// 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
//
//////////////////////////////////////////////////////////////////////////
// allow for multiple includes
#ifndef _GF_H_
#define _GF_H_
#include <NTL/ZZ_p.h>
extern map<ZZ,ZZ_pContext> ZZ_pContextCache;
class galois_field {
ZZ q;
public:
galois_field(void);
galois_field(const ZZ& qq);
bigint characteristic() const {return q;}
};
#define gf_element ZZ_p
#define NewGF(field,name) gf_element name
#define GFinit(field,name) name=to_ZZ_p(0)
#define GFSetZ(name,Zvalue) name=to_ZZ_p(Zvalue)
#define LiftGF(name) rep(name)
#define GFrandomize(name) random(name)
inline gf_element ZtoGF(const galois_field& F, const bigint& a)
{
return to_ZZ_p(a);
}
inline gf_element ItoGF(const galois_field& F, int a)
{
return to_ZZ_p(a);
}
// NB Here caller must ensure that a is a square; q odd
inline gf_element sqrt(const galois_field& F, const gf_element& a)
{
bigint rd;
sqrt_mod_p(rd,rep(a),F.characteristic());
return ZtoGF(F,rd);
}
// Returns 1 if a is a square (root in r), else 0
inline int sqrt(const galois_field& F, const gf_element& a, gf_element& r)
{
bigint rd = to_ZZ(0), repa=rep(a), q = F.characteristic();
switch(legendre(repa,q))
{
case -1: return 0;
case 1:
sqrt_mod_p(rd,repa,q); // & carry through to next lines
case 0:
r= ZtoGF(F,rd);
}
return 1;
}
inline gf_element root_of_unity(const galois_field& F, int n)
{
ZZ qm1 = F.characteristic()-1;
if(qm1%n !=0) return to_ZZ_p(0);
qm1/=n;
while(1)
{
ZZ_p mu = random_ZZ_p();
if(mu==to_ZZ_p(0)) continue;
power(mu,mu,qm1);
if(mu!=to_ZZ_p(1)) return mu;
}
}
inline bigint order(const gf_element& z)
{
gf_element one=z/z;
gf_element zn=z; bigint n=BIGINT(1);
while (zn!=one) {zn*=z; n+=1;}
return n;
}
inline vector<gf_element> roots_of_unity(const galois_field& Fq, int p)
{
gf_element mu = root_of_unity(Fq,p); // =0 if p ndiv q-1
vector<gf_element>mu_p;
mu_p.resize(p);
GFinit(Fq,mu_p[0]);
GFSetZ(mu_p[0],1);
for(int i=1; i<p; i++) mu_p[i]=mu_p[i-1]*mu;
return mu_p;
}
#endif // #define _GF_H_
|