00001 00002 /****************************************************************************** 00003 * MODULE : crt_int.cpp 00004 * DESCRIPTION: Subroutines for efficient Chinese remaindering 00005 * COPYRIGHT : (C) 2008 Joris van der Hoeven and Gregoire Lecerf 00006 ******************************************************************************* 00007 * This software falls under the GNU general public license and comes WITHOUT 00008 * ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details. 00009 * If you don't have this file, write to the Free Software Foundation, Inc., 00010 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00011 ******************************************************************************/ 00012 00013 #include <numerix/integer.hpp> 00014 #include <algebramix/crt_int.hpp> 00015 namespace mmx { 00016 00017 bool is_prime (nat n) { 00018 static coprime_moduli_sequence 00019 <modulus<nat,modulus_int_naive<8*sizeof(nat)> >,prime_sequence_int> seq; 00020 if (n == 0 || n == 1) return false; 00021 for (nat i= 0; true; i++) { 00022 nat p= * seq[i]; 00023 if (n % p == 0) return false; 00024 if (p * p >= n) break; 00025 } 00026 return true; 00027 } 00028 00029 bool is_probable_prime (unsigned long int n) { 00030 return is_probable_prime (integer (n)); 00031 } 00032 00033 } // namespace mmx
1.6.1