/Users/mourrain/Devel/mmx/algebramix/src/crt_int.cpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : crt_int.cpp
* DESCRIPTION: Subroutines for efficient Chinese remaindering
* COPYRIGHT  : (C) 2008  Joris van der Hoeven and Gregoire Lecerf
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#include <numerix/integer.hpp>
#include <algebramix/crt_int.hpp>
namespace mmx {

bool is_prime (nat n) {
  static coprime_moduli_sequence
    <modulus<nat,modulus_int_naive<8*sizeof(nat)> >,prime_sequence_int> seq;
  if (n == 0 || n == 1) return false;
  for (nat i= 0; true; i++) {
    nat p= * seq[i];
    if (n % p == 0) return false;
    if (p * p >= n) break;
  }
  return true;
}

bool is_probable_prime (unsigned long int n) {
  return is_probable_prime (integer (n));
}

} // namespace mmx