1 // =================================================================== // 2 // Copyright(c)'1994-2009 by The Givaro group 3 // This file is part of Givaro. 4 // Givaro is governed by the CeCILL-B license under French law 5 // and abiding by the rules of distribution of free software. 6 // see the COPYRIGHT file for more details. 7 // Time-stamp: <03 Aug 15 11:40:49 Jean-Guillaume.Dumas@imag.fr> 8 // =================================================================== // 9 10 11 /*! @file givintprime.h 12 * @ingroup integers 13 * @brief primes 14 * - Prime numbers 15 * - Modular powering, 16 * - Fermat numbers, 17 * - Primality tests 18 * - Factorization : (There are parameters to fix) 19 * . 20 */ 21 #ifndef __GIVARO_integers_prime_H 22 #define __GIVARO_integers_prime_H 23 24 #include "givaro/givinteger.h" 25 26 namespace Givaro { 27 28 // =================================================================== // 29 //! Fermat numbers 30 // =================================================================== // 31 class FermatDom : public IntegerDom { 32 public: FermatDom()33 FermatDom() : IntegerDom() {} 34 Rep& fermat (Rep&, const long) const ; 35 int pepin (const long) const ; 36 }; 37 38 39 // =================================================================== // 40 // Primality tests and factorization algorithms 41 // =================================================================== // 42 43 // Those macros are parameters to fix 44 45 // primes known 46 // first array 47 #define LOGMAX 3512 48 #define TABMAX 32768 49 // second array 50 #define LOGMAX2 3031 51 #define TABMAX2 65536 52 // Bounds between big and small 53 #define BOUNDARY_isprime TABMAX 54 #define BOUNDARY_2_isprime TABMAX2 55 56 #define GIVARO_ISLT(a,b) ((a)<(b)) 57 #define GIVARO_ISLEQ(a,b) ((a)<=(b)) 58 #define GIVARO_ISGT(a,b) ((a)>(b)) 59 #define GIVARO_ISGEQ(a,b) ((a)>=(b)) 60 61 62 // =================================================================== // 63 //! Primality tests 64 // =================================================================== // 65 class IntPrimeDom : public IntegerDom { 66 public: IntPrimeDom()67 IntPrimeDom() : IntegerDom() {} 68 69 int isprime(const Rep& n, int r=_GIVARO_ISPRIMETESTS_) const 70 { 71 /* 72 return probab_prime(n); 73 */ 74 // return ((n)<BOUNDARY_isprime ? isprime_Tabule(n) : 75 // (n)<BOUNDARY_2_isprime ? isprime_Tabule2(n) : 76 // probab_prime(n)); 77 int64_t l; 78 return int32_t (int32_t(GIVARO_ISLT(n,BOUNDARY_isprime) ? isprime_Tabule((int32_t)convert(l,n)): 79 GIVARO_ISLT(n,BOUNDARY_2_isprime) ? isprime_Tabule2((int32_t)convert(l,n)): 80 local_prime(n,r))); 81 } 82 83 // if p is a prime power, p = r^return 84 // else return is 0 and r is undefined 85 unsigned int isprimepower(Rep&, const Rep&) const ; 86 87 template<class MyRandIter> 88 unsigned int Miller(MyRandIter& g, const Rep& n=_GIVARO_ISPRIMETESTS_) const ; 89 90 template<class MyRandIter> 91 Rep& test_Lehmann(MyRandIter& g, Rep&, const Rep& n=_GIVARO_ISPRIMETESTS_) const ; 92 93 template<class MyRandIter> 94 int Lehmann(MyRandIter& g, const Rep& n=_GIVARO_ISPRIMETESTS_) const ; 95 96 int isprime_Tabule(const int n) const ; 97 int isprime_Tabule2(const int n) const ; 98 99 Rep& nextprime(Rep&, const Rep&, int r=_GIVARO_ISPRIMETESTS_) const ; 100 Rep& prevprime(Rep&, const Rep&, int r=_GIVARO_ISPRIMETESTS_) const ; 101 Rep& nextprimein(Rep&, int r=_GIVARO_ISPRIMETESTS_) const ; 102 Rep& prevprimein(Rep&, int r=_GIVARO_ISPRIMETESTS_) const ; 103 104 105 // Using Integer 106 int local_prime(const Rep& n, int r=_GIVARO_ISPRIMETESTS_) const 107 { 108 return Protected::probab_prime(n,r); 109 } 110 111 private: 112 static int IP[LOGMAX+5]; // -- table for Tabule 113 static const int * TP; // -- shifted table 114 static int IP2[LOGMAX2+5]; // -- table for Tabule2 115 static const int * TP2; // -- shifted table 116 #if 0 117 static int Tabule2(const Integer& p) ; 118 static int Tabule(const Integer& p) ; 119 static int _memTab2[LOGMAX2+5]; // -- table for Tabule2 120 static const int* _Tab2; // -- shifted _memTabule2 121 static int _memTab[]; // -- table for Tabule 122 static const int* _Tab; // -- shifted _memTabule 123 #endif 124 }; 125 126 } // Givaro 127 #include "givaro/givintprime.inl" 128 #endif // __GIVARO_integers_prime_H 129 130 /* -*- mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ 131 // vim:sts=4:sw=4:ts=4:et:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s 132