/usr/include/givaro/chineseremainder.h is in libgivaro-dev 4.0.2-8ubuntu1.
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 | // ==========================================================================
// $Source: /var/lib/cvs/Givaro/src/kernel/zpz/chineseremainder.h,v $
// Copyright(c)'1994-2009 by The Givaro group
// This file is part of Givaro.
// Givaro is governed by the CeCILL-B license under French law
// and abiding by the rules of distribution of free software.
// see the COPYRIGHT file for more details.
// Authors: T. Gautier
// $Id: chineseremainder.h,v 1.12 2011-02-02 16:23:56 briceboyer Exp $
// ==========================================================================
/*!@file chineseremainder.h
* @ingroup zpz
* @brief Chinese Remainder Algorithm for 2 Elements.
* @sa
* For any number of moduli see zpz/givrns.h or zpz/givrnsfixed.h
*/
#ifndef __GIVARO_cra_H
#define __GIVARO_cra_H
#include "givaro/givconfig.h"
#include "givaro/giverror.h"
namespace Givaro {
//! CRA
template<class Ring, class Domain, bool REDUCE = true>
struct ChineseRemainder {
typedef typename Ring::Element RingElement;
typedef typename Domain::Element DomainElement;
// Computes u = M^-1 in the domain
// Then C_12 = (M^-1 mod D)M
ChineseRemainder(const Ring& R, const RingElement& M, const Domain& D)
: _domain(D) {
DomainElement u;
_domain.invin( _domain.init(u, M) );
_domain.convert(C_12, u);
C_12 *= M;
}
// Computes res = A + ((e-A) mod D)*(M^-1 mod D)M
// Then res mod M == A
// And res mod D == e
RingElement & operator()( RingElement& res, const RingElement& A, const DomainElement& e) const {
DomainElement smallA, smallM;
_domain.init(smallA, A);
_domain.init(smallM);
_domain.sub(smallM, e, smallA);
_domain.convert(res, smallM);
res *= C_12;
return res += A;
}
private:
Domain _domain;
RingElement C_12;
};
//! CRA2.
//! JGD 05.12.2007: not required anymore ...
template<class Ring, class Domain>
struct ChineseRemainder<Ring, Domain, false> {
typedef typename Ring::Element RingElement;
typedef typename Domain::Element DomainElement;
// Computes u = M^-1 in the domain
// Then C_12 = (M^-1 mod D)M
ChineseRemainder(const Ring& R, const RingElement& M, const Domain& D)
: _domain(D) {
DomainElement u;
_domain.invin( _domain.init(u, M) );
_domain.convert(C_12, u);
C_12 *= M;
}
// Computes res = A + (e-A)*(M^-1 mod D)M
// Then res mod M == A
// And res mod D == e
RingElement & operator()( RingElement& res, const RingElement& A, const DomainElement& e) const {
_domain.convert(res, e);
res -= A;
res *= C_12;
return res += A;
}
private:
Domain _domain;
RingElement C_12;
};
} // namespace Givaro
#endif // __GIVARO_cra_H
|