#include <iostream>
#include <algorithm>
#include <givaro/givtimer.h>
#include <givaro/givpoly1crt.h>
#include <givaro/givintprime.h>
#include <givaro/montgomery.h>
#include <givaro/extension.h>
#include <givaro/modular.h>
#include <givaro/gfq.h>
#include <givaro/chineseremainder.h>
#include <givaro/givrns.h>
#include <givaro/givrandom.h>
#include <givaro/qfield.h>
typedef GFqDom<int64_t>
Field1;
typedef Modular<int16_t>
Field2;
typedef Modular<Log16>
Field3;
typedef Modular<int32_t>
Field4;
typedef Modular<int64_t>
Field5;
typedef Modular<uint32_t>
Field6;
typedef Montgomery<int32_t>
Field7;
typedef QField<Rational>
Field8;
typedef Modular<Integer>
Field9;
template <typename Field>
bool tmain(
int argc,
char ** argv, GivRandom& generator) {
bool pass = true;
typedef Poly1CRT< Field > CRTSystem;
typedef typename CRTSystem::array_T VScal;
IntPrimeDom ID;
Integer
a( generator() >>(argc>2?atoi(argv[2]):17) );
VScal Primes( argc>1 ? (size_t)atoi(argv[1]):15);
VScal Moduli( Primes.size() );
typename VScal::iterator i = Primes.begin();
typename VScal::iterator e = Moduli.begin();
for(; i != Primes.end(); ++i, ++e) {
do {
}
while ( (std::find(Primes.begin(), i, *i) != i) || (F.
isZero(*i))) ;
}
CRTSystem CRT( F, Primes, "X" );
Poly res;
Timer tim; tim.clear(); tim.start();
CRT.RnsToRing( res, Moduli );
tim.stop();
F.
write( std::cerr << tim <<
" using ") << std::endl;
if (Primes.size() < 14) {
i = Primes.begin();
e = Moduli.begin();
for( ; i != Primes.end(); ++i, ++e)
F.
write(CRT.getpolydom().write(F.
write(std::cout <<
"subs(X=", *i) <<
",", res) <<
") mod " << F.
characteristic() <<
" = ", *e) <<
';' << std::endl;
else
F.
write(CRT.getpolydom().write(F.
write(std::cout <<
"subs(X=", *i) <<
",", res) <<
") = ", *e) <<
';' << std::endl;
}
VScal Verifs( Primes.size() );
CRT.RingToRns( Verifs, res );
typename VScal::const_iterator v = Verifs.begin();
e = Moduli.begin();
for( ; e != Moduli.end(); ++e, ++v)
F.
write(std::cerr <<
"incoherency within ") << std::endl;
F.
write(std::cerr <<
"e: ", *e ) << std::endl;
F.
write(std::cerr <<
"v: ", *v ) << std::endl;
pass = false;
break;
}
CRT.getpolydom().random(generator, res, Degree((int64_t)Primes.size()-1));
CRT.RingToRns( Verifs, res );
Poly nres;
tim.clear(); tim.start();
CRT.RnsToRing( nres, Verifs );
tim.stop();
if (! CRT.getpolydom().areEqual(res,nres) ) {
CRT.getpolydom().write(std::cerr << "incoherency within ") << std::endl;
CRT.getpolydom().write(std::cerr << "r: ", res ) << std::endl;
CRT.getpolydom().write(std::cerr << "n: ", nres ) << std::endl;
pass = false;
}
F.
write( std::cerr << tim <<
" using ") << std::endl;
return pass;
}
template <typename Field>
bool tmainext(
int argc,
char ** argv, GivRandom& generator) {
bool pass = true;
typedef Poly1CRT< Field > CRTSystem;
typedef typename CRTSystem::array_T VScal;
IntPrimeDom ID;
Integer
a( generator() >>(argc>2?atoi(argv[2]):17) );
Field F(ID.nextprimein(
a ),2);
VScal Primes( argc>1 ? (size_t)atoi(argv[1]):15);
VScal Moduli( Primes.size() );
typename VScal::iterator i = Primes.begin();
typename VScal::iterator e = Moduli.begin();
for(; i != Primes.end(); ++i, ++e) {
F.init(*i); F.init(*e);
do {
F.random(generator,*i);
} while ( (std::find(Primes.begin(), i, *i) != i) || (F.isZero(*i))) ;
F.random(generator,*e);
}
for(typename VScal::const_iterator it=Primes.begin(); it!=Primes.end();++it)
F.write(std::cout, *it) << std::endl;
for(typename VScal::const_iterator it=Moduli.begin(); it!=Moduli.end();++it)
F.write(std::cout, *it) << std::endl;
CRTSystem CRT( F, Primes, "X" );
Poly res;
Timer tim; tim.clear(); tim.start();
CRT.RnsToRing( res, Moduli );
tim.stop();
F.write( std::cerr << tim << " using ") << std::endl;
if (Primes.size() < 14) {
i = Primes.begin();
e = Moduli.begin();
for( ; i != Primes.end(); ++i, ++e)
if (F.characteristic()>0)
F.write(CRT.getpolydom().write(F.write(std::cout << "subs(X=", *i) << ",", res) << ") mod " << F.characteristic() << " = ", *e) << ';' << std::endl;
else
F.write(CRT.getpolydom().write(F.write(std::cout << "subs(X=", *i) << ",", res) << ") = ", *e) << ';' << std::endl;
}
VScal Verifs( Primes.size() );
CRT.RingToRns( Verifs, res );
typename VScal::const_iterator v = Verifs.begin();
e = Moduli.begin();
for( ; e != Moduli.end(); ++e, ++v)
if (! F.areEqual(*e, *v) ) {
F.write(std::cerr << "incoherency within ") << std::endl;
F.write(std::cerr << "e: ", *e ) << std::endl;
F.write(std::cerr << "v: ", *v ) << std::endl;
pass = false;
break;
}
CRT.getpolydom().random(generator, res, Degree((int64_t)Primes.size()-1));
CRT.RingToRns( Verifs, res );
Poly nres;
tim.clear(); tim.start();
CRT.RnsToRing( nres, Verifs );
tim.stop();
if (! CRT.getpolydom().areEqual(res,nres) ) {
CRT.getpolydom().write(std::cerr << "incoherency within ") << std::endl;
CRT.getpolydom().write(std::cerr << "r: ", res ) << std::endl;
CRT.getpolydom().write(std::cerr << "n: ", nres ) << std::endl;
pass = false;
}
F.write( std::cerr << tim << " using ") << std::endl;
return pass;
}
int main(
int argc,
char ** argv) {
GivRandom seedor( argc>3 ? (uint64_t)atoi(argv[3]): (uint64_t)
BaseTimer::seed() );
uint64_t seed = seedor.seed();
std::cerr << "seed: " << seed << std::endl;
return
tmain<Field1>(argc, argv, *( new GivRandom(seed)))
&& tmain<Field2>(argc, argv, *( new GivRandom(seed)))
&& tmain<Field3>(argc, argv, *( new GivRandom(seed)))
&& tmain<Field4>(argc, argv, *( new GivRandom(seed)))
&& tmain<Field5>(argc, argv, *( new GivRandom(seed)))
&& tmain<Field6>(argc, argv, *( new GivRandom(seed)))
&& tmain<Field7>(argc, argv, *( new GivRandom(seed)))
&& tmain<Field8>(argc, argv, *( new GivRandom(seed)))
&& tmain<Field9>(argc, argv, *( new GivRandom(seed)))
&& tmainext<Field10>(argc, argv, *( new GivRandom(seed)))
;
}
bool tmainext(int argc, char **argv, GivRandom &generator)
Definition: PolynomialCRT.C:126
Extension Field10
Definition: PolynomialCRT.C:42
Modular< Integer > Field9
Definition: PolynomialCRT.C:39
QField< Rational > Field8
Definition: PolynomialCRT.C:38
int main(int argc, char **argv)
Definition: benchmark-recint_exp.C:20
static int64_t seed()
Definition: givtimer.C:30
UTT characteristic() const
Definition: gfq.inl:224
Rep & init(Rep &r) const
Definition: gfq.h:202
bool isZero(const Rep a) const
Definition: gfq.inl:280
std::ostream & write(std::ostream &s) const
Definition: gfq.inl:606
bool areEqual(const Rep a, const Rep b) const
Definition: gfq.inl:272
static void seeding()
Random numbers (no doc)
Definition: gmp++_int_rand.inl:54
int tmain(int argc, char **argv)
Definition: isunit.C:52
Namespace in which the whole Givaro library resides.
Definition: all_field.C:23
Modular< Integer > Field4
Definition: all_field.C:28
Modular< uint32_t > Field1
Definition: all_field.C:25
GFqDom< int64_t > Field2
Definition: all_field.C:26
Montgomery< int32_t > Field3
Definition: all_field.C:27
StaticElement< Field > Element
Definition: domain_to_operatorstyle.C:27
Modular< Log16 > Field7
Definition: all_field.C:31
Modular< int16_t > Field6
Definition: all_field.C:30
Modular< int32_t > Field5
Definition: all_field.C:29
MG & a
Definition: rmadd.h:143